2

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;
}
}
false
  • 10,264
  • 13
  • 101
  • 209
  • You might as well fix `pole` -> `board` and `places`/`spaces`. – Sergey Kalinichenko Dec 26 '13 at 11:32
  • One thing you can do is count the number of times the ride() is called for each board size, 4, 5, 6, 7 and look at the growth of it.. That might give you a rough idea of the time complexity of depth-first search vs board size.. Considering the size of the state space you have to search, it is no wonder that it takes so long to finish... – Buddhima Gamlath Dec 26 '13 at 12:02
  • Does this answer your question? [Knight's tour backtrack implementation choosing the step array](https://stackoverflow.com/questions/21511683/knights-tour-backtrack-implementation-choosing-the-step-array) – tkruse Apr 07 '20 at 05:36

1 Answers1

2

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.

Skandh Pathak
  • 21
  • 3
  • Surprisingly this solution works(for n = 7, 8 and 9) as the author describes. Can anybody shed any light on why it happens? branch prediction? – Quazi Irfan May 07 '18 at 09:51