#include <stdio.h>
#include <stdlib.h>
#include <string.h> 
#define MAX 81
typedef 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';
}