确定骑士是否可以通过二维阵列中的所有单元格——如果是的话，打印板

Question

我需要一个关于这个问题的建议，叫做“骑士之路”。给定一个n*n单元格初始化为0的单元格，我需要确定，给定一个任意骑士的位置，如果骑士可以通过单元格上的每一个单元格一次，骑士访问过的每一个单元格都将被标记为计数器，从：1-n^2.如果路径是可能的，我需要打印板。我需要打印所有有效的板。对于那些不知道国际象棋规则的人来说，骑士可以垂直向上或向下移动一个方块，水平移动两个方块，也可以垂直向上或向下移动两个方块，水平移动一个方块。

例如，给定一个5*5板，从（0,0）开始，该方法应打印：

{{1,16,11,6,21},
{10,5,20,15,12},
{17,2,13,22,7},
{4,9,24,19,14},
{25,18,3,8,23}};

以上所述将是为数不多的，因为考虑到不同的初始位置，可能会有不同的其他方式。我已经写了下面的代码，但它没有打印任何内容。我需要找出这里的逻辑缺陷，这样我才能让它工作。

public class KnightDemo {

    static int counter = 1;
    public static void KnightPath(int[][] b, int i, int j) {
        b[i][j] = counter;
        if (counter == b.length * b[0].length) {
            printMatrix(b);
            return;
        } else {
            counter++;

            if (isValid(b, i - 1, j + 2) && b[i - 1][j + 2] == 0) {
                KnightPath(b, i - 1, j + 2);
            } else {
                return;
            }
            if (isValid(b, i - 2, j + 1) && b[i - 1][j + 1] == 0) {
                KnightPath(b, i - 2, j + 1);
            } else {
                return;
            }
            if (isValid(b, i - 1, j - 2) && b[i - 1][j - 2] == 0) {
                KnightPath(b, i - 1, j - 2);
            } else {
                return;
            }
            if (isValid(b, i - 2, j - 1) && b[i - 2][j - 1] == 0) {
                KnightPath(b, i - 2, j - 1);
            } else {
                return;
            }
            if (isValid(b, i + 2, j - 1) && b[i + 2][j - 1] == 0) {
                KnightPath(b, i + 2, j - 1);
            } else {
                return;
            }
            if (isValid(b, i + 1, j - 2) && b[i + 1][j - 2] == 0) {
                KnightPath(b, i + 1, j - 2);
            } else {
                return;
            }
            if (isValid(b, i + 1, j + 2) && b[i + 1][j + 2] == 0) {
                KnightPath(b, i + 1, j + 2);
            } else {
                return;
            }
            if (isValid(b, i + 2, j + 1) && b[i + 2][j + 1] == 0) {
                KnightPath(b, i + 2, j + 1);
            } else {
                return;
            }

        }
    }

    public static boolean isValid(int[][] a, int i, int j) {
        if (i > a.length - 1 || i < 0 || j > a[0].length - 1 || j < 0) {
            return false;
        }
        return true;
    }

    public static void main(String[] args) {
        int[][] b = new int[5][5];
        for (int i = 0; i < b.length; i++) {
            for (int j = 0; j < b[0].length; j++) {
                KnightPath(b, i, j);
            }
        }
    }
    
    public static void printMatrix(int[][] matrix) {
        for (int[] rows: matrix) {
            StringBuilder buff = new StringBuilder();
            buff.append("[");
            for (int i = 0; i < rows.length; i++) {
                int value = rows[i];
                buff.append(value);
                if (i < rows.length - 1) {
                    buff.append(", ");
                }
            }
            buff.append("]");
            System.out.println(buff.toString());
        }
    }
}

输出是

[1, 2, 3, 4, 5]
[6, 7, 8, 9, 10]
[11, 12, 13, 14, 15]
[16, 17, 18, 19, 20]
[21, 22, 23, 24, 25]

Answer 1

要解决所有路径的问题，需要重置已耗尽路径的放置值，以便新路径可以访问它们。此外，你的计数器应该反映你走了多深，所以如果你退出尝试另一条路径，你的计数器也应该回滚。我建议将计数器作为参数传递，而不是使用静态计数器。此外，如果你想尝试所有有效的可能性，那么当一种可能性被认为无效时，你需要避免那些返回语句。

public static void KnightPath(int[][] b, int i, int j, int counter) {
    ...
        if (isValid(b, i - 1, j + 2) && b[i - 1][j + 2] == 0) {
            KnightPath(b, i - 1, j + 2, counter+1);
        }
    ...
    b[i][j] = 0;
}

public static void main(String[] args) {
    ...
            KnightPath(b, i, j, 1);
    ...
}

Answer 2

根据OP在评论部分的解释，目标是绘制出骑士可以从棋盘上某个位置走的所有可能路径。基本上，根据骑士的位置，计算所有合法路径。

如果骑士位于{0,0}，则骑士只有两条以{1,2}和{2,1}结尾的合法路径。这里的想法是在地图上捕捉到这一点。然后，转到电路板上的下一个位置（即{1，0}），并重复该过程。由于每个电路板位置都可以标识为一个整数（计数器），因此我们可以使用它来映射路径。。。

