使用 DFS 计算 Java 中 5x5 场地上可能的马移动

Question

我正在尝试计算 5x5 场地上所有可能的马移动。

为此，我尝试使用 DFS（深度优先搜索）和图表 class。

该字段看起来像这样（每个字段使用一个 id）：

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

可能的步骤定义如下（使用图的边，G）：

G.addEdge(0, 1); G.addEdge(0, 5);

G.addEdge(1, 2); G.addEdge(1, 6);

G.addEdge(2, 3); G.addEdge(2, 7);

G.addEdge(3, 4); G.addEdge(3, 8);

G.addEdge(4, 9);

G.addEdge(5, 6); G.addEdge(5, 10);

G.addEdge(6, 7); G.addEdge(6, 11);

G.addEdge(7, 8); G.addEdge(7, 12);

G.addEdge(8, 9); G.addEdge(8, 13);

G.addEdge(9, 14);

G.addEdge(10, 11); G.addEdge(10, 15);

G.addEdge(11, 12); G.addEdge(11, 16);

G.addEdge(12, 13); G.addEdge(12, 17);

G.addEdge(13, 14); G.addEdge(13, 18);

G.addEdge(14, 19);

G.addEdge(15, 16); G.addEdge(15, 20);

G.addEdge(16, 17); G.addEdge(16, 21);

G.addEdge(17, 18); G.addEdge(17, 22);

G.addEdge(18, 19); G.addEdge(18, 23);

G.addEdge(19, 24);

G.addEdge(20, 21);

G.addEdge(21, 22);

G.addEdge(22, 23);

G.addEdge(23, 24);

这是我试图找到可能目的地的内容：

private static void calculatePath(int currentSquare) {
        short tours = 0;

        for (int point : G.adj(currentSquare)) {
            System.out.print(currentSquare + " ");
            if (dfs.marked(currentSquare)){
                tours++;
                dfs.unmark(currentSquare);
                calculatePath(point);
            }
        }
        System.out.println(currentSquare + " - tours: " + tours);
        System.out.println("\n");
    }

例如，如果我尝试通过 calculatePath(20) 调用此递归函数，它应该 return 11 和 17，因为这是骑士可以从该字段跳转到的唯一可能目的地（ ID 为 20）。未标记的方块是已经到达的方块。

变量 tours 将是可能的游览次数（在 calculatePath(20) 的情况下为 2）。

Answer 1

您将需要一些方法来在图表中表达方向。您的图表 class 看起来如何？您可以做的是实现左、右、上和下的方法，其中 return 该方向的顶点（如果没有相邻顶点，则为 null）。这样，您就可以找到可能的动作。在您的示例中，return 顶点的唯一组合是 2x right()、1x up() 和 1x right()、2x up()。

Answer 2

你的主要问题是你在递归之前unmark计算正方形。

此代码：

        if (dfs.marked(currentSquare)){
            tours++;
            dfs.unmark(currentSquare);
            calculatePath(point);
        }

是说：

如果这个方块没有标记：
1. 标记正方形
2. 递增tours
3. 取消标记方块。 << 这显然是错误的。
4. 从这个新方块计算一条新路径。

只有在您尝试从现在标记的方块开始的新路径后，您才需要 unmark。

这不能解决您的问题并生成马移动，但它肯定会有所帮助。

您遇到的下一个问题是您要添加到图形中的边是每个正方形的直接邻居。如果你想检查马的移动，你需要增加图形标记方块，这些方块是马移动分开的相邻。这是给你的前五个 - 我会让你完成列表。

    g.addEdge(0, 7);
    g.addEdge(0, 11);

    g.addEdge(1, 10);
    g.addEdge(1, 12);
    g.addEdge(1, 8);

    g.addEdge(2, 5);
    g.addEdge(2, 11);
    g.addEdge(2, 13);
    g.addEdge(2, 9);

    g.addEdge(3, 6);
    g.addEdge(3, 12);
    g.addEdge(3, 14);

    g.addEdge(4, 7);
    g.addEdge(4, 13);

    g.addEdge(5, 2);
    g.addEdge(5, 12);
    g.addEdge(5, 14);

同样 - 这可能不是您问题的解决方案，但它显然是您的问题之一。

使用 DFS 计算 Java 中 5x5 场地上可能的马移动

Calculate possible knight moves on a 5x5 field in Java, using DFS

java

recursion

depth-first-search

knights-tour