问题描述
我想写$ C $下骑士旅行的：
我一直在试图改变别人的code，但回溯似乎无法正常工作 - 它从来没有找到解决方案。这工作完全正常时，骑士开始于0，0，但如果它开始于在2D网格中的任何其他地方，该计划继续下去。
在哪里是这个code中的错误？
的#include＆LT;的iostream＆GT;
＃包括＆LT;的ctime＆GT;
使用名字空间std;
const int的N = 8;
INT地图[N] [N];
/ *一个效用函数，以检查是否I，J是对于N * N的棋盘有效的索引* /
布尔isSafe（INT X，int y）对{
返回X＆GT; = 0＆安培;＆安培; X - LT; N'放大器;＆安培; Ÿ＆GT; = 0＆功放;＆安培; Y'LT; N'放大器;＆安培;图[X] [Y] == -1;
}
/ *一个效用函数打印解决方案的矩阵溶胶[N] [N] * /
无效printSolution（）{
为（中间体X = 0 X - 其中N; X ++）{
为（中间体y = 0的; Y＆所述; N; Y ++）
COUT＆LT;＆LT;地图[X] [Y]
COUT＆LT;＆LT; ENDL;
}
}
/ *递归效用函数来解决骑士之旅的问题* /
布尔knightsTourRecursive（INT X，INT Y，INT movei，INT XMOVE [N]，int的yMove偏移[N]）{
INT nextX，nextY;
如果（movei == N * N）
返回true;
/ *尝试从目前所有的下一步行动的坐标X，Y * /
对于（INT K = 0; K＆LT; 8; k ++）{
nextX = X + XMOVE [k]的;
nextY = Y + yMove偏移[K]
如果（isSafe（nextX，nextY））{
图[nextX] [nextY] = movei;
如果（knightsTourRecursive（nextX，nextY，movei + 1，XMOVE，yMove偏移））//递归
返回true;
其他
映射[nextX] [nextY] = -1; //回溯
}
}
返回false;
}
布尔knightsTour（）{
/ *解矩阵的初始化* /
为（中间体X = 0 X - 其中N; X ++）
为（中间体y = 0的; Y＆所述; N; Y ++）
地图[X] [Y] = -1;
/ * XMOVE []和yMove偏移[]定义骑士的下一步行动。
XMOVE []是x的下一个坐标值
yMove偏移[]是Y的下一个坐标值* /
INT XMOVE [8] = {2,1，-1，-2，-2，-1，1,2};
INT yMove偏移[8] = {1，2，2，1，-1，-2，-2，-1};
INT INITX =兰特（）％N;
INT inity这=兰特（）％N;
COUT＆LT;＆LT; 起价＆LT;＆LT; INITX＆LT;＆LT; ＆LT;＆LT; inity这与LT;＆LT; ENDL;
//由于奈特最初处于第一块
映射[INITX] [inity这] = 0;
/ *使用solveKTUtil（）浏览所有旅游* /
如果（！knightsTourRecursive（INITX，inity这1，XMOVE，yMove偏移））{
COUT＆LT;＆LT; 解决方案不存在＆LT;＆LT; ENDL;
返回false;
}
其他
printSolution（）;
返回true;
}
诠释的main（）{
函数srand（（符号）时间（0））;
knightsTour（）;
cin.get（）;
返回0;
}
该方案似乎是绝对正确的，我看不到在这code的错误。
不过，骑士的旅游是一个非常复杂的算法。事实上，该方案需要检查多达64个！= 1 * 2 * 3 * ...... *通过板64不同的方式。这是一个数字89零！
在许多情况下，回溯会停止在早期的分支，但有些分行会一直涨下去。
如果开始0,0的巡演foudn这么快，那么它可能要么是纯属偶然，还是阵列XMOVE和yMove偏移被巧妙地初始化，使得对（0,0）很快就找到了解决方案。
所以，问题不在于你的程序，但它的算法。我建议你做一些研究关于这一主题。有很多种算法，骑士的巡演，这将给你更多的时间合理的解决方案。
I'm trying to write code for the Knight's Tour:
I've been trying to alter someone else's code, but the backtracking seems to not work properly - it never finds the solution. It works perfectly fine when the knight starts at 0, 0 but if it starts at any other spot on the 2D grid, the program goes on forever.
Where is the bug in this code?
#include <iostream>
#include <ctime>
using namespace std;
const int N = 8;
int map[N][N];
/* A utility function to check if i,j are valid indexes for N*N chessboard */
bool isSafe(int x, int y) {
return x >= 0 && x < N && y >= 0 && y < N && map[x][y] == -1;
}
/* A utility function to print solution matrix sol[N][N] */
void printSolution() {
for (int x = 0; x < N; x++) {
for (int y = 0; y < N; y++)
cout << map[x][y];
cout << endl;
}
}
/* A recursive utility function to solve Knight Tour problem */
bool knightsTourRecursive(int x, int y, int movei, int xMove[N], int yMove[N]) {
int nextX, nextY;
if (movei == N*N)
return true;
/* Try all next moves from the current coordinate x, y */
for (int k = 0; k < 8; k++) {
nextX = x + xMove[k];
nextY = y + yMove[k];
if (isSafe(nextX, nextY)) {
map[nextX][nextY] = movei;
if (knightsTourRecursive(nextX, nextY, movei+1, xMove, yMove)) // recursion
return true;
else
map[nextX][nextY] = -1; // backtracking
}
}
return false;
}
bool knightsTour() {
/* Initialization of solution matrix */
for (int x = 0; x < N; x++)
for (int y = 0; y < N; y++)
map[x][y] = -1;
/* xMove[] and yMove[] define next move of Knight.
xMove[] is for next value of x coordinate
yMove[] is for next value of y coordinate */
int xMove[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int yMove[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
int initX = rand() % N;
int initY = rand() % N;
cout << "Starting at " << initX << " " << initY << endl;
// Since the Knight is initially at the first block
map[initX][initY] = 0;
/* explore all tours using solveKTUtil() */
if(!knightsTourRecursive(initX, initY, 1, xMove, yMove) ) {
cout << "Solution does not exist" << endl;
return false;
}
else
printSolution();
return true;
}
int main() {
srand( (unsigned) time(0));
knightsTour();
cin.get();
return 0;
}
This program seems to be absolutely correct, I cannot see a bug in this code.
However, the knight's tour IS a highly complex algorithm. Actually, the program needs to check up to 64!=1*2*3*...*64 different ways through the board. This is a number with 89 zeroes!
In many cases the backtracking will stop at an early branch, but some branches will go up forever.
If the tour starting at 0,0 is foudn so quickly, then it might either be pure chance, or the arrays xMove and yMove were cleverly initialized, such that a solution for (0,0) is found quickly.
So the problem is not your program, but it is the algorithm. I suggest you to do some research on this topic. There are many algorithms for the knight's tour which will give you a solution in more reasonable time.
这篇关于骑士之旅回溯无限循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！