[已解决]小甲鱼课后作业S1E36马踏棋盘问题

飞花落尽

请问各位大佬们，我的回溯算法为什么会死循环？

1. #include <stdio.h>
   
2. 
   
3. const int step[8][2] = {{-1,-2},{1,-2},{-2,-1},{2,-1},{-1,2},{-2,1},{1,2},{2,1}};
   
4. int array[8][8] = {0};
   
5. int end(int (*array)[8]);
   
6. 
   
7. int run(int row,int col,int (*array)[8])
   
8. {
   
9.         int i;
   
10.         printf("%2d ",(row - 1) * 8 + col);
    
11.         if (end(array))
    
12.         {
    
13.                 printf("success");
    
14.                 return 1;
    
15.         }
    
16.         for (i = 0;i < 8;i++)
    
17.         {
    
18.                 if (row + step[i][0] >= 1 && col + step[i][1] >= 1 && row + step[i][0] <= 8 && col + step[i][0] <= 8 && !array[row + step[i][0] - 1][col + step[i][1] - 1])
    
19.                 {
    
20.                         array[row + step[i][0] - 1][col + step[i][1] - 1] = (row + step[i][0] - 1) * 8 + (col + step[i][1]);
    
21.                         run(row + step[i][0],col + step[i][1],array);
    
22.                         printf("\b\b\b   ");
    
23.                         array[row + step[i][0] - 1][col + step[i][1] - 1] = 0;
    
24.                 }
    
25.         }
    
26.         return 0;
    
27. }
    
28. 
    
29. int end(int (*array)[8])
    
30. {
    
31.         for (int i = 0;i < 8;i++)
    
32.         {
    
33.                 for (int j = 0;j < 8;j++)
    
34.                 {
    
35.                         if (!array[i][j])
    
36.                         {
    
37.                                 return 0;
    
38.                         }
    
39.                 }
    
40.         }
    
41.         return 1;
    
42. }
    
43. 
    
44. int main(void)
    
45. {
    
46.         int row,col;
    
47.         printf("请输入行数：");
    
48.         scanf("%d",&row);
    
49.         printf("请输入列数：");
    
50.         scanf("%d",&col);
    
51.         array[row - 1][col - 1] = (row - 1) * 8 + col;
    
52.         run(row,col,array);
    
53.        
    
54.         return 0;
    
55. }

复制代码

最佳答案

月排行榜 / 总排行榜

人造人

2021-12-10 23:06:21

你代码逻辑就是错的吧？
还有写代码不认真

1. #include <stdio.h>
   
2. 
   
3. const int step[8][2] = {{-1, -2}, {1, -2}, {-2, -1}, {2, -1}, {-1, 2}, {-2, 1}, {1, 2}, {2, 1}};
   
4. int array[8][8] = {0};
   
5. int end(int (*array)[8]);
   
6. 
   
7. int run(int row, int col, int (*array)[8]) {
   
8.     int i;
   
9.     //printf("%2d ", (row - 1) * 8 + col);
   
10.     if(end(array)) {
    
11.         //printf("success");
    
12.         printf("success\n");
    
13.         return 1;
    
14.     }
    
15.     for(i = 0; i < 8; i++) {
    
16.         if(row + step[i][0] >= 1 && col + step[i][1] >= 1 &&
    
17.            // 认真一点
    
18.            //row + step[i][0] <= 8 && col + step[i][0] <= 8 &&
    
19.            row + step[i][0] <= 8 && col + step[i][1] <= 8 &&
    
20.            !array[row + step[i][0] - 1][col + step[i][1] - 1]) {
    
21.             array[row + step[i][0] - 1][col + step[i][1] - 1] =
    
22.                 (row + step[i][0] - 1) * 8 + (col + step[i][1]);
    
23. 
    
24.             // 上面都减1，这里怎么不减1了？
    
25.             //run(row + step[i][0], col + step[i][1], array);
    
26.             run(row + step[i][0] - 1, col + step[i][1] - 1, array);
    
27.             //printf("\b\b\b   ");
    
28.             array[row + step[i][0] - 1][col + step[i][1] - 1] = 0;
    
29.         }
    
30.     }
    
31.     return 0;
    
32. }
    
