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に等しくない最小の長さを探し、このセルの最初の可能な数を試し、それをその固定リストに入れます。ここに、セルを更新して、それがまだ解決可能な数独であるかどうかをチェックするアルゴリズムがあります。そうでなければ、私は1つを後退させて新しいものを試す方法がわかりません。私はそれの擬似コードを知っており、命令型言語には使用できますが、erlangには使用できません。（prologは実際にバックトラックアルゴリズムを実装しましたが、erlangは実装しませんでした）

何か案が？

4

2 に答える 2

5

Re: 私のバックトラッキング機能。

これらは、プロローグ エンジンに似たバック トラッキングと論理変数を処理するためのフレームワークを提供する一般的な関数です。プログラム ロジックを記述する関数 (述語) を指定する必要があります。プロローグと同じように記述すれば、それらを 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 に答える