我正在尝试在 Racket 中使用 DFS 来实现 Knight's Tour。
我当前的实现涉及从当前位置生成可能的合法移动列表（不在棋盘之外，也不在先前步骤的列表中）并将其放入堆栈中。然后我将第一个元素从堆栈中取出并递归运行算法，并将其作为下一个当前位置。如果移动的数量超过了棋盘上的方格数量，那么我知道我已经进行了详尽的搜索并且失败了。如果我不能生成任何合法节点，我就知道我已经完成了骑士之旅并输出了结果多维数组。我还计算了生成的孩子（合法移动）的数量；如果该数字大于预设的 max_node_count，它将中止算法。
我在想这个实现可能会遗漏一些东西。如果我只是移动到堆栈中的下一个位置，我会不会在没有必要进行骑士之旅的情况下在棋盘上跑来跑去？如何跟踪以前的正确位置和回溯？或者我应该使用不同的条件来检查是否完成。我想我不小心提前关闭了算法。
当我运行我当前的实现时，我收到一条消息，表明我已经用尽了搜索。我正在 5x5 板上进行测试，所以肯定有一个解决方案。
我认为当我进行详尽搜索或完成骑士之旅时，我的检查条件有问题。我在下面的评论应该更详细地说明我是如何实施这些检查的。
感谢阅读，感谢您的帮助。