示例：使用回溯法解决数独
如何在没有递归的情况下进行回溯 - 使用循环？我只找到了在调用backtrack（）本身时的解决方案。
1个回答
9
您可以使用堆栈来模拟递归。
回溯实际上是在候选解树中进行深度优先搜索。对于数独游戏，该树的叶子节点是完全填充的格子，节点是部分填充的格子。根是提供的网格。如果一个格子可以通过填数字从另一个格子中得到，则该格子节点是另一个格子节点的子节点。通过深度优先搜索和回溯之间的这种类比，您可以很容易地使用递归或堆栈来实现回溯。
堆栈（概念上）包含候选网格。首先，提供的（部分填充的）网格被推入堆栈。然后，在 while 循环内（检查堆栈是否为空），弹出顶部网格。检查网格是否已经完全填充。如果网格已经完全填充，则验证数独的限制条件，并返回满足条件的网格。如果网格没有完全填充，则从它生成其他候选网格（可能为零），然后将它们全部推入堆栈。这就总结了转换的想法，但是当然，它并不是真正有效的。
回溯实际上是在候选解树中进行深度优先搜索。对于数独游戏，该树的叶子节点是完全填充的格子，节点是部分填充的格子。根是提供的网格。如果一个格子可以通过填数字从另一个格子中得到，则该格子节点是另一个格子节点的子节点。通过深度优先搜索和回溯之间的这种类比，您可以很容易地使用递归或堆栈来实现回溯。
堆栈（概念上）包含候选网格。首先，提供的（部分填充的）网格被推入堆栈。然后，在 while 循环内（检查堆栈是否为空），弹出顶部网格。检查网格是否已经完全填充。如果网格已经完全填充，则验证数独的限制条件，并返回满足条件的网格。如果网格没有完全填充，则从它生成其他候选网格（可能为零），然后将它们全部推入堆栈。这就总结了转换的想法，但是当然，它并不是真正有效的。
- user3146587
2
这是什么意思？我不需要模拟递归，我需要使用循环，是否有回溯数独的循环版本？ - ERJAN
1转换后的版本将具有一个“while”循环，检查堆栈是否为空。 - user3146587
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接