数独

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <cstring>
 4 #include <iostream>
 5 using namespace std;
 6 
 7 int s[9][9];//数独
 8 
 9 bool ans(int x,int y, int z) //判断每一行、每一列、每一个3*3宫内是否符合
10 {
11     int a=x/3,b=y/3;
12     for(int i=0;i<9;i++)  //行列
13         if(s[i][y]==z||s[x][i]==z) return false;
14     for(int i=0;i<3;i++)
15         for(int j=0;j<3;j++)   //  3*3宫
16         if(s[i+a*3][j+b*3]==z)
17         return false;
18     return true;
19 }
20 bool dfs(int cur)   // 深搜
21 {
22     if(cur==81)
23         return true ;
24     if(s[cur/9][cur%9])   // 当前点不为0
25     {
26         return dfs(cur+1);
27     }
28         for(int i=1;i<10;i++)  // 循环填数
29         {
30             if(ans(cur/9,cur%9,i))
31             {
32                 s[cur/9][cur%9]=i;
33                 if(dfs(cur+1))
34                 return true;
35             }
36         }
37     
38     s[cur/9][cur%9]=0;  //倒退回，恢复原状。
39     return false;
40 }
41 int main()
42 {
43     int n;
44     scanf("%d",&n);
45     while(n--)
46     {
47         
48         for(int i=0;i<9;i++)
49             for(int j=0;j<9;j++)
50             scanf("%d",&s[i][j]);
51         dfs(0);
52         for(int i=0;i<9;i++)
53         {
54             for(int j=0;j<8;j++)
55                 printf("%d ",s[i][j]);
56             printf("%d
",s[i][8]);
57         }
58     }
59     return 0;
60 }
61

View Code

9*9数格既81，深搜，如当前位置数不为0，则继续深搜，否则判断从1-9数是否符合当前位置，如符合继续深搜，否则，对当前位置恢复原状，退回上一层。