33. 
    
34. int end(int (*array)[8]) {
    
35.     for(int i = 0; i < 8; i++) {
    
36.         for(int j = 0; j < 8; j++) {
    
37.             if(!array[i][j]) {
    
38.                 return 0;
    
39.             }
    
40.         }
    
41.     }
    
42.     return 1;
    
43. }
    
44. 
    
45. int main(void) {
    
46.     int row, col;
    
47.     printf("请输入行数：");
    
48.     scanf("%d", &row);
    
49.     printf("请输入列数：");
    
50.     scanf("%d", &col);
    
51. 
    
52.     // 这是在做什么？
    
53.     array[row - 1][col - 1] = (row - 1) * 8 + col;
    
54. 
    
55.     run(row, col, array);
    
56. 
    
57.     return 0;
    
58. }
    

复制代码

跳转到最佳答案楼层

人造人

你代码逻辑就是错的吧？
还有写代码不认真

1. #include <stdio.h>
   
2. 
   
3. const int step[8][2] = {{-1, -2}, {1, -2}, {-2, -1}, {2, -1}, {-1, 2}, {-2, 1}, {1, 2}, {2, 1}};
   
4. int array[8][8] = {0};
   
5. int end(int (*array)[8]);
   
6. 
   
7. int run(int row, int col, int (*array)[8]) {
   
8.     int i;
   
9.     //printf("%2d ", (row - 1) * 8 + col);
   
10.     if(end(array)) {
    
11.         //printf("success");
    
12.         printf("success\n");
    
13.         return 1;
    
14.     }
    
15.     for(i = 0; i < 8; i++) {
    
16.         if(row + step[i][0] >= 1 && col + step[i][1] >= 1 &&
    
17.            // 认真一点
    
18.            //row + step[i][0] <= 8 && col + step[i][0] <= 8 &&
    
19.            row + step[i][0] <= 8 && col + step[i][1] <= 8 &&
    
20.            !array[row + step[i][0] - 1][col + step[i][1] - 1]) {
    
21.             array[row + step[i][0] - 1][col + step[i][1] - 1] =
    
22.                 (row + step[i][0] - 1) * 8 + (col + step[i][1]);
    
23. 
    
24.             // 上面都减1，这里怎么不减1了？
    
25.             //run(row + step[i][0], col + step[i][1], array);
    
26.             run(row + step[i][0] - 1, col + step[i][1] - 1, array);
    
27.             //printf("\b\b\b   ");
    
28.             array[row + step[i][0] - 1][col + step[i][1] - 1] = 0;
    
29.         }
    
30.     }
    
31.     return 0;
    
32. }
    
33. 
    
34. int end(int (*array)[8]) {
    
35.     for(int i = 0; i < 8; i++) {
    
36.         for(int j = 0; j < 8; j++) {
    
37.             if(!array[i][j]) {
    
38.                 return 0;
    
39.             }
    
40.         }
    
41.     }
    
42.     return 1;
    
43. }
    
44. 
    
45. int main(void) {
    
46.     int row, col;
    
47.     printf("请输入行数：");
    
48.     scanf("%d", &row);
    
49.     printf("请输入列数：");
    
50.     scanf("%d", &col);
    
51. 
    
52.     // 这是在做什么？
    
53.     array[row - 1][col - 1] = (row - 1) * 8 + col;
    
54. 
    
55.     run(row, col, array);
    
56. 
    
57.     return 0;
    
58. }
    

复制代码

飞花落尽

1. step = [[-1,-2],[1,-2],[-2,-1],[2,-1],[-1,2],[-2,1],[1,2],[2,1]]
   
2. array = [[0 for j in range(8)] for i in range(8)]
   