0=[{1, 2}, {2, 1}]
1=[{2, 2}, {1, 3}, {2, 0}]
...
n=[{n^-2 - 3, n^-2 - 2}, {n^-2 - 2, n^-2 - 3}] // last location is always a corner

为了简单起见，我决定创建一个坐标的Java记录来存储给定路径结束位置的{x， y}坐标，使我的map

这里的逻辑很简单。首先，在地图中为矩阵中的每个对应位置添加空列表。然后，在矩阵（2D数组）中迭代，计算骑士可以从该位置获得的所有合法路径。对于每个合法路径，添加路径结束位置的坐标。我使用了集合来消除重复的坐标。

我的解决方案（也许不是最优的）如下（使用OP代码作为基线）-需要Java15或更高版本才能运行。对于Java14或更早，用长度为2的整数[]替换坐标，并将坐标存储在其中。

public class KnightDemo {

    static int counter = 0;
    static Map<Integer, Set<Coordinates>> map = new HashMap<>();

    public static void KnightPath(int[][] b, int i, int j) {
        Set<Coordinates> paths = map.get(counter);
        if (isValid(b, i - 1, j + 2)) {
            paths.add(new Coordinates(i - 1, j + 2));
            map.put(counter, paths);
        }
        if (isValid(b, i - 2, j + 1)) {
            paths.add(new Coordinates(i - 2, j + 1));
            map.put(counter, paths);
        }
        if (isValid(b, i - 1, j - 2)) {
            paths.add(new Coordinates(i - 1, j - 2));
            map.put(counter, paths);
        }
        if (isValid(b, i - 2, j - 1)) {
            paths.add(new Coordinates(i - 2, j - 1));
            map.put(counter, paths);
        }
        if (isValid(b, i + 2, j - 1)) {
            paths.add(new Coordinates(i + 2, j - 1));
            map.put(counter, paths);
        }
        if (isValid(b, i + 1, j - 2)) {
            paths.add(new Coordinates(i + 1, j - 2));
            map.put(counter, paths);
        }
        if (isValid(b, i + 1, j + 2)) {
            paths.add(new Coordinates(i + 1, j + 2));
            map.put(counter, paths);
        }
        if (isValid(b, i + 2, j + 1)) {
            paths.add(new Coordinates(i + 2, j + 1));
            map.put(counter, paths);
        }

        counter++;
    }

    public static boolean isValid(int[][] a, int i, int j) {
        return i >= 0 && i < a.length && j >= 0 && j < a[0].length;
    }

    public static void main(String[] args) {
        int[][] b = new int[5][5];
        for (int i = 0; i < b.length; i++) {
            for (int j = 0; j < b[0].length; j++) {
                map.put(counter, new HashSet<>()); // add a new set before calculating paths
                KnightPath(b, i, j);
            }
        }
        map.entrySet().stream().forEach(System.out::println);
    }

    private static record Coordinates(int row, int col) {

        @Override
        public String toString() {
            return "{" + row + ", " + col + "}";
        }
    }
}

程序输出：

0=[{1, 2}, {2, 1}]
1=[{2, 2}, {1, 3}, {2, 0}]
2=[{2, 3}, {1, 4}, {2, 1}, {1, 0}]
3=[{2, 2}, {1, 1}, {2, 4}]
4=[{2, 3}, {1, 2}]
5=[{2, 2}, {0, 2}, {3, 1}]
6=[{2, 3}, {0, 3}, {3, 0}, {3, 2}]
7=[{0, 0}, {3, 3}, {2, 4}, {0, 4}, {3, 1}, {2, 0}]
8=[{0, 1}, {3, 4}, {3, 2}, {2, 1}]
9=[{3, 3}, {2, 2}, {0, 2}]
10=[{1, 2}, {0, 1}, {4, 1}, {3, 2}]
11=[{0, 0}, {3, 3}, {1, 3}, {0, 2}, {4, 0}, {4, 2}]
12=[{0, 1}, {3, 4}, {1, 4}, {0, 3}, {4, 1}, {3, 0}, {1, 0}, {4, 3}]
13=[{1, 1}, {4, 4}, {0, 2}, {0, 4}, {4, 2}, {3, 1}]
14=[{1, 2}, {0, 3}, {4, 3}, {3, 2}]
15=[{2, 2}, {1, 1}, {4, 2}]
16=[{2, 3}, {1, 2}, {1, 0}, {4, 3}]
17=[{1, 1}, {4, 4}, {2, 4}, {1, 3}, {4, 0}, {2, 0}]
18=[{1, 2}, {1, 4}, {4, 1}, {2, 1}]
19=[{2, 2}, {1, 3}, {4, 2}]
20=[{3, 2}, {2, 1}]
21=[{3, 3}, {2, 2}, {2, 0}]
22=[{3, 4}, {2, 3}, {3, 0}, {2, 1}]
23=[{2, 2}, {2, 4}, {3, 1}]
24=[{2, 3}, {3, 2}]

是的，你可以的！假设你用黑和白给矩阵播种。您可以增强逻辑，这样，如果结束位置对应于您的颜色，您就不会将其添加为有效路径，因为它被您的一块阻挡。

