2

之前有人问过骑士的巡回演出，但我仍然遇到问题。我正在尝试递归访问棋盘的所有单元格，但访问次数不能超过 52 次。之后，它回溯并且访问的单元格的数量倒计时。这是我的代码：

public class Ch7E22_3 {
    public static int[][] chess;
    public static int[][] adjacent;

    public static void main(String[] args) {
        chess = new int[8][8];
        adjacent = new int[][] { { 2, 1 }, { 2, -1 }, { -2, 1 }, { -2, -1 }, { 1, 2 }, { -1, 2 }, { 1, -2 },
                { -1, -2 } };
        initializeChess();
        move(1, 0, 0);
    }

    private static void move(int cnt, int row, int col) {
        chess[row][col] = cnt;
        if (cnt == (8 * 8)) {
            System.out.println("You moved around all cells: " + cnt);
        } else {
            for (int i = 0; i < 8; i++) {
                if (((row + adjacent[i][0] >= 0) && (row + adjacent[i][0]) < 8)
                        && ((col + adjacent[i][1] >= 0) && (col + adjacent[i][1] < 8))) {
                    if (chess[row + adjacent[i][0]][col + adjacent[i][1]] == 0) {
                        row = row + adjacent[i][0];
                        col = col + adjacent[i][1];
                        cnt++;
                        System.out.println(row + "  " + col + "  cnt = " + cnt);
                        move(cnt, row, col);
                    }
                }
            }
        }
        chess[row][col] = 0;
    }

    private static void initializeChess() {
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                chess[i][j] = 0;
            }
        }
    }
}
4

2 回答 2

2

第一个问题在这里：

for (int i = 0; i < 8; i++) {

所以，你有那个 for 循环。假设您在 51 处输入 cnt。

现在你有

if ( ... some overly complicated condition ... ) {
  ... cnt++
  move(cnt,

现在发生的事情是：首先您进行递归调用，并且可能每次都正确执行您的第一个 if 命中。因此，您增加 cnt 并再次递归。因此，您的打印输出显示 cnt 如何不断增加。

但是在某些时候，递归结束了——if条件不再成立。所以递归调用的方法...结束。但请记住：您调用了该方法......从另一个调用move。而且那个可能仍在循环中。更重要的是， move() 有自己的 cnt 版本。

要明白我的意思：将 cnt 从方法局部变量更改为您的类的字段，类似于您的板！当你这样做时，你会发现你的代码实际上打印了：

...
3  7  cnt = 52
2  4  cnt = 53
...
2  3  cnt = 64
You moved around all cells: 64
0  4  cnt = 65
...

实际上稍后停止

4  0  cnt = 126

含义：打印 cnt 只是您的算法无法正常工作的副作用！

最后：我建议将您的 if 条件分解为一组小的辅助方法，例如

private static isXyz(...)

并在 if 语句中调用这些方法——这将极大地提高可读性！

于 2016-10-25T09:25:29.847 回答
2

你的回溯不正确。到最后一行执行时，设置chess[row][col]回零，row并且col几乎可以肯定已经改变。

最好不要在您的方法中更改row,col和cnt，而只将新值传递给递归调用。像这样的东西，虽然我还没有检查你的逻辑的其余部分：

    for (int i = 0; i < 8; i++) {
        int nextrow = row + adjacent[i][0];
        int nextcol = col + adjacent[i][1];
        if (nextrow >= 0 && nextrow < 8 &&
                nextcol >= 0 && nextcol < 8) {
            if (chess[nextrow][nextcol] == 0) {
                System.out.println(nextrow + "  " + nextcol + "  cnt = " + (cnt+1));
                move(cnt+1, nextrow, nextcol);
            }
        }
    }

为确保您在仅修改传递给后续递归调用的值时保持一致，并且从不在方法中修改它们，您可以将参数设为 final：

private static void move(final int cnt, final int row, final int col) {
    ...
}
于 2016-10-25T09:28:11.093 回答