#include <stdio.h>#include <stdlib.h>#include <string.h> #define MAX 81typedef struct asd{ int x;//待測試的值的x坐標  int y;//待測試的值的y坐標  int p;//待測試的值的位置（1道9代表在九宮格里的位置）  int n;//待測試的值}A;A zhan[MAX];//存放每個放進題目數組測試的數據 void kongque(int queshi[9][9],int aa[9][9]);//函數將候選數數組里去除題目中有的數字 void shuchu(int aa[9][9],int q);//輸出整個數組到文件中 int end(int aa[9][9]); //判斷是否結束 int next(int queshi[9][9],int m,int n,int *x,int *y,int aa[9][9]);//查找下一個應該放進九宮格測試的數據 int chazhao(int aa[9][9],int m,int n,int num);//查找同一行同一列是否有相同的值 int nfrz(int queshi[9][9],int aa[9][9],int m,int n,int *p);//判斷是否滿足入棧條件（就是當前值是否可以插入九宮格） int rz(int *t,int x,int y,int p,int num);//入棧操作 int cz(int *t,int *x,int *y,int *p,int *num);//出棧操作 void aaaa(char aa[10],int a);//計算題目文件的文件名 void bbbb(char aa[10],int a);//計算答案文件的文件名int main(){ int i;//記錄該調用哪道題  for(i=0;i<1000;i++){ int aa[9][9],j,k;//aa數組存放的是題目數獨  int queshi[9][9];//存放的是每個九宮格的待選數  int end=0;//判斷循環結束條件  int h=0,l=0,p=1;//h是候選數的行坐標，l是候選數的列坐標，p代表當前測試數屬于小九宮格的位置  int t=-1;//棧的長度  int s=0,num; FILE *u; char qwe[10]; for(j=0;j<9;j++)//將數組置為每行都是（1到9）  for(k=0;k<9;k++) queshi[j][k]=k+1; aaaa(qwe,i); u=fopen(qwe,"r"); for(j=0;j<9;j++){//讀入題目  for(k=0;k<9;k++){ fscanf(u,"%d",&aa[j][k]); } } fclose(u); memset(zhan,0,sizeof(zhan));//將棧的數據全部置為0  kongque(queshi,aa); while(end!=1){//開始求解  s=next(queshi,h,l,&h,&l,aa);//查找下一個應該放進九宮格測試的數據 if(s==0){//如果找到則進入下一層  s=nfrz(queshi,aa,h,l,&p);//判斷能否插入數獨里  if(s==0){//如果可以則將插入的數據存放到棧里（入棧）   s=rz(&t,h,l,p,queshi[h][l]);  if(s==0){ //如果入棧成功則寫入數獨  aa[h/3*3+(p-1)/3][h%3*3+(p-1)%3]=queshi[h][l];  l++;//待選數跳到下一個   p=1;//重新從第一個小格子開始判斷是否插入   }  else{  end=1;//循環結束   } } else{  s=cz(&t,&h,&l,&p,&num);  if(s==0){//如果出棧成功則擦除插入的數據   aa[h/3*3+(p-1)/3][h%3*3+(p-1)%3]=0;  p++;  }  else  end=1; } } else if(s==-1){ shuchu(aa,i);//輸出求解完畢的數獨  end=1;  } else{ printf("發生未知錯誤"); end=1; } } } return 0;}//函數將候選數數組里去除題目中有的數字 void kongque(int queshi[9][9],int aa[9][9]){ int i,j,x,y; for(i=0;i<j;i++){ for(j=0;j<9;j++){ if(aa[i][j]){ x=i/3*3+j/3;//數獨數組和候選數數組的坐標轉換  y=aa[i][j]-1; queshi[x][y]=0; } } }}//輸出整個數組到文件中void shuchu(int aa[9][9],int q){ int i,j; FILE *p; char qq[10]; bbbb(qq,q); p=fopen(qq,"w"); for(i=0;i<9;i++){ for(j=0;j<9;j++){ fprintf(p,"%d ",aa[i][j]); } fprintf(p,"/n"); } fclose(p);}//判斷是否結束int end(int aa[9][9]){ int i,j,num=0; for(i=0;i<9;i++){ num=0; for(j=0;j<0;j++){ num+=aa[i][j];//檢查每一行是否為1到9  } if(num!=45) return -1; } for(j=0;j<9;j++){//檢查每一列是否為1到9  num=0; for(i=0;i<9;i++){ num+=aa[i][j]; } if(num!=45) return -1; } return 0;}//查找下一個應該放進九宮格測試的數據 int next(int queshi[9][9],int m,int n,int *x,int *y,int aa[9][9]){ int qqq=0; if(n>8){//如果當前小九宮格填寫完畢則進入下一個九宮格  n=0; m++; } if(m>8){ qqq=end(aa);//判斷是否結束  if(qqq!=0) return -1; else return 1; } while(queshi[m][n]==0){ if(n<8) n++; else{ n=0; m++; if(m>8){ qqq=end(aa); if(qqq!=0)  return -1; else  return 1; } } } *x=m;//重新獲取測試的值的x坐標和y坐標  *y=n; return 0;}//查找同一行同一列是否有相同的值 int chazhao(int aa[9][9],int m,int n,int num){ int i; for(i=0;i<9;i++){//查找行  if(aa[m][i]==num) return -1; } for(i=0;i<9;i++){//查找列  if(aa[i][n]==num) return -1; } return 0;}//判斷是否滿足入棧條件（就是當前值是否可以插入九宮格） int nfrz(int queshi[9][9],int aa[9][9],int m,int n,int *p){ int s=*p; int i,t1,t2,num; num=queshi[m][n]; for(i=s;i<10;i++){ t1=(m/3)*3+(s-1)/3; t2=(m%3)*3+(s-1)%3; if(aa[t1][t2]!=0){ s++; continue; } if(chazhao(aa,t1,t2,num)!=0){ s++; continue; } else{ *p=s; return 0; } } return -1;}//入棧操作 int rz(int *t,int x,int y,int p,int num){ if(*t>=MAX){ return -1; } else{ (*t)++; zhan[*t].x=x; zhan[*t].y=y; zhan[*t].p=p; zhan[*t].n=num; return 0; }}//出棧操作 int cz(int *t,int *x,int *y,int *p,int *num){ if(*t==-1){ return -1; } else{ *x=zhan[*t].x; *y=zhan[*t].y; *p=zhan[*t].p; *num=zhan[*t].n; (*t)--; return 0; }}//計算題目文件的文件名 void aaaa(char aa[10],int a){ if(a>=0&&a<10){ aa[0]='0'; aa[1]='0'; aa[2]='0'; aa[3]=a+'0'; } else if(a<100){ aa[0]='0'; aa[1]='0'; aa[2]=a/10+'0'; aa[3]=a%10+'0'; } else if(a<1000){ aa[0]='0'; aa[1]=a/100+'0'; aa[2]=a/10%10+'0'; aa[3]=a%10+'0'; } aa[4]='.'; aa[5]='t'; aa[6]='x'; aa[7]='t'; aa[8]='/0';}//計算答案文件的文件名void bbbb(char aa[10],int a){ if(a>=0&&a<10){ aa[0]='a'; aa[1]='0'; aa[2]='0'; aa[3]=a+'0'; } else if(a<100){ aa[0]='a'; aa[1]='0'; aa[2]=a/10+'0'; aa[3]=a%10+'0'; } else if(a<1000){ aa[0]='a'; aa[1]=a/100+'0'; aa[2]=a/10%10+'0'; aa[3]=a%10+'0'; } aa[4]='.'; aa[5]='t'; aa[6]='x'; aa[7]='t'; aa[8]='/0';}