[已解决]回溯法解决数独问题（求助）

Alkane

上一次发帖也没人回我，本着不要脸的原则，再发一次
问题就在于回溯的那一步总是卡住，不清楚是那儿出了错
拜托各位啦！！！

1. #include<iostream>
   
2. #include<math.h>
   
3. #include<string>
   
4. #include<stdio.h>
   
5. #include<algorithm>
   
6. #include<vector>
   
7. #include<time.h>
   
8. /*
   
9.                 数独问题
   
10. */
    
11. #define maxn 400000
    
12. using namespace std;
    
13. int num[9][9];
    
14. bool judge(int i, int j, int number)
    
15. {
    
16.         int i0 = i / 3 * 3;
    
17.         int j0 = j / 3 * 3;
    
18.         int ii = i; int jj = j;
    
19.         //对块判断
    
20.         for (i = i0; i < i0 + 3; i++)
    
21.         {
    
22.                 for (j = j0; j < j0 + 3; j++)
    
23.                 {
    
24.                         if (num[i][j] == number)return false;
    
25.                 }
    
26.         }
    
27.         j = jj;
    
28.         //对列判断
    
29.         for (i = 0; i < 9; i++)
    
30.         {
    
31.                 if (num[i][j] == number)return false;
    
32.         }
    
33.         i = ii;
    
34.         //对行判断
    
35.         for (j = 0; j < 9; j++)
    
36.         {
    
37.                 if (num[i][j] == number)return false;
    
38.         }
    
39.         return true;
    
40. }
    
41. bool isfull()
    
42. {
    
43.         for (int i = 0; i < 9; i++)
    
44.         {
    
45.                 for (int j = 0; j < 9; j++)
    
46.                 {
    
47.                         if (num[i][j] == 0)return false;
    
48.                 }
    
49.         }
    
50.         return true;
    
51. }
    
52. void out()
    
53. {
    
54.         cout << "结果" << endl;
    
55.         for (int i = 0; i < 9; i++)
    
56.         {
    
57.                 for (int j = 0; j < 9; j++)
    
58.                 {
    
59.                         cout << num[i][j] << ' ';
    
60.                 }
    
61.                 cout << endl;
    
62.         }
    
63. }
    
64. void dfs(int i, int j)
    
65. {
    
66.         /*
    
67.         到达底部时，退出，此时i=j=8；
    
68.         */
    
69.         if (i>= 8&&isfull())
    
70.         {        
    
71.                 out();
    
72.                 return;
    
73.         }
    
74.         else {
    
75.                 int p;
    
76.                 for (p = 1; p <= 9; p++)
    
77.                 {
    
78.                         /*
    
79.                         只有行、列、以及块都可以放置这个数的时候我们才放置，
    
80.                         不然就退出此次循环，也就是剪掉这个枝
    
81.                         */
    
82.                         if (num[i][j])
    
83.                         {
    
84.                                 if (j <8)dfs(i, j + 1);
    
85.                                 if (j >= 8)dfs(i + 1, 0);
    
86.                                 continue;
    
87.                         }
    
88.                         if (judge(i,j,p))
    
89.                         {
    
90.                                 num[i][j] = p;
    
91.                                 if (j < 8)dfs(i, j + 1);
    
92.                                 if (j >= 8)dfs(i + 1, 0);
    
93.                         /*
    
94.                         放置后记得还原
    
95.                         */
    
96.                                 num[i][j] = 0;
    
97.                         }
    
98.                 }
    
99.         }
    
100. }
     
101. int main()
     
102. {
     
103.         //输入
     
104.         for (int i = 0; i < 9; i++)
     
105.         {
     
106.                 for (int j = 0; j < 9; j++)
     
107.                 {
     
108.                         scanf("%d", &num[i][j]);
     
109.                 }
     
110.         }
     
111.         dfs(0, 0);
     
112.         
     
113.         return 0;
     
114. }

复制代码

最佳答案

月排行榜 / 总排行榜

claws0n

2018-8-30 18:36:38

乖乖，不哭了
上面导入了不必要的头文件
宏定义没有必要
out() 修改一下，输出不好看

关键问题：
judge() 对块的逻辑判断有问题
dfs() p 的循环，位置 i, j 是相对局部，所以没有延续性，应该要相对全局。是可以完成，但进入死循环（虽然答案是错的）。
回溯还原的部分，在 if 判断式内部，不会执行呀

跳转到最佳答案楼层

fc1735

开头加上

1. #define continue break

复制代码

还有很多优化的空间，加油吧！

claws0n

乖乖，不哭了
上面导入了不必要的头文件
宏定义没有必要
out() 修改一下，输出不好看

关键问题：
judge() 对块的逻辑判断有问题
dfs() p 的循环，位置 i, j 是相对局部，所以没有延续性，应该要相对全局。是可以完成，但进入死循环（虽然答案是错的）。
回溯还原的部分，在 if 判断式内部，不会执行呀