Java 中的 Knight's Tour 递归方法，代码执行卡在第 5 步（在 25 平方的棋盘上）？

Question

由于棋盘是 5x5，所以应该有 25 步。我使用打印语句来验证递归方法只成功运行了 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' 移动，您将骑士送到那里，如果已经到达，您将完全 return 从巡回赛中出局。如果游览失败，您应该修改此部分以继续检查移动，或者修改您的 'isSafe' 方法以说明非零的棋盘位置实际上并不安全。

Java 中的 Knight's Tour 递归方法，代码执行卡在第 5 步（在 25 平方的棋盘上）？

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

java

knights-tour