题目网址：http://acm.nyist.net/JudgeOnline/problem.php?pid=722

 老套路，加深下这类题的思路。

1 #include 
     
        2 #include 
      
         3 #define NN 10///NN-1宫格  4 int ok;  5     int a[NN][NN];//  6     int flag_hang[NN][NN];//标记行的可选数字  7     int flag_lie[NN][NN];;//标记列的可选数字  8     int nine[NN][NN];//标记九宫格的可选数字  9  10 void next(int x,int y,int& c,int& d){
   ///由(x,y)查找下一个可填格子的位置(c,d) 11     int i,j; 12     if(a[x][y] == 0){
   ///当前格子为空 13         c = x; 14         d = y; 15         return ; 16     } 17     for(i = x; i < NN; i++){ 18         for(j = y; j < NN; j++){ 19             if(a[i][j] == 0){ 20                 c = i; 21                 d = j; 22                 return ; 23             } 24         } 25         y = 1; 26     } 27     if(i == NN && j == NN){ 28         ok = 1; 29         return ; 30     } 31 } 32  33 void judge(int x,int y,int& figure){
   ///查找相对于figure来说，(x,y)的下一个可填写数字 34     for(int i = figure + 1; i < NN; i++) 35         if(flag_hang[x][i] == 0 && flag_lie[y][i] == 0 && nine[3*((x-1)/3)+(y-1)/3][i] == 0){ 36             figure = i; 37             return ; 38         } 39     figure = 0; 40 } 41  42 int dfs(int x,int y,int figure){
   ///将要填写的格子的坐标,figure为填写数字 43     if(x >= NN || y >= NN)//a[x][y] != 0 || 44         return 1; 45     ///填写完后要刷新行、列、九宫格 46     a[x][y] = figure; 47     flag_hang[x][a[x][y]] = 1; 48     flag_lie[y][a[x][y]] = 1; 49     nine[3*((x-1)/3)+(y-1)/3][a[x][y]] = 1; 50  51     int c=NN,d=NN,newfigure=0,i=1;///(c,d)下一个九宫格应该填写的位置 52     do{ 53         next(x,y,c,d); 54         if(ok == 1) 55             return 1; 56         judge(c,d,newfigure); 57         if(newfigure != 0) 58             dfs(c,d,newfigure); 59     }while(newfigure != 0); 60  61     if(a[x][y] != 0){ 62         flag_hang[x][a[x][y]] = 0; 63         flag_lie[y][a[x][y]] = 0; 64         nine[3*((x-1)/3)+(y-1)/3][a[x][y]] = 0; 65         a[x][y] = 0; 66     } 67     return 0; 68 } 69  70 int main(){ 71     int n,i,j; 72     scanf("%d",&n); 73     while(n--){ 74         ok = 0; 75         for(i = 0; i < NN; i++){ 76             memset(flag_hang[i],0,NN*sizeof(int)); 77             memset(flag_lie[i],0,NN*sizeof(int)); 78             memset(nine[i],0,NN*sizeof(int)); 79         } 80         for(i = 1; i < NN; i++){ 81             for(j = 1; j < NN; j++){ 82                 scanf("%d",&a[i][j]); 83                 flag_hang[i][a[i][j]] = 1; 84                 flag_lie[j][a[i][j]] = 1; 85                 nine[3*((i-1)/3)+(j-1)/3][a[i][j]] = 1; 86             } 87         } 88         int x=1,y=1,figure=0; 89         ///查找第一个可填位置 90         for(i = 1; i < NN; i++) 91         for(j = 1; j < NN; j++) 92         if(a[i][j] == 0){ 93             x = i; 94             y = j; 95             goto L; 96         } 97         ///查找(x,y)格子的可填数字； 98 L:      judge(x,y,figure); 99 100         for(i = 1; i < NN; i++){101             int result = dfs(x,y,figure);102             if(result == 1)103                 break;104             judge(x,y,figure);105         }106         for(i = 1; i < NN; i++){107             for(j = 1; j < NN; j++)108                 printf("%d ",a[i][j]);109             printf("\n");110         }111     }112     return 0;113 }