Java递归实现Knight's Tour在5×5棋盘第5步卡住问题咨询

我一眼就看出你的代码卡壳的核心问题——递归遍历方向的逻辑写得太急躁了！在knightsTour的for循环里，你一找到第一个合法的移动位置就直接return递归结果，这相当于程序只敢走第一条看起来可行的路，完全不给自己留“回头换路”的机会。

举个具体的例子：当第5步走到最后一行时，明明有4个合法方向，但你的代码只会试第一个方向。如果这个方向是死胡同，程序直接就把当前位置重置回0并返回false，根本没机会尝试剩下的7个方向，自然就卡在这儿了。

修复后的完整代码 #

把for循环里的逻辑调整一下：不要急着return，先尝试这个方向，如果走通了再返回true；走不通就继续试下一个方向，直到所有方向都试过才回溯。另外我还顺手优化了几个小细节：

public class KnightsTour {
    public boolean isSafe(int[][] board, int y, int x) {
        // 把"未被访问"的判断直接整合到这里，避免重复检查
        if (y >= 0 && x >= 0 && y < board.length && x < board.length && board[y][x] == 0) {
            return true;
        }
        return false;
    }

    public boolean knightsTour(int[][] board, int y, int x, int move) {
        System.out.println("Move " + move + " happened!");
        board[y][x] = move;
        move++;

        // 修正终止条件：move从1开始，完成25步后会变成26，此时才是真的填满了棋盘
        if (move == board.length * board.length + 1) {
            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++) {
            int newY = y + moves[i][0];
            int newX = x + moves[i][1];
            if (isSafe(board, newY, newX)) {
                // 先尝试这个方向，走通了就返回true，走不通就继续试下一个
                if (knightsTour(board, newY, newX, move)) {
                    return true;
                }
            }
        }

        // 所有方向都试过都走不通，回溯重置当前位置
        board[y][x] = 0;
        return false;
    }

    public static void main(String[] args) {
        KnightsTour tour = new KnightsTour();
        int[][] board = new int[5][5];
        // Java的int数组默认初始值就是0，不用手动循环赋值啦

        boolean isCompleted = tour.knightsTour(board, 0, 0, 1);
        System.out.println("巡游是否完成：" + isCompleted);

        // 打印最终棋盘
        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("");
        }
    }
}

额外说明 #

• 原来的终止条件move == board.length * board.length会提前一步结束，因为move从1开始，第25步时move是25，执行move++后才是26，这时候才代表所有位置都填满了。
• isSafe方法里加入board[y][x] == 0的判断，让逻辑更紧凑，不用在递归开头再重复检查。

现在运行代码，程序会正确尝试所有可能的路径，最终完成5×5棋盘的骑士巡游。

内容的提问来源于stack exchange，提问作者J__