Knights tour backtracking lasts too long

Question

How long does it last to solve the knights tour problem with backtracking on an 8x8 board? Because my algorithm already computes somehow too long and it seems, like it wont finish. But when I try a 6x6, or 5x5 board, it finishes successfully.

the code:

class KnightsTour{

private boolean[][] board;
private int count, places;
private static final Point[] moves = new Point[]{
    new Point(-2, -1),
    new Point(-2, 1),
    new Point(2, -1),
    new Point(2, 1),
    new Point(-1, -2),
    new Point(-1, 2),
    new Point(1, -2),
    new Point(1, 2)
};

public KnightsTour(int n) {
    board = new boolean[n][n];
    places = n*n;
    count = 0;
     }

public boolean ride(int x, int y) {
    
    
    board[x][y] = true;
    count++;
    
    if (count == places) {
        return true;
    }

    for (Point p : moves) {
        int nextX = x + p.x;
        int nextY = y + p.y;

        if (nextX < 0 || nextX >= board.length || nextY < 0 || nextY >= board.length || board[nextX][nextY]) {
            continue;
        } 
        if (ride(nextX, nextY)) {
            return true;
        }
    }
    
    board[x][y] = false;
    count--;
    
    return false;
}
}

Answer 1

I came across the same problem. Everything runs smoothly till n=7 and suddenly it takes forever to calculate for n=8. I hope this helps someone :)

The problem lies with the order in which you are checking for the moves. You are using :

xMove[8] = { -2, -2, 2, 2, -1, -1, 1, 1}

yMove[8] = { -1, 1, -1, 1, -2, 2, -2, 2}

If you plot these vectors in the 2D plane, they are haphazardly placed. In other words, they are not ordered in either a clockwise or an anti-clockwise manner. Consider this instead :

xMove[8] = { 2, 1, -1, -2, -2, -1, 1, 2 }

yMove[8] = { 1, 2, 2, 1, -1, -2, -2, -1 }

If you plot these vectors, they are neatly arranged in an anticlockwise circle. Somehow this causes the recursion to run much quickly for large values of n. Mind you, it still takes forever to calculate for n=9 onwards.