algorithm - 无限循环搜索空间的DFS实现

Question

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

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

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

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

示例(前 3 个 Action ):

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

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

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

Answer 1

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

感谢@PaulHankin 的回答。