public class KnightDemo {

    static int counter = 0;
    static Map<Coordinates, Set<Coordinates>> map = new HashMap<>();

    public static void KnightPath(int[][] b, Coordinates coordinates) {

        Set<Coordinates> paths = map.get(coordinates);
        if (isValid(b, coordinates.row() - 1, coordinates.col() + 2)) {
            paths.add(new Coordinates(coordinates.row() - 1, coordinates.col() + 2));
            map.put(coordinates, paths);
        }
        if (isValid(b, coordinates.row() - 2, coordinates.col() + 1)) {
            paths.add(new Coordinates(coordinates.row() - 2, coordinates.col() + 1));
            map.put(coordinates, paths);
        }
        if (isValid(b, coordinates.row() - 1, coordinates.col() - 2)) {
            paths.add(new Coordinates(coordinates.row() - 1, coordinates.col() - 2));
            map.put(coordinates, paths);
        }
        if (isValid(b, coordinates.row() - 2, coordinates.col() - 1)) {
            paths.add(new Coordinates(coordinates.row() - 2, coordinates.col() - 1));
            map.put(coordinates, paths);
        }
        if (isValid(b, coordinates.row() + 2, coordinates.col() - 1)) {
            paths.add(new Coordinates(coordinates.row() + 2, coordinates.col() - 1));
            map.put(coordinates, paths);
        }
        if (isValid(b, coordinates.row() + 1, coordinates.col() - 2)) {
            paths.add(new Coordinates(coordinates.row() + 1, coordinates.col() - 2));
            map.put(coordinates, paths);
        }
        if (isValid(b, coordinates.row() + 1, coordinates.col() + 2)) {
            paths.add(new Coordinates(coordinates.row() + 1, coordinates.col() + 2));
            map.put(coordinates, paths);
        }
        if (isValid(b, coordinates.row() + 2, coordinates.col() + 1)) {
            paths.add(new Coordinates(coordinates.row() + 2, coordinates.col() + 1));
            map.put(coordinates, paths);
        }
    }

    public static boolean isValid(int[][] a, int i, int j) {
        return i >= 0 && i < a.length && j >= 0 && j < a[0].length;
    }

    public static void main(String[] args) {
        int[][] b = new int[5][5];
        for (int i = 0; i < b.length; i++) {
            for (int j = 0; j < b[0].length; j++) {
                Coordinates coordinates = new Coordinates(i, j);
                map.put(coordinates, new HashSet<>());
                KnightPath(b, coordinates);
                counter++;
            }
        }
        map.entrySet().stream().forEach(System.out::println);
    }

    private static record Coordinates(int row, int col) {

        @Override
        public String toString() {
            return "{" + row + ", " + col + "}";
        }
    }
}

输出：

{0, 0}=[{1, 2}, {2, 1}]
{2, 2}=[{0, 1}, {3, 4}, {1, 4}, {0, 3}, {4, 1}, {3, 0}, {1, 0}, {4, 3}]
{4, 4}=[{2, 3}, {3, 2}]
{0, 1}=[{2, 2}, {1, 3}, {2, 0}]
{2, 3}=[{1, 1}, {4, 4}, {0, 2}, {0, 4}, {4, 2}, {3, 1}]
{0, 2}=[{2, 3}, {1, 4}, {2, 1}, {1, 0}]
{2, 4}=[{1, 2}, {0, 3}, {4, 3}, {3, 2}]
{0, 3}=[{2, 2}, {1, 1}, {2, 4}]
{0, 4}=[{2, 3}, {1, 2}]
{3, 0}=[{2, 2}, {1, 1}, {4, 2}]
{3, 1}=[{2, 3}, {1, 2}, {1, 0}, {4, 3}]
{1, 0}=[{2, 2}, {0, 2}, {3, 1}]
{3, 2}=[{1, 1}, {4, 4}, {2, 4}, {1, 3}, {4, 0}, {2, 0}]
{1, 1}=[{2, 3}, {0, 3}, {3, 0}, {3, 2}]
{3, 3}=[{1, 2}, {1, 4}, {4, 1}, {2, 1}]
{1, 2}=[{0, 0}, {3, 3}, {2, 4}, {0, 4}, {3, 1}, {2, 0}]
{3, 4}=[{2, 2}, {1, 3}, {4, 2}]
{1, 3}=[{0, 1}, {3, 4}, {3, 2}, {2, 1}]
{1, 4}=[{3, 3}, {2, 2}, {0, 2}]
{4, 0}=[{3, 2}, {2, 1}]
{4, 1}=[{3, 3}, {2, 2}, {2, 0}]
{2, 0}=[{1, 2}, {0, 1}, {4, 1}, {3, 2}]
{4, 2}=[{3, 4}, {2, 3}, {3, 0}, {2, 1}]
{2, 1}=[{0, 0}, {3, 3}, {1, 3}, {0, 2}, {4, 0}, {4, 2}]
{4, 3}=[{2, 2}, {2, 4}, {3, 1}]

它们的打印顺序不同，但可以看出坐标{2，2}与上例中的计数器==12设置相同。单元格{2，2}是左上角的第13个单元格。