3. 
   
4. def end(array):
   
5.     for i in range(8):
   
6.         for j in range(8):
   
7.             if (not array[i][j]):
   
8.                 return False
   
9.     return True
   
10. 
    
11. 
    
12. def run(row,col,array):
    
13.     print((row - 1) * 8 + col)
    
14.     if (end(array)):
    
15.         print("success")
    
16.         return True
    
17.     print(row)
    
18.     print(col)
    
19.     for i in range(8):
    
20.         if (row + step[i][0] >= 1 and col + step[i][1] >= 1 and row + step[i][0] <= 8 and col + step[i][0] <= 8 and not array[row + step[i][0] - 1][col + step[i][1] - 1]):
    
21.             array[row + step[i][0] - 1][col + step[i][1] - 1] = (row + step[i][0] - 1) * 8 + (col + step[i][1])
    
22.             run(row + step[i][0],col + step[i][1],array)
    
23.             print("\b\b\b   ")
    
24.             array[row + step[i][0] - 1][col + step[i][1] - 1] = 0
    
25.     return False
    
26. 
    
27. def main(row,col):
    
28.     array[row - 1][col - 1] = 18
    
29.     run(row,col,array)
    
30.     return True
    
31. 
    
32. if __name__ == "__main__":
    
33.     main(3,2)
    

复制代码

我试了下Python写，他说我列表越界了，有没有大佬帮帮忙

人造人

我先贴一下我的代码，等一下看你写的代码

1. #include <stdio.h>
   
2. #include <stdbool.h>
   
3. #include <time.h>
   
4. 
   
5. const int step[8][2] = {{-1, -2}, {1, -2}, {-2, -1}, {2, -1}, {-2, 1},  {2, 1},  {-1, 2},  {1, 2}};
   
6. size_t array[8][8];
   
7. 
   
8. bool verify(void) {
   
9.     for(size_t y = 0; y < 8; ++y) {
   
10.         for(size_t x = 0; x < 8; ++x) {
    
11.             if(!array[y][x]) return false;
    
12.         }
    
13.     }
    
14.     return true;
    
15. }
    
16. 
    
17. bool exist(size_t x, size_t y) {
    
18.     if(x >= 8) return false;
    
19.     if(y >= 8) return false;
    
20.     return true;
    
21. }
    
22. 
    
23. bool run(size_t x, size_t y, size_t count) {
    
24.     if(verify()) return true;
    
25.     if(!exist(x, y)) return false;
    
26.     if(array[y][x]) return false;
    
27.     bool flag = false;
    
28.     array[y][x] = count;
    
29.     for(size_t i = 0; i < 8; ++i) {
    
30.         size_t nx = x + step[i][0];
    
31.         size_t ny = y + step[i][1];
    
32.         if((flag = run(nx, ny, count + 1))) break;
    
33.     }
    
34.     if(!flag) array[y][x] = 0;
    
35.     return flag;
    
36. }
    
37. 
    
38. int main(void) {
    
39.     time_t begin = time(NULL);
    
40.     run(2, 0, 1);
    
41.     for(size_t y = 0; y < 8; ++y) {
    
42.         for(size_t x = 0; x < 8; ++x) {
    
43.             printf("%2lu ", array[y][x]);
    
44.         }
    
45.         puts("");
    
46.     }
    
47.     time_t end = time(NULL);
    
48.     printf("time: %lu\n", end - begin);
    
49.     return 0;
    
50. }
    

复制代码

1. $ gcc -O3 -o main main.c
   
2. $ ./main
   
3. 11  4  1 18  9  6 15 64
   
4. 2 19 10  5 14 17 24  7
   
5. 39 12  3 20 23  8 63 16
   
6. 30 21 38 13 28 25 46 61
   
7. 37 40 29 22 47 62 51 26
   
8. 34 31 36 55 52 27 60 45
   
9. 41 56 33 48 43 58 53 50
   
10. 32 35 42 57 54 49 44 59
    
