问题标签 [knights-tour]

我知道有几个类似的线程，但即使在 SO 之外我也没有找到解决方案。这是我的问题：我为骑士之旅问题实现了 Warnsdorff 的算法http://en.wikipedia.org/wiki/Knight%27s_tour，但在某些情况下它没有给出解决方案。在我读到的某些地方，它可以通过一些更改更好地工作，但没有人指定哪些更改是那些。有人知道解决方案吗？我知道其他算法，但它们要复杂得多。

即使对于 8x8 棋盘，它有时也不能提供好的解决方案。我认为阅读我的代码没有意义，因为它是经典的 Warnsdorff 的：检查可能的移动，并在下一步中选择移动最少的一个。

我正在尝试使用深度优先搜索算法来解决骑士之旅问题。每当算法有两个都导致死胡同的选择时，它似乎就在循环。我知道这是因为算法会在发现死胡同时再次将“wasVisited”布尔值重置为假，但我根本不知道如何解决它。

这是我到目前为止的代码：

提前致谢 ：）。

编辑：

这是更新的代码和一些输出：

我正在尝试为 5x5 板解决此问题，因此有 25 个垂直（0 - 24）。以下是当前问题变得更加清晰的一些输出：

当然，输出末尾的循环是不应该发生的。

我在学年的最后一个项目（我作为 CS 学生的第一年）的代码中找不到错误。我在执行骑士巡回问题时陷入了递归。这是有问题的文件：https ://github.com/sheagunther/tsp161knightstour/blob/master/KnightsTourRecursiveSearch.java

具体来说，我的问题在于这部分代码（从第 265 行开始）：

这是 findTour() 的结束。这是程序的一部分，它测试从当前方格（也称为单元格）的所有可能的移动，如果可以从新移动到的方格完成游览，则返回 true。如果不能从广场完成游览，它会进入 else{ 并撤消移动。这就是我认为的问题所在。

现在，按照上面的代码设置，程序陷入了无限递归循环。

请注意声明的这一部分else{：

这部分代码将 chessBoard 中的方块更改为 -1，这意味着它未被访问（1 = 已访问）。如上所示，新移动的 currentRow 和 currentColumn 用于将方格设置回未访问状态。然后使用 currentRowStorage 和 currentColumnStorage 将这些值重置为先前的跳转值。

如果我将代码更改为

它成功地找到了一个错误的路线，其中最后 1/3 左右的移动只是在几个方格之间来回跳跃。这是意料之中的，因为它没有正确处理重置过程。

我怀疑我的问题是由于我声明变量的位置。这是我的第一个复杂的递归问题，我不确定我是否正确处理了 currentRow/Column 和 currentRow/ColumnStorage 之间的切换。我应该在本地或多或少地声明它们吗？

这是描述该项目的页面： http: //cs.usm.maine.edu/~briggs/webPage/c161/projects/KnightsTour.html

以下是要求的相关部分：

如果游览未完成，则 findTour 确定可以从骑士的当前单元格到达的空单元格列表（可能为空），并将此列表存储在本地声明的列表变量中，candidateNextMoves。将此列表变量声明为方法的本地变量是至关重要的。如果此列表为空，则无法扩展当前部分游览，因此 findTour 应返回 false。如果列表不为空，则 findTour 尝试通过列表上的每个移动来扩展游览，如下所示。它遍历列表，并且对于列表中的每个单元格，它会下一次移动到该单元格，更新所有 L（巡回赛中的移动列表），B（棋盘状态的二维数组（已访问，未访问))、currRow 和 currCol 以反映这一举动。然后它递归地调用自己，将调用结果分配给本地声明的布尔变量，您可以将其命名为“成功”。如果 success 为 true，findTour 返回 true。如果成功为假，findTour 撤消它刚刚进行的移动，或“回溯”，并尝试 CandidateNextMoves 的下一步移动。您将维护一个静态 int 变量 backtrackCount，该变量初始化为 0，并随着移动的每次撤消而递增。

一个注释-我将我的布尔值称为“tourFound”而不是“成功”。

在 8X8 棋盘中，只考虑马，如果我们从棋盘的任何一个方格开始马，目标是覆盖最大的方格数，而不重复任何一个方格。到目前为止，我发现下面的代码最有效的解决方案是：

其中以 1 开头的数字表示骑士所遵循的路径。我的问题是这个代码是否可以被纠正为一个完美的答案，即 64（我的只有 60）？

我正在尝试使用 DFS 制作程序骑士之旅，但我无法解决这个程序..因为我总是有这样的消息错误

KnightTour 的 java.util.ArrayList.get(ArrayList.java:384) 的 java.util.ArrayList.elementData(ArrayList.java:371) 的线程“AWT-EventQueue-0”中的异常 java.lang.ArrayIndexOutOfBoundsException: -1 .processKnightTour(KnightTour.java:82)

我希望有一个人可以帮助我..

我正在尝试使用本网站上给出的回溯解决骑士巡回赛问题。

在 ideone上给出的实现 大约需要 0.49 秒。

而我实现的几乎相同的一个是在 ideone 上显示超出时间限制（超过 5 秒）。

什么在我的代码中执行了这么长时间？

我最近一直在阅读 C++，尤其是 STL，我决定再做一次骑士巡回赛的问题。我正在考虑实现这一点的最佳方法，我正在寻求帮助。

只是为了好玩和练习，我想我会从一个“Piece”基类开始，“Knight”类可以从中继承。我想这样做，以便稍后我可以尝试添加其他部分（即使大多数部分无法遍历整个电路板并完成问题）。

因此，“棋子类”将需要某种容器来存储棋子在棋盘上的坐标以及它在该特定步骤中所做的移动次数。

我想我需要一个包含 64 (8 * 8) 个位置的链表来最有效地执行此操作，其中包含 x、y 和移动。

查看 STL 容器，除了可以容纳一种以上类型的 map 之外，我找不到任何东西。

我可以做些什么来存储坐标对和一个容器中移动次数的 int？有比使用矢量、列表或地图更有效的方法吗？我需要自定义容器吗？

谢谢！

我编写了一个基于尝试解决骑士巡回赛问题的程序。我相信我已经想出了一个合适的解决方案，一切看起来都很好。

我很好奇的一个小问题是一小段代码，它基于展望未来可能的方格来实现最佳移动。

如果我这样实现（implementation1）——</p>

软件会挂起 - 为什么？

如果我做一个像这样（实施2）这样无害且看似微不足道的小改动——</p>

那么一切都很好，代码将得出结论。

我正在使用 netbeans 7.1 编写我的软件，并认为它一定与 IDE 有关，所以我尝试仅使用“javac”和命令行来编译它，只是为了找到相同的结果。我不明白为什么我不能像这样在数组参数中调用这个方法——vertical[ HERE ] 或 Horizo​​ntal[ HERE ] 并让返回的结果在表达式中使用。我之前已经设法编写这样的代码而没有任何问题。

这是被调用的方法——</p>

上面 return 语句中使用的方法 bestmove -

我编写了这段代码来打印一个可能的骑士之旅，这样每个地方都被访问一次。

此代码有效，但以下代码无效，我对 X[] 和 Y[] 进行了少许更改，这不应该影响算法。

我刚变

至

我正在尝试编写骑士巡回递归算法：

有人可以告诉我我在哪里犯了错误吗？我已经逐步检查了哪些池算法添加到列表中。添加 4,3 池然后 6,4 池后什么是大惊喜算法应该以 6,4 作为实际位置调用它自己，但我不知道为什么它以 4,3 作为实际位置调用它自己。