[已解决]回溯法解决数独问题

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:17:08

1. #include<iostream>
   
2. 
   
3. using namespace std;
   
4. 
   
5. int puzzle[9][9];
   
6. 
   
7. void out()
   
8. {
   
9.     cout << "Puzzle Solved Successfully!" << endl;
   
10.     for (int i = 0; i < 9; i++)
    
11.     {
    
12.         for (int j = 0; j < 9; j++)
    
13.         {
    
14.             cout << puzzle[i][j] << ' ';
    
15.             if (j == 2 || j == 5)
    
16.                cout << "| ";
    
17.         }
    
18.         cout << endl;
    
19.         if (i == 2 || i == 5)
    
20.            cout << "**********************\n";
    
21.     }
    
22. }
    
23. 
    
24. bool isfull()
    
25. {
    
26.     for (int i = 0; i < 9; i++)
    
27.     {
    
28.         for (int j = 0; j < 9; j++)
    
29.         {
    
30.             if (puzzle[i][j] == 0)
    
31.                 return false;
    
32.         }
    
33.     }
    
34.     return true;
    
35. }
    
36. 
    
37. bool judge(int i0, int j0, int number)
    
38. {
    
39.     int x = i0 / 3 * 3;
    
40.     int y = j0 / 3 * 3;
    
41.     int i, j;
    
42.    
    
43.     for (i = x; i < x+3 && i < 9; i++)
    
44.     {
    
45.         for (j = y; j < y+3 && j < 9; j++)
    
46.         {
    
47.             if (puzzle[i][j] == number)
    
48.                 return false;
    
49.         }
    
50.     }
    
51. 
    
52.     for (x = 0; x < 9; x++)
    
53.     {
    
54.         if (puzzle[x][j0] == number)
    
55.             return false;
    
56.     }
    
57. 
    
58.     for (y = 0; y < 9; y++)
    
59.     {
    
60.         if (puzzle[i0][y] == number)
    
61.             return false;
    
62.     }
    
63.     return true;
    
64. }
    
65. 
    
66. void solveSudoku(int i, int j)
    
67. {
    
68.     if ( isfull() )
    
69.     {      
    
70.         out();
    
71.         return;
    
72.     }
    
73.     else
    
74.         {
    
75.         if (puzzle[i][j])
    
76.         {
    
77.             if (j <8) {j++;}
    
78.             else {i++; j = 0;}
    
79.             solveSudoku(i,j);
    
80.         }
    
81.         else
    
82.         {
    
83.                 int p;
    
84.                 for (p = 1; p <= 9; p++)
    
85.                 {
    
86.                     if (judge(i,j,p))
    
87.                     {
    
88.                         puzzle[i][j] = p;
    
89.                         solveSudoku(i,j);
    
90.                     }
    
91.                 }
    
92.                 puzzle[i][j] = 0;
    
93.             }
    
94.     }
    
95. }
    
96. 
    
97. int main()
    
