我想测试一下我是否了解回溯，所以尝试了“骑士问题”。但是我的代码似乎不起作用。它似乎发生了无限循环，因此也许我对路径的跟踪没有很好地执行。所以我想知道我对这个问题的理解。
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define N 8
int board[8][8]= {
-1,-1,-1,-1,-1,-1,-1,-1, //1
-1,-1,-1,-1,-1,-1,-1,-1, //2
-1,-1,-1,-1,-1,-1,-1,-1, //3
-1,-1,-1,-1,-1,-1,-1,-1, //4
-1,-1,-1,-1,-1,-1,-1,-1, //5
-1,-1,-1,-1,-1,-1,-1,-1, //6
-1,-1,-1,-1,-1,-1,-1,-1, //7
-1,-1,-1,-1,-1,-1,-1,-1, //8
};
bool isSafe(int x, int y)
{
return ( x >= 0 && x < N && y >= 0 &&
y < N && board[x][y] == -1);
}
int SolveKnight_From_One_Point (int x,int y , int number_Moov) {
if (number_Moov == N*N)
return 1;
if (isSafe(x,y)){
board[x][y] = number_Moov;
if (SolveKnight_From_One_Point(x-2,y+1,number_Moov+1)==1) {
return 1;
}
if (SolveKnight_From_One_Point(x-2,y-1,number_Moov+1)==1) {
return 1;
}
if (SolveKnight_From_One_Point(x-1,y+2,number_Moov+1)==1) {
return 1;
}
if (SolveKnight_From_One_Point(x-1,y-2,number_Moov+1)==1) {
return 1;
}
if (SolveKnight_From_One_Point(x+2,y-1,number_Moov+1)==1) {
return 1;
}
if (SolveKnight_From_One_Point(x+2,y+1,number_Moov+1)==1) {
return 1;
}
if (SolveKnight_From_One_Point(x+1,y+2,number_Moov+1)==1) {
return 1;
}
if (SolveKnight_From_One_Point(x+1,y-2,number_Moov+1)==1) {
return 1;
}
board[x][y] = -1;
}
return 0;
}
int main (){
if (SolveKnight_From_One_Point(0,0,0)==1){
printf(" Solution found :)\n");
}
printf("No solution :(\n");
return 0;
}
最佳答案
对我来说，您的程序可以运行，但是需要很长时间才能找到解决方案。
请注意两点：
最好像这样初始化数组：
int board[8][8]= {
{ -1,-1,-1,-1,-1,-1,-1,-1}, //1
{ -1,-1,-1,-1,-1,-1,-1,-1}, //2
{ -1,-1,-1,-1,-1,-1,-1,-1}, //3
{ -1,-1,-1,-1,-1,-1,-1,-1}, //4
{ -1,-1,-1,-1,-1,-1,-1,-1}, //5
{ -1,-1,-1,-1,-1,-1,-1,-1}, //6
{ -1,-1,-1,-1,-1,-1,-1,-1}, //7
{ -1,-1,-1,-1,-1,-1,-1,-1} //8
};
并更换
if (SolveKnight_From_One_Point(0,0,0)==1){
printf(" Solution found :)\n");
}
printf("No solution :(\n");
通过
if (SolveKnight_From_One_Point(0,0,0)==1){
printf(" Solution found :)\n");
}
else {
printf("No solution :(\n");
}
不总是说没有解决办法
有一种启发式方法可以解决问题Warnsdorf's rule in Wikipedia：骑士移动了，因此它总是前进到骑士前进最少的位置。在计算每个候选方格的前进次数时，我们不计算重新访问任何已访问过的方格的次数。当然，可以有两个或更多个选择，使前进的次数相等
在回答的最后，我使用启发式方法提出了一个建议
稍作更改即可查看搜索进度：
int SolveKnight_From_One_Point (int x,int y , int number_Moov) {
static int max = 0;
if (number_Moov > max) {
int a,b;
printf("%d moves\n", number_Moov);
max = number_Moov;
for (a = 0; a != N; ++a) {
for (b = 0; b != N; ++b) {
printf("%02d ", board[a][b]);
}
putchar('\n');
}
putchar('\n');
}
if (number_Moov == N*N)
return 1;
...
如果我将N更改为5，则立即找到解决方案：
1 moves
00 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
2 moves
00 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 01 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
3 moves
00 -1 02 -1 -1
-1 -1 -1 -1 -1
-1 01 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
4 moves
00 -1 02 -1 -1
-1 -1 -1 -1 -1
-1 01 -1 03 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
5 moves
00 -1 02 -1 04
-1 -1 -1 -1 -1
-1 01 -1 03 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
6 moves
00 -1 02 -1 04
-1 -1 05 -1 -1
-1 01 -1 03 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
7 moves
00 -1 02 -1 04
-1 -1 05 -1 -1
-1 01 -1 03 -1
-1 06 -1 -1 -1
-1 -1 -1 -1 -1
8 moves
00 -1 02 -1 04
07 -1 05 -1 -1
-1 01 -1 03 -1
-1 06 -1 -1 -1
-1 -1 -1 -1 -1
9 moves
00 -1 02 -1 04
07 -1 05 -1 -1
-1 01 08 03 -1
-1 06 -1 -1 -1
-1 -1 -1 -1 -1
10 moves
00 -1 02 09 04
07 -1 05 -1 -1
-1 01 08 03 -1
-1 06 -1 -1 -1
-1 -1 -1 -1 -1
11 moves
00 -1 02 09 04
07 -1 05 -1 -1
-1 01 08 03 10
-1 06 -1 -1 -1
-1 -1 -1 -1 -1
12 moves
00 -1 02 09 04
07 -1 05 -1 -1
-1 01 08 03 10
-1 06 -1 -1 -1
-1 -1 -1 11 -1
13 moves
00 -1 02 09 04
07 -1 05 12 -1
-1 01 08 03 10
-1 06 11 -1 -1
-1 -1 -1 -1 -1
14 moves
00 13 02 09 04
07 -1 05 12 -1
-1 01 08 03 10
-1 06 11 -1 -1
-1 -1 -1 -1 -1
15 moves
00 13 02 09 04
07 -1 05 12 -1
14 01 08 03 10
-1 06 11 -1 -1
-1 -1 -1 -1 -1
16 moves
00 13 02 09 04
07 -1 05 12 -1
14 01 08 03 10
-1 06 11 -1 -1
-1 15 -1 -1 -1
17 moves
00 13 02 09 04
07 -1 05 12 -1
14 01 08 03 10
-1 06 11 16 -1
-1 15 -1 -1 -1
18 moves
00 13 02 09 04
07 -1 05 12 17
14 01 08 03 10
-1 06 11 16 -1
-1 15 -1 -1 -1
19 moves
00 17 02 09 04
07 12 05 16 -1
18 01 08 03 10
13 06 11 -1 15
-1 -1 14 -1 -1
20 moves
00 17 02 09 04
07 12 05 16 -1
18 01 08 03 10
13 06 11 -1 15
-1 19 14 -1 -1
21 moves
00 17 02 09 04
07 12 05 16 -1
18 01 08 03 10
13 06 11 20 15
-1 19 14 -1 -1
22 moves
00 17 02 09 04
07 12 05 16 21
18 01 08 03 10
13 06 11 20 15
-1 19 14 -1 -1
23 moves
00 13 02 19 04
07 18 05 14 09
12 01 08 03 20
17 06 21 10 15
-1 11 16 -1 22
24 moves
00 11 02 19 06
15 20 05 10 03
12 01 14 07 18
21 16 09 04 23
-1 13 22 17 08
25 moves
00 17 02 11 20
07 12 19 16 03
18 01 06 21 10
13 08 23 04 15
24 05 14 09 22
Solution found :)
在N向后8的情况下，立即执行前60个动作，然后它就会越来越长
1 movs
00 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
2 movs
00 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 01 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
3 movs
00 -1 02 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 01 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
4 movs
00 -1 02 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 01 -1 03 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
5 movs
00 -1 02 -1 04 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 01 -1 03 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
6 movs
00 -1 02 -1 04 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 01 -1 03 -1 05 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
7 movs
00 -1 02 -1 04 -1 06 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 01 -1 03 -1 05 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
8 movs
00 -1 02 -1 04 -1 06 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 01 -1 03 -1 05 -1 07
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
9 movs
00 -1 02 -1 04 -1 06 -1
-1 -1 -1 -1 -1 08 -1 -1
-1 01 -1 03 -1 05 -1 07
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
10 movs
00 -1 02 -1 04 -1 06 09
-1 -1 -1 -1 -1 08 -1 -1
-1 01 -1 03 -1 05 -1 07
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
...
60 movs
00 15 02 13 04 11 06 09
-1 24 17 22 -1 08 29 -1
16 01 14 03 12 05 10 07
25 18 23 38 21 28 33 30
46 55 20 27 32 37 40 35
19 26 45 56 39 34 31 50
54 47 58 43 52 49 36 41
59 44 53 48 57 42 51 -1
61 movs
00 15 02 13 04 11 06 09
-1 24 17 22 31 08 33 60
16 01 14 03 12 05 10 07
25 18 23 30 21 32 59 34
52 29 20 27 58 45 38 41
19 26 51 44 55 40 35 46
50 53 28 57 48 37 42 39
-1 -1 49 54 43 56 47 36
62 movs
00 15 02 13 04 11 06 09
-1 24 17 22 33 08 31 -1
16 01 14 03 12 05 10 07
25 18 23 34 21 32 49 30
44 59 20 27 48 29 36 53
19 26 45 56 35 52 39 50
58 43 60 47 28 41 54 37
61 46 57 42 55 38 51 40
63 movs
00 15 02 13 04 11 06 09
-1 24 17 22 35 08 33 62
16 01 14 03 12 05 10 07
25 18 23 36 21 34 61 32
56 37 20 29 60 31 52 43
19 26 57 40 53 44 49 46
38 55 28 59 30 47 42 51
27 58 39 54 41 50 45 48
（6小时后计算未完成）
使用Warnsdorf的启发式方法对程序进行修改：
#include <stdio.h>
#define N 8
int Board[8][8]= {
{ -1,-1,-1,-1,-1,-1,-1,-1}, //1
{ -1,-1,-1,-1,-1,-1,-1,-1}, //2
{ -1,-1,-1,-1,-1,-1,-1,-1}, //3
{ -1,-1,-1,-1,-1,-1,-1,-1}, //4
{ -1,-1,-1,-1,-1,-1,-1,-1}, //5
{ -1,-1,-1,-1,-1,-1,-1,-1}, //6
{ -1,-1,-1,-1,-1,-1,-1,-1}, //7
{ -1,-1,-1,-1,-1,-1,-1,-1} //8
};
typedef struct DxDy {
int dx;
int dy;
} DxDy;
#define NDEPLS 8
const DxDy Depls[NDEPLS] = { {-2,1}, {-2,-1}, {-1,2}, {-1,-2}, {2,-1}, {2,1}, {1,2} , {1,-2} };
int isSafe(int x, int y)
{
return ((x >= 0) && (x < N) &&
(y >= 0) && (y < N) &&
(Board[x][y] == -1));
}
int nchoices(int x, int y)
{
int r = 0;
int i;
for (i = 0; i != NDEPLS; ++i) {
if (isSafe(x + Depls[i].dx, y + Depls[i].dy))
r += 1;
}
return r;
}
void pr()
{
int a, b, c;
for (a = 0; a != N; ++a) {
for (c = 0; c != 2; c++) {
for (b = 0; b != N; ++b)
printf(((a ^ b) & 1) ? "********" : " ");
putchar('\n');
}
for (b = 0; b != N; ++b)
printf(((a ^ b) & 1) ? "***%2d***" : " %2d ", Board[a][b]);
putchar('\n');
for (c = 0; c != 2; c++) {
for (b = 0; b != N; ++b)
printf(((a ^ b) & 1) ? "********" : " ");
putchar('\n');
}
}
putchar('\n');
}
int SolveKnight_From_One_Point(int x, int y , int number_Moov)
{
Board[x][y] = number_Moov;
number_Moov += 1;
int i, fx[NDEPLS], fy[NDEPLS], mins[NDEPLS];
int imin = 0;
int min = NDEPLS+1;
for (i = 0; i != NDEPLS; ++i) {
int nx = x + Depls[i].dx;
int ny = y + Depls[i].dy;
if (isSafe(nx, ny)) {
Board[nx][ny] = number_Moov;
if (number_Moov == (N*N - 1)) {
puts("Done");
pr();
return 1;
}
int n = nchoices(nx, ny);
if ((n != 0) && (n < min)) {
mins[imin] = min = n;
fx[imin] = nx;
fy[imin] = ny;
imin += 1;
}
Board[nx][ny] = -1;
}
}
while (imin-- != 0) {
if ((mins[imin] == min) &&
SolveKnight_From_One_Point(fx[imin], fy[imin], number_Moov))
return 1;
}
Board[x][y] = -1;
return 0;
}
int main ()
{
if (SolveKnight_From_One_Point(0, 0, 0))
printf("Solution found :)\n");
else
printf("No solution :(\n");
return 0;
}
那个时候立即找到解决方案：
pi@raspberrypi:~ $ ./a.out
Done
******** ******** ******** ********
******** ******** ******** ********
0 ***21*** 2 ***17*** 24 ***29*** 12 ***15***
******** ******** ******** ********
******** ******** ******** ********
******** ******** ******** ********
******** ******** ******** ********
*** 3*** 18 ***23*** 28 ***13*** 16 ***33*** 30
******** ******** ******** ********
******** ******** ******** ********
******** ******** ******** ********
******** ******** ******** ********
22 *** 1*** 20 ***25*** 48 ***31*** 14 ***11***
******** ******** ******** ********
******** ******** ******** ********
******** ******** ******** ********
******** ******** ******** ********
***19*** 4 ***55*** 38 ***27*** 34 ***49*** 32
******** ******** ******** ********
******** ******** ******** ********
******** ******** ******** ********
******** ******** ******** ********
56 ***39*** 26 ***47*** 60 ***53*** 10 ***35***
******** ******** ******** ********
******** ******** ******** ********
******** ******** ******** ********
******** ******** ******** ********
*** 5*** 42 ***59*** 54 ***37*** 46 ***63*** 50
******** ******** ******** ********
******** ******** ******** ********
******** ******** ******** ********
******** ******** ******** ********
40 ***57*** 44 *** 7*** 52 ***61*** 36 *** 9***
******** ******** ******** ********
******** ******** ******** ********
******** ******** ******** ********
******** ******** ******** ********
***43*** 6 ***41*** 58 ***45*** 8 ***51*** 62
******** ******** ******** ********
******** ******** ******** ********
Solution found :)
关于c - 骑士之旅无限循环，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/54591797/