问题标签 [knights-tour]

最近几天，我一直克制自己的硕士学习，一直专注于这个（看似简单的）难题：

有这个 10*10 的网格构成了一个包含 100 个可用地点的正方形。目的是从一个角落开始，根据一些简单的“遍历规则”遍历所有地方并达到第 100 号（如果您是程序员，则为 99 号，而不是从 0 开始：）

遍历的规则是：
1. 沿纵横轴跳两个空格
2. 沿对角线跳一个空格
3. 每个方格只能访问一次

为了更好地可视化，这是一个有效的遍历示例（直到第 8 步）：
示例遍历 http://img525.imageshack.us/img525/280/squarepuzzle.png

出于无聊，我一直在手动解决这个难题。多年来，我时不时尝试手动解决，但从未超过96。听起来容易吗？试试自己，看看自己:)

因此，为了解决这个问题，我用 Python 开发了一个简短的（大约 100 行代码）程序。我是这门语言的初学者，我想看看我能做什么。
该程序简单地应用了详尽的尝试和错误解决技术。换句话说：蛮力深度优先搜索。

我的问题从这里出现：不幸的是，该程序无法解决问题，因为状态空间太大以至于搜索永远不会结束而没有找到解决方案。它可以毫不费力地上升到 98 号（并打印出来），但也不是一个完整的解决方案。
该程序还打印出到目前为止它所覆盖的搜索树的长度。几分钟后，从第 65 个元素开始的遍历列表就被覆盖到最后，只有一条路径。这个数字在指数增加的时间段内减少。我已经运行代码很长一段时间了，无法超过 50 个障碍，现在我确信了。

除非我永远运行它，否则这种简单的方法似乎是不够的。那么，如何改进我的代码以更快、更高效地提出解决方案呢？

基本上，我期待看到有关如何：

1. 捕获和利用特定于该问题的领域知识

2. 应用编程技术/技巧来克服疲惫

   ..并最终实现一个实质性的解决方案。

提前致谢。

修订
感谢 Dave Webb 将问题与它所属的域相关联：

这与骑士巡回赛问题非常相似，后者涉及在棋盘周围移动骑士而不重新访问同一个方格。基本上这是同一个问题，但有不同的“遍历规则”。

我正在研究骑士巡回赛问题，并决定尝试使用神经网络在 python 中实现它以找到解决方案。

该方法的一般解释可以在维基百科上找到

虽然我认为我已经正确实现了它（我看不到其他任何错误），但它不起作用，它更新了一些链接，删除了连接顶点度数大于二的边缘，但它没有不要收敛于解决方案。

我想知道是否有人对我错误实施的内容有任何想法（对不起，可怕的代码）。

编辑
工作代码可以在 GitHub https://github.com/Yacoby/KnightsTour找到

I've done my best to make a simple java implementation of the neural network knight's tour finder but I'm completely stumped as to why it fails to work..

there are 6 classes, 3 for the GUI which im pretty sure works fine, and 3 to deal with the actual logic etc.

If you are wondering, this is inspired by Yacoby's python offering He had a problem with the implementation also, although I don't think I'm making the same mistake..

I appreciate its not super coding, but any suggestions gratefully received

Neuron class:

Square class:

Control class:

the GUI classes: -

Board class:

}

GuiSquare class:

Line class:

我正在尝试更多地了解递归，但不知何故我无法解决骑士之旅，我希望有人能指出我的逻辑错误。

编辑：希望这没问题。我试图运行这个程序，但不能得到超过 22 个有效动作。

好的大家，我知道骑士的巡回赛问题在所有 cs 学生中都很流行，我无法让我的工作。我使用这种递归算法来进行移动，但是，一旦我到达移动 50 左右，我必须回溯，因为没有可用的移动，我最终永远无法完成巡回演出。我传递了一个 ChessNode（保存诸如节点是否已被访问、移动它是否被访问等内容）、下一行、下一列和前一个节点的移动计数。

所以，最初我检查可以移动到角板位置的点，然后我只是根据可用的移动进行递归调用。所以我想我的主要问题是我做错了什么？或者我可以使用其他条件使游览更直观一些吗？

提前致谢！

我正在尝试制作一个程序，它可以通过一个名为“Knight's Tour”的骑士（大小并不重要，但现在它是 6x6）的所有方格，请在 wiki 上查看。

游览应该是关闭的，这意味着最后访问过的广场上的骑士可以“攻击”他开始的广场。该代码适用于某些方块，例如，在 main 中输入“traverse(1,1,1)”会生成输出，该输出不仅显示他正在遍历，而且还回溯并返回成功地遍历目标。但是，如果我输入 'traverse(1,0,0)' ，我会得到一个StackOverflowError。由于它有时是成功的，回溯和遍历，我知道代码有效，我只是不知道如何摆脱错误。我假设我打了太多电话，但我不知道如何解决这个问题，有很多方块可以访问:) 编辑了代码，主要是因为老师会发现它说我作弊。

我必须编写 SML 代码来解决回溯中的骑士之旅问题。象棋骑士必须跑遍整个棋盘（大小：NxN），并且必须在每个方格中准确访问一次（最后不需要回到第一个方格）。

我已经编写了所有函数来创建一个空棋盘，设置或获取棋盘中的方块，获取可能的骑士下一步动作列表。但是我不知道如何在 SML 中编写递归函数（我知道如何在 C 中编写此算法，但不知道在 SML 中）。

用于 8x8 棋盘的 C 算法

我正在尝试用 JavaScript 编写一个算法来解决使用回溯的骑士​​之旅问题，但它不起作用。基本上，该函数应该输出一个名为visited的数组，其中包含每个移动的位置。但是，没有将位置附加到数组，它仍然是 [[0,0]]。这是我的代码。有什么线索吗？

谢谢你。

这是我写的代码。

一点解释。我使用 int [8][8] 来表示棋盘，最初我在棋盘的每个方格中输入数字 -1。

当骑士移动时，它用计数器（int counter）标记他访问的方格，然后从那里（以及骑士可以采取的所有合法移动）进行递归调用以找到路径（目标是每个方格只访问一次）。

一旦计数器达到 64，该函数bool knighttour(square start,int &counter,int cb[][8]) 必须返回 true，然后主程序应该显示“骑士之旅”，因为它在 [8][8] 棋盘上被标记。

我相信我提供的上述代码在无限循环上运行。我让它运行了 3 分钟。

我正在尝试使用递归回溯解决骑士巡回赛问题。有人可以帮我优化我的代码。我的代码工作到 6X6 板。. 在 N=7 之后，几乎需要无限时间来求解 。这是我的代码：

我正在使用斯坦福 106B 库（网格是二维向量）Visual Studio 2008 带有所需库文件的空白项目https://docs.google.com/viewer?a=v&pid=explorer&chrome=true&srcid=0BwLe9NJT8IreNWU0N2M5MGUtY2UxZC00ZTY2LWE1YjQtMjgxYzAxMWE3OWU2&hl=en