确定骑士是否可以穿过二维数组中的所有单元格 - 如果可以，打印板
Determining if a knight can pass through all cells in a 2d array - if so print board
我需要关于这个名为“Knight Path”的问题的建议。
给定一个 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]
根据 OP 在评论部分的解释，目标是绘制出骑士从棋盘上的某个位置可以采取的所有可能路径。基本上，给定骑士的位置b[i][j]，计算所有合法路径。
如果骑士位于 {0, 0}，则骑士只有两条合法路径以 {1, 2} 和 {2, 1} 结束。这里的想法是在地图中捕获它。然后，移动到棋盘上的下一个位置（即 {1, 0}）并重复该过程。由于每个板位置都可以标识为一个整数（counter），我们可以用它来映射路径...
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 record 坐标来存储结束位置的 {x, y} 坐标给定路径，使我的地图 <Integer, Set<Coordinates>>
这里的逻辑很简单。首先，为矩阵中每个对应位置的空列表播种地图。然后，遍历矩阵（二维数组）并计算骑士可以从该位置走的所有合法路径。对于每个合法路径，添加路径结束位置的 Coordinates。我使用 Set 来消除重复坐标。
我的解决方案（可能不是最优的）如下（使用 OP 代码作为基准）- 需要 Java 15 或更高版本到 运行。对于 Java 14 或更早版本，将 Coordinates 替换为长度为 2 的 Integer[]，并将坐标存储在其中。
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}]
更新：你能在真正的国际象棋游戏中使用它吗？
是的，你可以！假设您使用 black 和 white 作为矩阵的种子。您可以增强逻辑，这样，如果结束位置对应于您的颜色，您就不会添加为有效路径，因为它被您的一个棋子挡住了。
第二次更新：相同的代码，但使用 Coordinate 对象作为键
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} 与前面示例中的 counter==12 是同一组。单元格 {2, 2} 是 top-left.
中的第 13 个单元格
要解决所有路径，您需要重置已用尽的路径的放置值，以便新路径可以访问它们。此外，你的计数器应该反映你走了多深，这样如果你退出尝试另一条路径，你的计数器也应该回滚。我建议将计数器作为参数传递，而不是使用静态计数器。此外，如果您想尝试所有有效的可能性，那么只要一种可能性被认为无效，就需要避免那些 return 语句。
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);
...
}
我需要关于这个名为“Knight Path”的问题的建议。 给定一个 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]
根据 OP 在评论部分的解释，目标是绘制出骑士从棋盘上的某个位置可以采取的所有可能路径。基本上，给定骑士的位置b[i][j]，计算所有合法路径。
如果骑士位于 {0, 0}，则骑士只有两条合法路径以 {1, 2} 和 {2, 1} 结束。这里的想法是在地图中捕获它。然后，移动到棋盘上的下一个位置（即 {1, 0}）并重复该过程。由于每个板位置都可以标识为一个整数（counter），我们可以用它来映射路径...
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 record 坐标来存储结束位置的 {x, y} 坐标给定路径，使我的地图 <Integer, Set<Coordinates>>
这里的逻辑很简单。首先，为矩阵中每个对应位置的空列表播种地图。然后，遍历矩阵（二维数组）并计算骑士可以从该位置走的所有合法路径。对于每个合法路径，添加路径结束位置的 Coordinates。我使用 Set 来消除重复坐标。
我的解决方案（可能不是最优的）如下（使用 OP 代码作为基准）- 需要 Java 15 或更高版本到 运行。对于 Java 14 或更早版本，将 Coordinates 替换为长度为 2 的 Integer[]，并将坐标存储在其中。
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}]
更新：你能在真正的国际象棋游戏中使用它吗？
是的，你可以！假设您使用 black 和 white 作为矩阵的种子。您可以增强逻辑，这样，如果结束位置对应于您的颜色，您就不会添加为有效路径，因为它被您的一个棋子挡住了。
第二次更新：相同的代码，但使用 Coordinate 对象作为键
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} 与前面示例中的 counter==12 是同一组。单元格 {2, 2} 是 top-left.
要解决所有路径，您需要重置已用尽的路径的放置值，以便新路径可以访问它们。此外，你的计数器应该反映你走了多深，这样如果你退出尝试另一条路径，你的计数器也应该回滚。我建议将计数器作为参数传递，而不是使用静态计数器。此外，如果您想尝试所有有效的可能性，那么只要一种可能性被认为无效，就需要避免那些 return 语句。
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);
...
}