11. time: 496
    
12. $

复制代码

O3 优化都 496 秒，^_^


对于我的这个代码，第一次选的是题目中的位置

1.     run(4, 3, 1);
   

复制代码

1. $ gcc -O3 -o main main.c
   
2. $ ./main
   
3. 6  3  8 11 14 17 20 23
   
4. 9 12  5  2 21 24 15 18
   
5. 4  7 10 13 16 19 22 25
   
6. 31 28 41 36  1 26 49 38
   
7. 42 35 30 27 40 37 60 47
   
8. 29 32 55 44 61 48 39 50
   
9. 54 43 34 57 52 63 46 59
   
10. 33 56 53 62 45 58 51 64
    
11. time: 22
    
12. $

复制代码

O3 优化，22 秒

这个使用时间的多少，和起点的选择有关
还和step数组中的元素排列顺序有关

想要得到一个用时最短的组合（起点和step数组中的元素排列顺序）
需要对每一个起点去尝试step数组的全排列，这需要相当长的时间
我就不找这个组合了

我试了一下答案，6秒

1. #include <stdio.h>
   
2. #include <time.h>
   
3. 
   
4. #define X 8
   
5. #define Y 8
   
6. 
   
7. int chess[X][Y];
   
8. 
   
9. // 找到下一个可走的位置
   
10. int next(int *px, int *py, int count)
    
11. {
    
12.         int x = *px;
    
13.         int y = *py;
    
14. 
    
15.         switch(count)
    
16.         {
    
17.         case 0:
    
18.                 if (x+2<=X-1 && y-1>=0 && chess[x+2][y-1] == 0)
    
19.                 {
    
20.                         *px = x + 2;
    
21.                         *py = y - 1;
    
22.                         return 1;
    
23.                 }
    
24.                 break;
    
25.         case 1:
    
26.                 if (x+2<=X-1 && y+1<=Y-1 && chess[x+2][y+1] == 0)
    
27.                 {
    
28.                         *px = x + 2;
    
29.                         *py = y + 1;
    
30.                         return 1;
    
31.                 }
    
32.                 break;
    
33.         case 2:
    
34.                 if (x+1<=X-1 && y-2>=0 && chess[x+1][y-2] == 0)
    
35.                 {
    
36.                         *px = x + 1;
    
37.                         *py = y - 2;
    
38.                         return 1;
    
39.                 }
    
40.                 break;
    
41.         case 3:
    
42.                 if (x+1<=X-1 && y+2<=Y-1 && chess[x+1][y+2] == 0)
    
43.                 {
    
44.                         *px = x + 1;
    
45.                         *py = y + 2;
    
46.                         return 1;
    
47.                 }
    
48.                 break;
    
49.         case 4:
    
50.                 if (x-2>=0 && y-1>=0 && chess[x-2][y-1] == 0)
    
51.                 {
    
52.                         *px = x - 2;
    
53.                         *py = y - 1;
    
54.                         return 1;
    
55.                 }
    
56.                 break;
    
57.         case 5:
    
58.                 if (x-2>=0 && y+1<=Y-1 && chess[x-2][y+1] == 0)
    
59.                 {
    
60.                         *px = x - 2;
    
61.                         *py = y + 1;
    
62.                         return 1;
    
63.                 }
    
64.                 break;
    
65.         case 6:
    
66.                 if (x-1>=0 && y-2>=0 && chess[x-1][y-2] == 0)
    
67.                 {
    
68.                         *px = x - 1;
    
69.                         *py = y - 2;
    
70.                         return 1;
    
71.                 }
    
72.                 break;
    
73.         case 7:
    
74.                 if (x-1>=0 && y+2<=Y-1 && chess[x-1][y+2] == 0)
    
75.                 {
    
76.                         *px = x - 1;
    
77.                         *py = y + 2;
    
78.                         return 1;
    
79.                 }
    
80.                 break;
    
81.         }
    
82. 
    
83.         return 0;
    
84. }
    
