java - Knight 的巡回递归找不到解决方案

Question

之前有人问过 Knight 的巡演，但我仍然遇到问题。我正在尝试递归访问棋盘的所有单元格，但我不能进行超过 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;
            }
        }
    }
}

Answer 1

第一个问题是:

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 从 方法本地 变量更改为您类(class)的一个字段，类似于您的董事会!当您这样做时，您会发现您的代码实际上打印了:

...
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 语句中调用这些方法 - 这将极大地提高可读性!