Erlang でのバックトラック

StackOverflow https://stackoverflow.com/questions/1849223

  •  13-09-2019
  •  | 
  •  

質問

まず最初に私の英語について申し訳ありません。

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 つの解決策があります。両方とも書かなければなりません。最初の解決策に到達した後、バックトラッキング アルゴリズムを実装する必要がありますが、その作成方法がわかりません。

私の考えは、固定要素を fixlist と呼ばれる新しいリストに書き出すことです。これにより、複数の解決策のセルが [] に変更されます。

前述の例の場合、fixedlist は次のようになります。[[1]、[3]、[2]、[4]、[4]、[2]、[3]、[1]、[]、[4]、[1]、[]、[]、 [1]、[4]、[]]

ここから「サンプル」を取得し、解決リスト内で 1 に等しくない最小の長さを探し、このセルの最初の可能な数値を試し、それをその固定リストに入れます。ここではセルを更新し、それがまだ解ける数独であるかどうかをチェックするアルゴリズムを持っています。そうでない場合、一歩下がって新しいものを試す方法がわかりません。私はその疑似コードを知っており、命令型言語には使用できますが、erlang には使用できません。(prolog は実際にはバックトラック アルゴリズムを実装しましたが、erlang は実装しませんでした)

何か案が？

役に立ちましたか？

解決

Re:私の後戻り機能。

これらは、プロローグ エンジンに似たバックトラッキングおよび論理変数を処理するためのフレームワークを提供する一般的な関数です。プログラムのロジックを記述する関数 (述語) を提供する必要があります。プロローグで書くのと同じように記述すれば、それらを erlang に変換する方法を示すことができます。非常に簡単に言うと、次のように訳します。

p :- q, r, s.

プロローグで次のようなものに

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

ここでは無視します 全て 継続を除く他の引数。

これが何らかの助けになることを願っています。アルゴリズムを説明していただければ、翻訳をお手伝いできると申し上げましたが、私は良い例を探していました。もちろん、自分で行うこともできますが、これはある程度の助けになります。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top