Я пытаюсь написать код для рыцарский тур:
Тур коня — это последовательность ходов коня на шахматной доске, так что рыцарь посещает каждый квадрат ровно один раз.
Я пытался изменить чей-то код, но откат, кажется, не работает должным образом — он никогда не находит решения. Он отлично работает, когда конь начинается с 0, 0, но если он начинается в любой другой точке 2D-сетки, программа продолжается вечно.
Где ошибка в этом коде?
#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;
}
Эта программа кажется абсолютно правильной, я не вижу ошибки в этом коде.
Тем не менее, рыцарский тур — очень сложный алгоритм. На самом деле, программе необходимо проверить до 64! = 1 * 2 * 3 * … * 64 различных способов через плату. Это число с 89 нулями!
Во многих случаях обратное отслеживание останавливается на ранней ветви, но некоторые ветви будут расти вечно.
Если тур, начинающийся с 0,0, выполняется так быстро, то это может быть либо просто случайность, либо массивы xMove и yMove были умно инициализированы, так что решение для (0,0) было найдено быстро.
Так что проблема не в вашей программе, а в алгоритме. Я предлагаю вам сделать некоторые исследования по этой теме. Есть много алгоритмов для рыцарского тура, которые дадут вам решение в более разумное время.
У меня недостаточно репутации, чтобы комментировать, но это больше похоже на комментарий. Проверьте Вот для реализации Python Правило Варнсдорфа. Дальнейшая оптимизация по правилу Варнсдорфа обсуждается Вот