Рекурсивный метод Knight's Tour в Java, выполнение кода застревает на 5-м ходу (на доске с 25 квадратами)?

Question

Поскольку на доске 5х5, должно быть 25 ходов.Я использовал оператор print, чтобы убедиться, что рекурсивный метод успешно выполняется только 5 раз.Когда он доходит до пятого хода в последнем ряду, он не продолжает движение, даже если из этой позиции есть 4 действительных хода.Он может изменить направление по горизонтали после нажатия на самый правый столбец.

Я не уверен, почему он не может восстановиться после достижения нижней строки.

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

Я полагаю, что ваша проблема заключается в этом разделе кода:

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

Для первого хода 'isSafe' вы отправляете коня туда, и если он уже был, вы полностью вернете ложьиз тура.Вам следует либо изменить этот раздел, чтобы продолжить проверку ходов в случае неудачи тура, либо изменить свой метод «isSafe», указав, что ненулевые позиции на доске не являются безопасными.