Knights tour backtracking Java

Question

I am trying to solve the Knights tour problem on a 4x4 board with backtracking and recursion in java, and on the output I get this step sequence:

1  13   16  15
10  7   4   14
5    2   11   8
12  9   6   3

in the right upper corner, the 14, 15 and 16 neighbour with each other, which is impossible, because the knight moves on the chessboard into an L-shape. I would be thankful if someone could help me solve this.

the code:

public class KnightsTour {

private static int board[][] = new int[4][4];
private static int stepCounter = 1;

public Test() {
    initBoard(board);
    tour(0,0);
    printSol(board);

}

  public static void printSol(int[][] a) {
    for (int i = 0; i < a.length; i++) {
        for (int j = 0; j < a[i].length; j++) {
            if(a[i][j]>9){
                System.out.print(a[i][j] + "  ");
            }else{
                System.out.print(a[i][j] + "   ");
            }
        }
        System.out.println();
    }
    System.out.println();
}


public static void initBoard(int[][] a) {
    for (int i = 0; i < a.length; i++) {
        for (int j = 0; j < a[i].length; j++) {
            a[i][j] = -1;
        }
    }
}


public void tour(int x, int y) {


    if (((x < 0) || (x >= 4) || (y < 0) || (y >= 4)) || (board[x][y] != -1)) {
        return;
    }else{
        board[x][y] = stepCounter++;
        tour(x+2, y+1);
        tour(x+1, y-2);
        tour(x+1, y+2);
        tour(x-1, y+2);
        tour(x-2, y-1);
        tour(x-2, y+1);
        tour(x-1, y-2);
        tour(x+2, y-1);  
    }
}




public static void main(String[] args){
    new KnightsTour();
}
}

Answer 1

Your tour() function appears to set the value of a square to the step-counter of the order it's visited for the first time. But you're trying multiple options. Your first tour dead ends when you get to 12 - one of the subsequent attempts touches each of the 13-16 squares.

You need to store the state of the current tour, rather than the order in which you visited. E.g. if you backtrack, the current square is no longer part of the tour. If you find a tour, you should stop, because you're done.

Answer 2

• You need to make the function return a boolean so it can tell the calling function whether or not it succeeded. Otherwise you just carry on until you've tried every possible combination, even after you've found a solution.

  Then, at each call of the function, you need to check the return value and return true if it succeeded.

  Then you also obviously need to return true when done.

  I suggest something like:

  if (stepCounter == 1 + board.length * board[0].length)
    return true;
  

  Right after board[x][y] = stepCounter++;.

• You need to revert any changes made at the end of the function call, i.e. stepCounter needs to decrease and board[x][y] needs to be set to -1.

After you've successfully made these changes, you should actually see a result of all -1's, because it's not possible on a 4x4 board, but changing it to 8x8 should succeed.

Note that I didn't use 17 above - it's good practice to not use hard-coded values (in, for example, x >= 4). Use either the size of the array, or final values, instead.