在Erlang中回溯

Question

首先抱歉我的英语.

我想在Erlang中使用回溯算法.它可以作为解决部分填充的sudokus的猜测.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).

在这里，我忽略了除了延续之外的所有其他论点。

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