85. 
    
86. int setHorse(int x, int y, int tag)
    
87. {
    
88.         int x1 = x, y1 = y, flag = 0, count = 0;
    
89. 
    
90.         // tag记录轨迹
    
91.         chess[x][y] = tag;
    
92.         // 如果tag等于64退出程序
    
93.         if (tag == X*Y)
    
94.         {
    
95.                 return 1;
    
96.         }
    
97. 
    
98.         // 如果可以走，那么flag为1
    
99.         flag = next(&x1, &y1, count);
    
100.         // 否则尝试其他路径
     
101.         while (flag == 0 && count < 7)
     
102.         {
     
103.                 count += 1;
     
104.                 flag = next(&x1, &y1, count);
     
105.         }
     
106. 
     
107.         // 递归进入下一个坐标
     
108.         while (flag)
     
109.         {
     
110.                 // 返回1表示成功找到落脚点
     
111.                 if (setHorse(x1, y1, tag+1))
     
112.                 {
     
113.                         return 1;
     
114.                 }
     
115.                 // 否则从上一步重新尝试
     
116.                 x1 = x;
     
117.                 y1 = y;
     
118.                 count += 1;
     
119.                 flag = next(&x1, &y1, count);
     
120.                 while (flag == 0 && count < 7)
     
121.                 {
     
122.                         count += 1;
     
123.                         flag = next(&x1, &y1, count);
     
124.                 }
     
125.         }
     
126. 
     
127.         if (flag == 0)
     
128.         {
     
129.                 chess[x][y] = 0;
     
130.         }
     
131. 
     
132.         return 0;
     
133. }
     
134. 
     
135. int main(void)
     
136. {
     
137.     time_t begin = time(NULL);
     
138.         int i, j;
     
139. 
     
140.         for (i = 0; i < X; i++)
     
141.         {
     
142.                 for (j = 0; j < Y; j++)
     
143.                 {
     
144.                         chess[i][j] = 0;
     
145.                 }
     
146.         }
     
147. 
     
148.         // 讲道理，从 (2, 0) 坐标开始计算是比较容易出结果的
     
149.         // 如果你比较有耐心，或 CPU 特别强劲，可以尝试计算其它坐标
     
150.         if (setHorse(2, 0, 1))
     
151.         {
     
152.                 for (i = 0; i < X; i++)
     
153.                 {
     
154.                         for (j = 0; j < Y; j++)
     
155.                         {
     
156.                                 printf("%02d  ", chess[i][j]);
     
157.                         }
     
158.                         putchar('\n');
     
159.                 }
     
160.         }
     
161.         else
     
162.         {
     
163.                 printf("可惜无解！\n");
     
164.         }
     
165.     time_t end = time(NULL);
     
166.     printf("time: %lu\n", end - begin);
     
167. 
     
168.         return 0;
     
169. }
     

复制代码

1. $ gcc -O3 -o tmp tmp.c
   
2. $ ./tmp
   
3. 43  50  47  38  57  52  61  32
   
4. 48  37  44  51  46  33  58  53
   
5. 01  42  49  56  39  60  31  62
   
6. 36  15  40  45  34  29  54  59
   
7. 41  02  35  16  55  24  63  30
   
8. 14  05  12  09  22  19  28  25
   
9. 03  10  07  20  17  26  23  64
   
10. 06  13  04  11  08  21  18  27
    
11. time: 6
    
12. $

复制代码

人造人

1. #include <stdio.h>
   
2. #include <stdbool.h>
   
3. #include <time.h>
   
4. 
   
5. const int step[8][2] = {{2, -1}, {2, 1}, {1, -2}, {1, 2}, {-2, -1},  {-2, 1},  {-1, -2},  {-1, 2}};
   
6. size_t array[8][8];
   
7. 
   
