Erlang回溯

Question

首先感謝我的英語。

我想在Erlang中使用回溯算法。它可以作爲解決部分填充的數獨問題的猜測。 9×9的數獨被存儲爲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]，[我從這裏有一個「樣本」，我尋找解決方案列表中的最低長度，它是不等於1，我嘗試了這個單元格的第一個可能的數字，然後把它放到那個固定列表中。在這裏我有一個算法來更新單元格，並檢查它是否仍然是可以解決的數獨問題。如果不是，我不知道如何退後一步並嘗試新的。 我知道它的僞代碼，我可以將它用於命令式語言，但不能用於erlang。 （prolog實際上實現了回溯算法，但erlang沒有）

任何想法？

Answer 1

回覆：我bactracking功能。

這些是一般函數，它提供了一個處理類似於prolog引擎的回溯和邏輯變量的框架。您必須提供描述程序邏輯的函數（謂詞）。如果你像在序言中那樣編寫它們，我可以告訴你如何將它們翻譯成erlang。簡單地說你翻譯是這樣的：在序言

p :- q, r, s. 

成類似

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

這裏我忽略除延續所有其他參數。

我希望這能提供一些幫助。正如我所說，如果你描述你的算法，我可以幫你翻譯它們，我一直在尋找一個很好的例子。當然，你也可以自己做，但這會提供一些幫助。

Answer 2

查覈在羅伯特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