98. {
    
99. 
    
100.         puzzle[0][0] = 0;
     
101.         puzzle[0][1] = 0;
     
102.         puzzle[0][2] = 5;
     
103.         puzzle[0][3] = 3;
     
104.         puzzle[0][4] = 0;
     
105.         puzzle[0][5] = 0;
     
106.         puzzle[0][6] = 0;
     
107.         puzzle[0][7] = 0;
     
108.         puzzle[0][8] = 0;
     
109.        
     
110.         puzzle[1][0] = 8;
     
111.         puzzle[1][1] = 0;
     
112.         puzzle[1][2] = 0;
     
113.         puzzle[1][3] = 0;
     
114.         puzzle[1][4] = 0;
     
115.         puzzle[1][5] = 0;
     
116.         puzzle[1][6] = 0;
     
117.         puzzle[1][7] = 2;
     
118.         puzzle[1][8] = 0;
     
119.        
     
120.         puzzle[2][0] = 0;
     
121.         puzzle[2][1] = 7;
     
122.         puzzle[2][2] = 0;
     
123.         puzzle[2][3] = 0;
     
124.         puzzle[2][4] = 1;
     
125.         puzzle[2][5] = 0;
     
126.         puzzle[2][6] = 5;
     
127.         puzzle[2][7] = 0;
     
128.         puzzle[2][8] = 0;
     
129.        
     
130.         puzzle[3][0] = 4;
     
131.         puzzle[3][1] = 0;
     
132.         puzzle[3][2] = 0;
     
133.         puzzle[3][3] = 0;
     
134.         puzzle[3][4] = 0;
     
135.         puzzle[3][5] = 5;
     
136.         puzzle[3][6] = 3;
     
137.         puzzle[3][7] = 0;
     
138.         puzzle[3][8] = 0;
     
139.        
     
140.         puzzle[4][0] = 0;
     
141.         puzzle[4][1] = 1;
     
142.         puzzle[4][2] = 0;
     
143.         puzzle[4][3] = 0;
     
144.         puzzle[4][4] = 7;
     
145.         puzzle[4][5] = 0;
     
146.         puzzle[4][6] = 0;
     
147.         puzzle[4][7] = 0;
     
148.         puzzle[4][8] = 6;
     
149.        
     
150.         puzzle[5][0] = 0;
     
151.         puzzle[5][1] = 0;
     
152.         puzzle[5][2] = 3;
     
153.         puzzle[5][3] = 2;
     
154.         puzzle[5][4] = 0;
     
155.         puzzle[5][5] = 0;
     
156.         puzzle[5][6] = 0;
     
157.         puzzle[5][7] = 8;
     
158.         puzzle[5][8] = 0;
     
159.        
     
160.         puzzle[6][0] = 0;
     
161.         puzzle[6][1] = 6;
     
162.         puzzle[6][2] = 0;
     
163.         puzzle[6][3] = 5;
     
164.         puzzle[6][4] = 0;
     
165.         puzzle[6][5] = 0;
     
166.         puzzle[6][6] = 0;
     
167.         puzzle[6][7] = 0;
     
168.         puzzle[6][8] = 9;
     
169.        
     
170.         puzzle[7][0] = 0;
     
171.         puzzle[7][1] = 0;
     
172.         puzzle[7][2] = 4;
     
173.         puzzle[7][3] = 0;
     
174.         puzzle[7][4] = 0;
     
175.         puzzle[7][5] = 0;
     
176.         puzzle[7][6] = 0;
     
177.         puzzle[7][7] = 3;
     
178.         puzzle[7][8] = 0;
     
179.        
     
180.         puzzle[8][0] = 0;
     
181.         puzzle[8][1] = 0;
     
182.         puzzle[8][2] = 0;
     
183.         puzzle[8][3] = 0;
     
184.         puzzle[8][4] = 0;
     
185.         puzzle[8][5] = 9;
     
186.         puzzle[8][6] = 7;
     
187.         puzzle[8][7] = 0;
     
188.         puzzle[8][8] = 0;
     
189.        
     
190.     printf("Solving sudoku puzzle.....\n");
     
191.     solveSudoku(0,0);
     
192. 
     
193.     return 0;
     
194. }

复制代码

跳转到最佳答案楼层

Alkane

Alkane

附上测试用例一个：
0 0 5 3 0 0 0 0 0
8 0 0 0 0 0 0 2 0
0 7 0 0 1 0 5 0 0
4 0 0 0 0 5 3 0 0
0 1 0 0 7 0 0 0 6
0 0 3 2 0 0 0 8 0
0 6 0 5 0 0 0 0 9
0 0 4 0 0 0 0 3 0
0 0 0 0 0 9 7 0 0

Alkane

@各路大神

claws0n

不是不想回，算法没有多少人会

claws0n

1. #include<iostream>
   
2. 
   
3. using namespace std;
   
4. 
   
5. int puzzle[9][9];
   
6. 
   
7. void out()
   
8. {
   
9.     cout << "Puzzle Solved Successfully!" << endl;
   
10.     for (int i = 0; i < 9; i++)
    
11.     {
    
12.         for (int j = 0; j < 9; j++)
    
13.         {
    
14.             cout << puzzle[i][j] << ' ';
    
15.             if (j == 2 || j == 5)
    
16.                cout << "| ";
    
17.         }
    
18.         cout << endl;
    
19.         if (i == 2 || i == 5)
    
20.            cout << "**********************\n";
    
21.     }
    
22. }
    
23. 
    
24. bool isfull()
    
25. {
    
26.     for (int i = 0; i < 9; i++)
    
27.     {
    
28.         for (int j = 0; j < 9; j++)
    
29.         {
    
30.             if (puzzle[i][j] == 0)
    
31.                 return false;
    
32.         }
    
33.     }
    
34.     return true;
    
35. }
    
36. 
    
37. bool judge(int i0, int j0, int number)
    
38. {
    
39.     int x = i0 / 3 * 3;
    
40.     int y = j0 / 3 * 3;
    
41.     int i, j;
    
42.    
    
43.     for (i = x; i < x+3 && i < 9; i++)
    
44.     {
    
45.         for (j = y; j < y+3 && j < 9; j++)
    
46.         {
    
47.             if (puzzle[i][j] == number)
    
48.                 return false;
    
49.         }
    
50.     }
    
51. 
    
52.     for (x = 0; x < 9; x++)
    
53.     {
    
54.         if (puzzle[x][j0] == number)
    
55.             return false;
    
56.     }
    
57. 
    
58.     for (y = 0; y < 9; y++)
    
59.     {
    
60.         if (puzzle[i0][y] == number)
    
61.             return false;
    
62.     }
    
63.     return true;
    
64. }
    
65. 
    
66. void solveSudoku(int i, int j)
    
