示例：使用回溯求解数独
你如何在没有递归的情况下回溯 - 使用循环？我只有在您调用 backtrack() 本身时才找到解决方案。
问问题
4274 次
1 回答
7
您可以使用堆栈模拟递归。
本质上，回溯在候选解决方案树中进行深度优先搜索。对于数独，这棵树在叶子处有完全填充的网格，在节点处有部分填充的网格。根是提供的网格。一个网格节点是另一个节点的子节点，如果它可以通过填充一个数字从它派生。通过深度优先搜索和回溯之间的类比，您可以轻松地以递归方式或使用堆栈实现回溯。
堆栈可以（概念上）包含候选网格。首先，将提供的（部分填充的）网格推入堆栈。然后在一个while循环内（检查堆栈是否为空），顶部网格被弹出。一个检查网格是否完全填充。如果完全填充，则验证数独约束，如果满足，则返回网格。如果网格未完全填充，则从中生成其他候选网格（可能没有），它们都被推入堆栈。这总结了转换的想法，但当然它并不是真正有效的。
于 2014-01-25T17:27:36.680 回答