Knight's Tour backtracking infinite loop

Question

I'm trying to write code for the Knight's Tour:

A knight's tour is a sequence of moves of a knight on a chessboard such that the knight visits every square exactly once.

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;
}

Poignant

Are you sure it is actually going on forever? It just might be very very very slow. BTW, logically, the size of the xMove and yMove parameters in the declaration of knightsTourRecursive is 8 and not N (that is, the number of moves a knight can make, not the size of the board.) – Ernesternesta

Yes that's right, you should change the parameter to xMove[8] and yMove[8]. The knight can do 8 possible moves, this is independent of the board size. In the current code, if you would change the board size to a smaller Board (e.g. N=4), then the knight could not perform all possible moves and you will never get a result. – Phytogeography

Answer 1

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.

Phytogeography

thanks! Could you suggest a better solution for Knight's tour? – Poignant

Use this heuristic: choose the move that results in the least number of choices (Warnsdorff's Rule). – Bishopric

Answer 2

I don't have enough reputation to comment, but this is more like a comment. Check here for a python implementation of Warnsdorff's Rule. Further optimizations over Warnsdorff's Rule is discussed here

Myna