回溯法求解数独的一个CPP程序

1. // sudoku.cpp : Defines the entry point for the console application.
   
2. //
   
3. 
   
4. 
   
5. #include <iostream>
   
6. #include <vector>
   
7. using namespace std;
   
8. 
   
9. const int N = 9;
   
10. 
    
11. void valid(const int a[N][N], int x, int y, vector<int>& validList)
    
12. {
    
13.         for(int m=1; m<=N; m++)
    
14.         {
    
15.                 bool flag = true;
    
16.                 for(int j = 0; j<N; j++)
    
17.                 {
    
18.                         if(a[x][j] == m) //每行只能出现一次
    
19.                         {
    
20.                                 flag = false;
    
21.                                 break;
    
22.                         }
    
23.                         if(a[j][y] == m)//每列只能出现一次
    
24.                         {
    
25.                                 flag = false;
    
26.                                 break;
    
27.                         }
    
28.                         int xx,yy;//每3*3格子只能出现一次
    
29.                         xx = (x/3)*3 + j/3;
    
30.                         yy = (y/3)*3 + j%3;
    
31.                         if(a[xx][yy] == m)
    
32.                         {
    
33.                                 flag = false;
    
34.                                 break;
    
35.                         }
    
36.                 }
    
37.                 if(flag) validList.push_back(m);
    
38.         }
    
39. }
    
40. 
    
41. int b[N][N] = {
    
42.                                 8, 0, 0, 0, 0, 0, 0, 0, 0,
    
43.                                 0, 0, 3, 6, 0, 0, 0, 0, 0,
    
44.                                 0, 7, 0, 0, 9, 0, 2, 0, 0,
    
45.                                 0, 5, 0, 0, 0, 7, 0, 0, 0,
    
46.                                 0, 0, 0, 0, 4, 5, 7, 0, 0,
    
47.                                 0, 0, 0, 1, 0, 0, 0, 3, 0,
    
48.                                 0, 0, 1, 0, 0, 0, 0, 6, 8,
    
49.                                 0, 0, 8, 5, 0, 0, 0, 1, 0,
    
50.                                 0, 9, 0, 0, 0, 0, 4, 0, 0
    
51.                         };
    
52. void print(int a[N][N])
    
53. {
    
54.         for(int i=0; i<N; i++)
    
55.         {
    
56.                 for(int j=0; j<N; j++)
    
57.                 {
    
58.                         printf("%d ", a[i][j]);
    
59.                 }
    
60.                 printf("        ");
    
61.                 for(int j=0; j<N; j++)
    
62.                 {
    
63.                         printf("%d ", b[i][j]);
    
64.                 }
    
65.                 printf("\n");
    
66.         }
    
67.         cout<<endl;
    
68. }
    
69. 
    
70. bool success = false;
    
71. 
    
72. bool solve(int a[N][N], int x, int y)
    
73. {
    
74.         while(a[x][y] != 0)
    
75.         {
    
76.                 if(++y==9)
    
77.                 {
    
78.                         y=0;
    
79.                         x++;
    
80.                         if(x==9) //到达右下角，游戏结束
    
81.                                 return true;
    
82.                 }
    
83.         }
    
84.         if(b[x][y] != 0) return false;
    
85.         vector<int> validList;
    
86.         valid(a, x, y, validList); // 将这个格子所有可以填的数字放到list里
    
87.         if(validList.size() == 0) return false;
    
88.         //遍历这个list，每个数填进去试一试
    
89.         for(int i=0; i<validList.size(); i++)
    
90.         {
    
91.                 a[x][y]=validList[i];
    
92.                 bool f=solve(a, x,y);//递归试算
    
93.                 if(f) return true;
    
94.                 a[x][y]=0;
    
95.         }
    
96.         return false;
    
97. }
    
98. 
    
99. 
    
100. 
     
101. int main()
     
102. {
     
103.         int a[N][N] = {
     
104.                                         8, 0, 0, 0, 0, 0, 0, 0, 0,
     
105.                                         0, 0, 3, 6, 0, 0, 0, 0, 0,
     
106.                                         0, 7, 0, 0, 9, 0, 2, 0, 0,
     
107.                                         0, 5, 0, 0, 0, 7, 0, 0, 0,
     
108.                                         0, 0, 0, 0, 4, 5, 7, 0, 0,
     
109.                                         0, 0, 0, 1, 0, 0, 0, 3, 0,
     
110.                                         0, 0, 1, 0, 0, 0, 0, 6, 8,
     
111.                                         0, 0, 8, 5, 0, 0, 0, 1, 0,
     
112.                                         0, 9, 0, 0, 0, 0, 4, 0, 0
     
113.                                 };
     
114. 
     
115.         solve(a,0,0);
     
116.         print(a);
     
117.         return 0;
     
118. }
     
119. 
     

复制代码

我没搞清楚，a[0][0]=b[0][0]=8,运行到84行应该直接返回false了啊，怎么还能接着运行下去？

这个false返回到116行吗？那有什么意义？。。。

我操尼玛，++y，太隐蔽了，这作者逼格太高......小弟弄懂了，大牛不用回复了