无限循环搜索的 DFS 实现 space

Question

我目前正在编写一段代码来解决数字游戏：

从一个空的 10x10 网格开始。
在随机方格中放置一个 1。
依次填入方块中的数字2-100。
上下左右 - 您必须将数字放在 3 个方块之外。
对角线 - 您必须将数字放在 2 个方块之外。

我尝试实现深度优先搜索算法来搜索所有路径以找到（可能的）解决方案。我遇到的问题是，当搜索到达没有更多有效移动和回溯的状态时，我无法将块标记为已访问，因为解决方案将不可避免地使用来自另一条路径的块，但如果我不标记它们如已访问，则搜索将无限次循环和重新搜索路径。

这个问题有什么优雅的解决方案吗？还是我应该研究其他搜索算法以解决问题？任何正确方向的提示都将不胜感激。

示例（前 3 步）：

. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . 1 . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .

. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . 1 . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . 2 . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .

. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . 1 . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . 2 . . . .
. . . . . . . . . .
. . . 3 . . . . . .
. . . . . . . . . .

Answer 1

由于访问状态似乎是您的问题陈述，您可以创建另一个相同大小的数组并将访问状态放在那里。

您可以做的另一件事是使用负数作为访问状态标志。例如，未访问标记为“5”的位置，但标记为“-5”的位置表示它是“5”，但此外还访问了它。

Answer 2

这个问题可以归类为试图找到 Hamiltonian Path。寻找哈密顿路径是一个 NP 完全问题，没有已知的有效通用解决方案。

感谢@PaulHankin 的回答。

无限循环搜索的 DFS 实现 space

Implementation of DFS for infinitely loopy search space

algorithm

graph

depth-first-search