Erlang 中的回溯

Question

首先对我的英语感到抱歉。

我想在 Erlang 中使用回溯算法。它将作为解决部分填充数独的猜测。 9x9 数独存储为 81 个元素的列表，其中每个元素存储可以进入该单元格的可能数字。

对于 4x4 数独，我最初的解决方案如下所示： [[1],[3],[2],[4],[4],[2],[3],[1],[2,3],[4],[1],[2, 3],[2,3],[1],[4],[2,3]]

此数独有 2 个解。我必须把它们都写出来。达到初始解决方案后，我需要实现回溯算法，但我不知道如何实现。

我的想法是将固定元素写到一个名为“fixedlist”的新列表中，这会将多解决方案单元格更改为 []。

对于上面提到的示例，固定列表如下所示： [[1],[3],[2],[4],[4],[2],[3],[1],[],[4],[1],[],[], [1],[4],[]]

从这里我有一个“样本”，我在解决方案列表中查找不等于 1 的最小长度，然后尝试该单元格的第一个可能的数字并将其放入到那个固定列表。这里我有一个算法来更新单元格并检查它是否仍然是可解的数独。如果没有，我不知道如何退一步尝试新的。 我知道它的伪代码，我可以将它用于命令式语言，但不能用于 erlang。 （prolog 实际上实现了回溯算法，但 erlang 没有）

有什么想法吗？

Answer 1

回复：我的回溯功能。

这些是通用函数，它们提供了处理回溯和逻辑变量的框架，类似于序言引擎。您必须提供描述程序逻辑的函数（谓词）。如果你像在 prolog 中那样编写它们，我可以向你展示如何将它们翻译成 erlang。非常简单地，您将以下内容翻译为：

p :- q, r, s.

在序言中 为类似

p(Next0) ->
    Next1 = fun () -> s(Next0) end,
    Next2 = fun () -> r(Next1) end,
    q(Next2).

此处我忽略除延续之外的所有其他参数。

我希望这能提供一些帮助。正如我所说，如果你描述你的算法，我可以帮助你翻译它们，我一直在寻找一个很好的例子。当然，您也可以自己做，但这提供了一些帮助。