67. {
    
68.     if ( isfull() )
    
69.     {      
    
70.         out();
    
71.         return;
    
72.     }
    
73.     else
    
74.         {
    
75.         if (puzzle[i][j])
    
76.         {
    
77.             if (j <8) {j++;}
    
78.             else {i++; j = 0;}
    
79.             solveSudoku(i,j);
    
80.         }
    
81.         else
    
82.         {
    
83.                 int p;
    
84.                 for (p = 1; p <= 9; p++)
    
85.                 {
    
86.                     if (judge(i,j,p))
    
87.                     {
    
88.                         puzzle[i][j] = p;
    
89.                         solveSudoku(i,j);
    
90.                     }
    
91.                 }
    
92.                 puzzle[i][j] = 0;
    
93.             }
    
94.     }
    
95. }
    
96. 
    
97. int main()
    
98. {
    
99. 
    
100.         puzzle[0][0] = 0;
     
101.         puzzle[0][1] = 0;
     
102.         puzzle[0][2] = 5;
     
103.         puzzle[0][3] = 3;
     
104.         puzzle[0][4] = 0;
     
105.         puzzle[0][5] = 0;
     
106.         puzzle[0][6] = 0;
     
107.         puzzle[0][7] = 0;
     
108.         puzzle[0][8] = 0;
     
109.        
     
110.         puzzle[1][0] = 8;
     
111.         puzzle[1][1] = 0;
     
112.         puzzle[1][2] = 0;
     
113.         puzzle[1][3] = 0;
     
114.         puzzle[1][4] = 0;
     
115.         puzzle[1][5] = 0;
     
116.         puzzle[1][6] = 0;
     
117.         puzzle[1][7] = 2;
     
118.         puzzle[1][8] = 0;
     
119.        
     
120.         puzzle[2][0] = 0;
     
121.         puzzle[2][1] = 7;
     
122.         puzzle[2][2] = 0;
     
123.         puzzle[2][3] = 0;
     
124.         puzzle[2][4] = 1;
     
125.         puzzle[2][5] = 0;
     
126.         puzzle[2][6] = 5;
     
127.         puzzle[2][7] = 0;
     
128.         puzzle[2][8] = 0;
     
129.        
     
130.         puzzle[3][0] = 4;
     
131.         puzzle[3][1] = 0;
     
132.         puzzle[3][2] = 0;
     
133.         puzzle[3][3] = 0;
     
134.         puzzle[3][4] = 0;
     
135.         puzzle[3][5] = 5;
     
136.         puzzle[3][6] = 3;
     
137.         puzzle[3][7] = 0;
     
138.         puzzle[3][8] = 0;
     
139.        
     
140.         puzzle[4][0] = 0;
     
141.         puzzle[4][1] = 1;
     
142.         puzzle[4][2] = 0;
     
143.         puzzle[4][3] = 0;
     
144.         puzzle[4][4] = 7;
     
145.         puzzle[4][5] = 0;
     
146.         puzzle[4][6] = 0;
     
147.         puzzle[4][7] = 0;
     
148.         puzzle[4][8] = 6;
     
149.        
     
150.         puzzle[5][0] = 0;
     
151.         puzzle[5][1] = 0;
     
152.         puzzle[5][2] = 3;
     
153.         puzzle[5][3] = 2;
     
154.         puzzle[5][4] = 0;
     
155.         puzzle[5][5] = 0;
     
156.         puzzle[5][6] = 0;
     
157.         puzzle[5][7] = 8;
     
158.         puzzle[5][8] = 0;
     
159.        
     
160.         puzzle[6][0] = 0;
     
161.         puzzle[6][1] = 6;
     
162.         puzzle[6][2] = 0;
     
163.         puzzle[6][3] = 5;
     
164.         puzzle[6][4] = 0;
     
165.         puzzle[6][5] = 0;
     
166.         puzzle[6][6] = 0;
     
167.         puzzle[6][7] = 0;
     
168.         puzzle[6][8] = 9;
     
169.        
     
170.         puzzle[7][0] = 0;
     
171.         puzzle[7][1] = 0;
     
172.         puzzle[7][2] = 4;
     
173.         puzzle[7][3] = 0;
     
174.         puzzle[7][4] = 0;
     
175.         puzzle[7][5] = 0;
     
176.         puzzle[7][6] = 0;
     
177.         puzzle[7][7] = 3;
     
178.         puzzle[7][8] = 0;
     
179.        
     
180.         puzzle[8][0] = 0;
     
181.         puzzle[8][1] = 0;
     
182.         puzzle[8][2] = 0;
     
183.         puzzle[8][3] = 0;
     
184.         puzzle[8][4] = 0;
     
185.         puzzle[8][5] = 9;
     
186.         puzzle[8][6] = 7;
     
187.         puzzle[8][7] = 0;
     
188.         puzzle[8][8] = 0;
     
189.        
     
190.     printf("Solving sudoku puzzle.....\n");
     
191.     solveSudoku(0,0);
     
192. 
     
193.     return 0;
     
194. }

复制代码

claws0n

77 - 79 可以换成这样，比较好

1. if (j < 8) {solveSudoku(i, j+1);}
   
2. else {solveSudoku(i+1, 0);}

复制代码

余生愿你常欢笑

可以的

钱闻韬

学习