骑士之旅无限循环 [英] Knight's Tour Infinite loop
本文介绍了骑士之旅无限循环的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我想测试我是否了解回溯，所以尝试了骑士问题".但是我的代码似乎不起作用.它似乎发生了无限循环，因此也许我对路径的跟踪没有很好地执行.所以我想知道我对这个问题的理解.
I wanted to test if I understand well the backtracking, so I tried the Knight Problem. But my code doesn't seem to work. It seem to do an infinite loop, so maybe my tracking of the path is not well executed. So I wanted to know what I miss in my comprehension of the problem.
#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;
}
推荐答案
对我来说，您的程序可以运行，但是需要很长时间才能找到解决方案.
For me your program works but need a very long time to find a solution.
只有两句话:
最好像这样初始化数组:
It is better to initialize your array like that :
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");
}
并非总是说没有解决办法
有一种启发式方法可以解决问题维基百科中的瓦尔斯多夫规则:移动骑士，使其始终前进到骑士前进最少的正方形.在计算每个候选方格的向前移动次数时，我们不计算重新访问任何已访问过的方格的移动.当然，可以有两个或更多个选择，使前进的次数相等.
There is an heuristic to solve the problem Warnsdorf's rule in Wikipedia : The knight is moved so that it always proceeds to the square from which the knight will have the fewest onward moves. When calculating the number of onward moves for each candidate square, we do not count moves that revisit any square already visited. It is, of course, possible to have two or more choices for which the number of onward moves is equal
在回答的最后，我使用启发式方法给出了一个建议
稍作更改即可查看搜索进度:
A little change to see the progress in the search :
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，则会立即找到解决方案:
If I change N to be 5 the solution is found immediately :
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步动作，然后它就会越来越长
With N back 8 it is immediate to do the first 60 moves, then it is more and more longer
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小时后计算未完成)
(computing not finished after 6 hours)
使用Warnsdorf的启发式方法修改程序:
A modification of your program using the heuristic of 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;
}
那个时候立即找到解决方案:
That time a solution is found immediately :
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 :)
这篇关于骑士之旅无限循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
