时间戳

首页 > 解决方案 > Java中的Knight's Tour递归方法，代码执行卡在第5步（在25平方板上）？

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

问题描述

由于棋盘是 5x5，所以应该有 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("");
    }
}

}

标签： javaknights-tour

解决方案

我相信您的问题在于这部分代码：

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”移动，您将骑士派到那里，如果已经派上去，您将从巡回赛中完全返回 false。如果巡回赛失败，您应该修改此部分以继续检查移动，或者修改您的“isSafe”方法以说明非零棋盘位置实际上并不安全。

推荐阅读