8. bool verify(void) {
   
9.     for(size_t y = 0; y < 8; ++y) {
   
10.         for(size_t x = 0; x < 8; ++x) {
    
11.             if(!array[y][x]) return false;
    
12.         }
    
13.     }
    
14.     return true;
    
15. }
    
16. 
    
17. bool exist(size_t x, size_t y) {
    
18.     if(x >= 8) return false;
    
19.     if(y >= 8) return false;
    
20.     return true;
    
21. }
    
22. 
    
23. bool run(size_t x, size_t y, size_t count) {
    
24.     if(verify()) return true;
    
25.     if(!exist(x, y)) return false;
    
26.     if(array[y][x]) return false;
    
27.     bool flag = false;
    
28.     array[y][x] = count;
    
29.     for(size_t i = 0; i < 8; ++i) {
    
30.         size_t nx = x + step[i][0];
    
31.         size_t ny = y + step[i][1];
    
32.         if((flag = run(nx, ny, count + 1))) break;
    
33.     }
    
34.     if(!flag) array[y][x] = 0;
    
35.     return flag;
    
36. }
    
37. 
    
38. int main(void) {
    
39.     time_t begin = time(NULL);
    
40.     run(2, 0, 1);
    
41.     for(size_t y = 0; y < 8; ++y) {
    
42.         for(size_t x = 0; x < 8; ++x) {
    
43.             printf("%2lu ", array[y][x]);
    
44.         }
    
45.         puts("");
    
46.     }
    
47.     time_t end = time(NULL);
    
48.     printf("time: %lu\n", end - begin);
    
49.     return 0;
    
50. }
    

复制代码

1. $ gcc -O3 -o main main.c
   
2. $ ./main
   
3. 43 48  1 36 41 14  3  6
   
4. 50 37 42 15  2  5 10 13
   
5. 47 44 49 40 35 12  7  4
   
6. 38 51 56 45 16  9 20 11
   
7. 57 46 39 34 55 22 17  8
   
8. 52 33 60 29 24 19 26 21
   
9. 61 58 31 54 63 28 23 18
   
10. 32 53 62 59 30 25 64 27
    
11. time: 9

复制代码

接下来看你写的代码

人造人

作为练习，上面那个八皇后的问题，我也写了，有兴趣的话可以看一看

参考：https://www.jianshu.com/p/deb028537af2
基本思路是：
1.第一行先占一个皇后
2.第二行再占一个且不能与第一个皇后攻击
3.第三行再占一个
。。。。。

1. #include <stdio.h>
   
2. #include <stdbool.h>
   
3. 
   
4. bool array[8][8];
   
5. size_t count;
   
6. 
   
7. bool verify(size_t y, size_t x) {
   
8.     for(size_t cy = 0; cy < y; ++cy) {
   
9.         if(array[cy][x]) return false;
   
10.     }
    
11.     for(size_t cy = y - 1, cx = x - 1; cy < 8 && cx < 8; --cy, --cx) {
    
12.         if(array[cy][cx]) return false;
    
13.     }
    
14.     for(size_t cy = y - 1, cx = x + 1; cy < 8 && cx < 8; --cy, ++cx) {
    
15.         if(array[cy][cx]) return false;
    
16.     }
    
17.     return true;
    
18. }
    
19. 
    
20. void run(size_t y) {
    
21.     if(y >= 8) {
    
22.         printf("count: %lu\n", ++count);
    
23.         for(size_t y = 0; y < 8; ++y) {
    
24.             for(size_t x = 0; x < 8; ++x) {
    
25.                 printf("%u ", array[y][x]);
    
26.             }
    
27.             puts("");
    
28.         }
    
29.         return;
    
30.     }
    
31.     for(size_t x = 0; x < 8; ++x) {
    
32.         if(!verify(y, x)) continue;
    
33.         array[y][x] = true;
    
34.         run(y + 1);
    
35.         array[y][x] = false;
    
36.     }
    
37. }
    
38. 
    
39. int main(void) {
    
40.     run(0);
    
41.     return 0;
    
42. }
    

复制代码