问题标签 [knights-tour]

我正在使用 Racket 中的 DFS 实现骑士之旅。

我查看了如何让 define 在 cond 中工作，并看到在 let 中包装 define 会使其工作。但现在我得到这个错误：

begin（可能是隐含的）：在一系列内部定义之后没有表达式：(begin (define nxn (cons n n)) (define array (for/vector ((x (car nxn))) (for/vector ((y (cdr nxn))) 0))))

知道这是为什么吗？

所以我想出了这个实现来解决 8*8 棋盘的骑士之旅。但似乎它需要很长时间才能运行（以至于我不得不停止它）。但是，如果我用注释中写的数组替换 dx、dy 数组，程序就会像魔术一样工作并给出输出。他们说它巧妙地选择了数组，因此暴力算法很幸运能够快速找到解决方案。

但是首先是如何提出这个数组的，这个数组（dx，dy）是我从其他代码中得到的。所以谁能解释我为什么这段代码适用于这些数组（在评论中）而不是我的。

我正在尝试在 Racket 中使用 DFS 来实现 Knight's Tour。

我当前的实现涉及从当前位置生成可能的合法移动列表（不在棋盘之外，也不在先前步骤的列表中）并将其放入堆栈中。然后我将第一个元素从堆栈中取出并递归运行算法，并将其作为下一个当前位置。如果移动的数量超过了棋盘上的方格数量，那么我知道我已经进行了详尽的搜索并且失败了。如果我不能生成任何合法节点，我就知​​道我已经完成了骑士之旅并输出了结果多维数组。我还计算了生成的孩子（合法移动）的数量；如果该数字大于预设的 max_node_count，它将中止算法。

我在想这个实现可能会遗漏一些东西。如果我只是移动到堆栈中的下一个位置，我会不会在没有必要进行骑士之旅的情况下在棋盘上跑来跑去？如何跟踪以前的正确位置和回溯？或者我应该使用不同的条件来检查是否完成。我想我不小心提前关闭了算法。

当我运行我当前的实现时，我收到一条消息，表明我已经用尽了搜索。我正在 5x5 板上进行测试，所以肯定有一个解决方案。

我认为当我进行详尽搜索或完成骑士之旅时，我的检查条件有问题。我在下面的评论应该更详细地说明我是如何实施这些检查的。

感谢阅读，感谢您的帮助。

我正在使用 DFS 进行骑士之旅的实施。

我的问题是，当我运行它时，它在第 20 步之前都可以正常工作，但之后算法会崩溃并在 5x5 板上输出（对于从 (0,0) 开始的 5x5 板有一个解决方案）：

*合法的继任者必须是 0 <= row < n 和 0 <= column < n 并且不是上一步。

我的实现包括使用 genSuccessors 函数生成*合法的后继者，将它们扔到堆栈上，并以堆栈顶部的项目作为新的当前位置递归运行算法。如果下一个位置是之前未采取的步骤，我只会增加 step_count（负责跟踪骑士访问的方格顺序）。当我无法再生成任何孩子时，该算法会探索边界中的其他替代方案，直到边界为空（失败条件）或 step_count = # 棋盘上的方格（获胜）。

我认为一般的算法是合理的。

编辑：我认为问题是当我不能产生更多的孩子时，我去探索边境的其余部分，我需要废弃一些当前的旅行。我的问题是，我怎么知道我需要走多远？

以图形方式，在树中，我认为我需要返回到最近的节点，该节点有一个未访问的子节点的分支，并从那里重新开始，在走下前一个（错误的）分支时报废所有访问的节点。它是否正确？我将如何在我的代码中跟踪它？

感谢您阅读这么长的帖子；并感谢你们可以给我的任何帮助。

我目前正在尝试使用 Python 编写一个简单的多线程程序。但是我遇到了一个我认为我错过的错误。我正在尝试简单地编写一个使用蛮力方法解决以下问题的程序：

从图像中可以看出，有一个棋盘，骑士在各个方格中移动。

我的方法是简单地尝试每一种可能的方式，其中每一种可能的方式都是一个新线程。如果在线程结束时没有可能的移动，如果等于 63，则计算访问了多少个正方形，在简单文本文件上写入解决方案...

代码如下：

我愿意接受所有建议...我的示例输出如下：

如果似乎由于某种原因线程数停留在 12...任何帮助将是最受欢迎的...

谢谢

我目前正在从事骑士巡回赛项目。我的最终目标是使用回溯（通过实现堆栈）和 Warnsdorff 的启发式方法来创建这个项目。我不允许使用任何已经创建了堆栈函数的库，例如 push 和 pop。我也不允许使用递归来解决问题。话虽如此，我现在很困，我的下一个重要里程碑将是仅通过回溯来解决问题。

我根本不会粉饰这一点，但现在我的代码是一团糟。我几乎已经创建了使程序运行所需的所有工具，但现在我只需要将所有部分放在一起。

以下是我的代码：

}

所以我在这一点上的想法是做以下事情：

创建一个循环，使用水平和垂直数组（马可能的移动）改变马的当前位置。一旦位置发生变化，计数器将递增，并且 -1 将被当前计数器值替换。当骑士被移动后，需要使用我创建的推送函数将新坐标的信息传递给链表。为了做到这一点，我需要找出一种方法来传递一个数组 (x,y) 或多个值来推送。我还需要创建一些我目前正在处理的边界检查（确保骑士不会移动到他去过的地方并且不会离开棋盘）。最后，如果骑士确实卡住了，我需要使用我创建的弹出函数返回一步并尝试继续执行不同的动作。

我真的非常感谢您提供的任何帮助、更正、起点或其他建议！我好困。。

当我运行程序而不是查找 Knights Tour 时，我收到 StackOverflow 错误。知道是什么原因造成的，以及如何更改代码以实际找到 Knights Tour 并消除此错误。项目适用于我的 CS280 课程，将于周五到期，请帮忙。谢谢！！

每次我运行程序时，它都不会超过第 10 步，因为 q 总是通过 9，这是我在 switch 语句中的最后一种情况，它使移动将其发送到默认值。请帮助有谁知道我如何控制 q 使其不会通过 9，或者如果它通过了，我可以使该函数执行其他操作。

我创建了一个专门为此目的处理 2d 向量的类 Board。我正在尝试解决骑士之旅。我想在完成后打印出来。使用递归 voyagingKnight() 函数，我发现它没有做任何事情，也没有打印结果。似乎我想增加递归调用的步骤号，但这不起作用。

向量参数 incs 是用于移动马的 2d 增量向量，在每一行中，第一列中移动一行，第二列中移动一列。

有人对我在这里推理的缺陷有任何建议吗？相关代码

我正在尝试用 8*8 棋盘解决骑士的巡回问题。但是我的回溯是无限循环的。我的逻辑功能如下：-

N 为 8。

sol [][] 存储骑士的移动。

数组 move_x 和 move_y 存储要添加到 x 和 y 以获得骑士的下一个位置的值。

我首先将 x 传递为 0，y 传递为 0，no_of_moves 传递为 1，sol[][] 中的所有值都传递为 -1，除了 sol[0][0] 传递为 0。

并is_valid()检查nextx, 和nexty是否在棋盘内且尚未访问。