java - Java 中的 Knight's Tour(递归)，使用 Graph 和 DFS

Question

我正在尝试计算 5x5 field 上所有可能的骑士移动:

为此，我尝试使用 DFS(深度优先搜索)类和 Graph 类。

我认为将这些整个类粘贴到这篇文章中可能需要太多代码(并且可能不够相关)，因此我将它们显示在这里:

Graph.java

DepthFirstSearch.java

Graph.java 使用 Bag.java:

Bag.java

该字段看起来像这样(每个字段使用一个 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

CalculatePath 方法中使用以下属性，该方法应计算骑士从特定方格到每个方格恰好访问一次的可能旅行次数(应花费一两分钟才能解决)。

可能的骑士步骤(在主类中)定义如下(使用图的边，G):

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

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

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

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, 16);

G.addEdge(6, 15);
G.addEdge(6, 17);
G.addEdge(6, 3);
G.addEdge(6, 13);

G.addEdge(7, 0);
G.addEdge(7, 4);
G.addEdge(7, 10);
G.addEdge(7, 14);
G.addEdge(7, 16);
G.addEdge(7, 18);

G.addEdge(8, 1);
G.addEdge(8, 17);
G.addEdge(8, 19);
G.addEdge(8, 11);

G.addEdge(9, 2);
G.addEdge(9, 12);
G.addEdge(9, 18);

G.addEdge(10, 1);
G.addEdge(10, 21);
G.addEdge(10, 7);
G.addEdge(10, 17);

G.addEdge(11, 0);
G.addEdge(11, 2);
G.addEdge(11, 20);
G.addEdge(11, 22);
G.addEdge(11, 8);
G.addEdge(11, 18);

G.addEdge(12, 1);
G.addEdge(12, 3);
G.addEdge(12, 21);
G.addEdge(12, 23);
G.addEdge(12, 5);
G.addEdge(12, 9);
G.addEdge(12, 15);
G.addEdge(12, 19);

G.addEdge(13, 2);
G.addEdge(13, 4);
G.addEdge(13, 22);
G.addEdge(13, 24);
G.addEdge(13, 6);
G.addEdge(13, 16);

G.addEdge(14, 3);
G.addEdge(14, 23);
G.addEdge(14, 7);
G.addEdge(14, 17);

G.addEdge(15, 6);
G.addEdge(15, 12);
G.addEdge(15, 22);

G.addEdge(16, 5);
G.addEdge(16, 7);
G.addEdge(16, 13);
G.addEdge(16, 23);

G.addEdge(17, 6);
G.addEdge(17, 8);
G.addEdge(17, 10);
G.addEdge(17, 14);
G.addEdge(17, 20);
G.addEdge(17, 24);

G.addEdge(18, 7);
G.addEdge(18, 9);
G.addEdge(18, 11);
G.addEdge(18, 21);

G.addEdge(19, 8);
G.addEdge(19, 12);
G.addEdge(19, 22);

G.addEdge(20, 11);
G.addEdge(20, 17);

G.addEdge(21, 10);
G.addEdge(21, 12);
G.addEdge(21, 18);

G.addEdge(22, 11);
G.addEdge(22, 13);
G.addEdge(22, 15);
G.addEdge(22, 19);

G.addEdge(23, 12);
G.addEdge(23, 14);
G.addEdge(23, 16);

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

int currentSquare = 20;
calculatePath(currentSquare);
System.out.println("From square " + currentSquare + " there are " + tours + " possible tours.");

以下是我尝试寻找可能的旅行的方法:

  private static void calculatePath(int currentSquare) {
        boolean foundChoice = false;
        for (int point : G.adj(currentSquare)) {

            if (dfs.marked(currentSquare)) {
                foundChoice = true;
//              dfs.unmark(currentSquare);
                calculatePath(point);
            }
        }
        if (!foundChoice) {
            tours++;
            dfs.unmark(currentSquare);
        }
        System.out.println(currentSquare + " - tours: " + tours);
    }

例如，如果我尝试通过 calculatePath(20) 调用此递归函数，它应该使用每个方 block 从该方 block 返回所有可能的旅行 (tours)在场上。

未标记的方 block 是已经到达的方 block ，在同一次游览中不应再访问。

现在，问题是我无法让 CalculatePath 跳过已经访问过的方 block (输出显示它从 20 到 17，从 20 到 11，然后停止递归方法)。

此外，该方法还不能计算多个游览。我想首先正确计算一条路径，并最终计算所有可能的旅行。

我使用的所有代码都在这篇文章中提供 - 包括上面链接中的类。

Answer 1

此代码仍然存在:)许多问题，但看起来您正在取得进展。

你的方法DepthFirstSearch.marked对我来说似乎是错误的。我本以为如果它成功地将标记从 false 更改为 true ，它应该返回 true 。这里您只返回 marked[w] 的值。

您的 DepthFirstSearch 构造函数似乎试图标记所有相邻的(及其所有相邻点)。这看起来很奇怪——你期望它如何运作？避免循环的正常 DFS 机制是在递归时在您触摸过的每个位置留下一个标记，并在递归完成时删除该标记。在这里，您似乎在一开始就标记了所有方 block ，然后当您完成所有相邻方 block 的一轮而没有找到标记的方 block 时取消标记它们。