/*重做了一部分，自己对比*/#include #include #include void initialize();//初始化尝试矩阵matvoid random(int i);//产生一个1到9的随机排列参数i为行数int solve(int num);//根据第一行产生的随机排列以及mat矩阵中每行的尝试顺序
//求解，随机产生一组数独，参数为空格的编号，1到81int isValid(int num, int val);//在num位置填入的数据val是否合法void swap(int *arrays, int left, int right);//交换一行中的顺序void output();//输出函数int mat[9][9];//尝试的矩阵，其中第一行为初始矩阵int answer[9][9];//根据尝试矩阵产生的答案矩阵int main(int argc, char *argv[]){
void initialize();
void output();
initialize();
solve(10);
output();
return0;}//初始化mat和answervoid initialize(){
int i,j;
for(i=0;i<9;i++)
for(j=0;j<9;j++){
mat[j] = j+1;
answer[j] = 0;
}
for(i=0;i<9;i++)
random(i);
for(i=0;i<9;i++)
answer[0] = mat[0];
for(i=0;i<9;i++)
for(j=0;j<9;j++){
printf((j==8)?"%d\n" : "%d",mat[j]);
}
printf("\n");}//回溯算法求解int solve(int num){
int isValid(int num,int val);
int i, row,col;
if (num == 82)
return 1;
row =(num-1)/9;
col = (num-1)%9;
if (answer[row][col]!= 0)
return solve(++num);
for(i=1;i<=9;i++){
if(isValid(num,i))
{
answer[row][col] = i;
if(solve(num+1))
{
return 1;
}
answer[row][col] = 0;
}
}
return 0;}//在num位置填入的数据val是否合法int isValid(int num, int val){
int i,j,row,col;
row = (num-1) / 9;
col = (num-1) % 9;
for(i = 0;i<col;i++)
if(val == answer[row])
return 0;
for(j = 0;j<row;j++){
if(val == answer[j][col])
return 0;
}
row = row/3*3;
col = col/3*3;
if(num%9==0)
for(i = 0;i<=2;i++)
for(j = 0;j<=2;j++)
if(answer[row+i][col+j] == val)
return 0;
return 1;}void random(int row){
void swap(int *arrays, int left, int right);
int len = 9;
int i,cloc;
static int n = 1;
for(i=0;i<len;i++){
srand((unsigned)time(NULL));
cloc = (rand()+(++n)) % (len-i);
swap(mat[row],i,cloc);
}}void swap(int *arrays, int left, int right){
int tmp = arrays[left];
arrays[left] = arrays[right];
arrays[right] = tmp;}void output(){
for(int i=0;i<9;i++)
for(int j=0;j<9;j++)
printf((j == 8)?"%d\n":"%d",answer[j]);} |
