iteration - 回溯范式 : is it possible to do it without recursion?

Question

<分区>

Answer 1

您可以使用堆栈模拟递归。

本质上，回溯在候选解决方案树中进行深度优先搜索。对于数独，这棵树在叶子处有完全填充的网格，在节点处有部分填充的网格。根是提供的网格。如果一个网格节点可以通过填充一个数字从它派生出来，那么它就是另一个网格节点的子节点。通过深度优先搜索和回溯之间的类比，您可以轻松地以递归方式或使用堆栈实现回溯。

堆栈可以(概念上)包含候选网格。首先，将提供的(和部分填充的)网格压入堆栈。然后在 while 循环内(检查堆栈是否为空)，弹出顶部网格。检查网格是否完全填满。如果完全填满，则验证数独约束，如果满足则返回网格。如果网格未完全填充，则从中生成其他候选网格(可能没有)，这些网格都被压入堆栈。这总结了转换的想法，但当然它并不是真正有效。