Knight’s Tour возвращается назад бесконечный цикл

Я пытаюсь написать код для рыцарский тур:

Тур коня — это последовательность ходов коня на шахматной доске, так что рыцарь посещает каждый квадрат ровно один раз.

Я пытался изменить чей-то код, но откат, кажется, не работает должным образом — он никогда не находит решения. Он отлично работает, когда конь начинается с 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;
}