Knight's Tour recursive method in Java, code execution is stuck on the 5th move (on a 25 square board)?

Question

Since the board is 5x5 there should be 25 moves. I used a print statement to verify that the recursive method only runs 5 times successfully. When it gets to the fifth move in the last row it doesn't keep going, even though there are 4 valid moves from that position. It's able to change direction horizontally after hitting the right-most column.

I'm not sure why it can't recover from reaching the bottom row.

public class KnightsTour {


public boolean isSafe(int[][] board, int y, int x) {
    if (y >= 0 && x >= 0 && y < board.length && x < board.length) {
        return true;
    }
    return false;
}

public boolean knightsTour(int[][] board, int y, int x, int move) {  

    if (board[y][x] != 0) {
        // already been here
        return false;
    }
    System.out.println("Move " + move + " happened!");
    board[y][x] = move;
    move++;

    if (move == (board.length * board.length)) {
        // board is full, you completed the tour, end game
        return true;
    }



    int[][] moves =
    {
        {1, 2},
        {1, -2},
        {-1, 2},
        {-1, -2},
        {2, 1},
        {2, -1},
        {-2, -1},
        {-2, 1}
    };

    for (int i = 0; i < moves.length; i++) {
        if (isSafe(board, y + moves[i][0], x + moves[i][1])) {
            return knightsTour(board, y + moves[i][0], x + moves[i][1], move);
        }           
    }

    // if the board isn't full and there are no valid moves you can make
    // from here then this is not a part of the valid solution
    board[y][x] = 0;
    return false;
}

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

    int[][] board = new int[5][5];
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board.length; j++) {
            board[i][j] = 0;
        }
    }

    tour.knightsTour(board, 0, 0, 1);

    // print board
    System.out.println("Board:");
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board.length; j++) {
            System.out.print(board[i][j] + "\t");
        }
        System.out.println("");
    }
}

}

Answer 1

I believe your problem lies in this section of code:

for (int i = 0; i < moves.length; i++) {
    if (isSafe(board, y + moves[i][0], x + moves[i][1])) {
        return knightsTour(board, y + moves[i][0], x + moves[i][1], move);
    }           
}

For the first 'isSafe' move, you send the knight there, and if it has already been, you will fully return out false from the Tour. You should either modify this section to continue checking the moves if the tour fails, or modify your 'isSafe' method to say that board positions of non-zero are not actually safe.