6

首先对不起我的英语。

我想在 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没有）

任何的想法？

4

2 回答 2

5

回复：我的回溯功能。

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

p :- q, r, s.

在序言中变成类似的东西

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

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

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

于 2009-12-04T22:12:54.670 回答
2

在 Robert Virding 的博客中查看这些文章：

http://rvirding.blogspot.com/2009/03/backtracking-in-erlang-part-1-control.html http://rvirding.blogspot.com/2009/04/backtracking-in-erlang-part-2 -passing.html

于 2009-12-04T20:38:58.583 回答