Sudokuソルバーが遅い、先に制約を考慮する必要がある

Question

私はNxNのsudokuソルバーをプロローグで書いています。以下のコードは、4 * 4解決のためにうまく機能します。 （私はいくつかのドメイン情報を持っています）しかし、それは9x9のために遅いです。私は行の作成機能を改善するために多くの方法を試しました。行のすべての値が一意でなければならないことを既に考慮しています（ドメインに含める必要があります）。 ライブラリーなしでこれをどのように改善できますか？

all_distinct(X) :- 
    sort(X, Sorted), 
    length(X, OriginalLength), 
    length(Sorted, SortedLength), 
    OriginalLength == SortedLength. 

good_by_coulmns(Solution) :- length(Solution, Length), 
           forall((between(1, Length, X), get_column(Solution, X, Y)), 
           all_distinct(Y)). 
get_area(Solution, X, Y, Z) :- length(Solution, Length), 
           SQRootF is sqrt(Length), 
           SQRoot is round(SQRootF), 
           MinCol is SQRoot * (X-1) + 1, 
           MinRow is SQRoot * (Y-1) + 1, 
           matrix_block(MinRow, MinCol, SQRoot, SQRoot, Solution, A), flatten2(A,Z). 

good_by_areas(Solution) :- length(Solution, Length), 
          SQRootF is sqrt(Length), SQRoot is round(SQRootF), 
          forall((between(1, SQRoot, X), between(1, SQRoot, Y), get_area(Solution, X, Y, Z)), 
          all_distinct(Z)). 

createRow(Solution, Domain, Row) :- maplist(member, Row, Domain), 
            all_distinct(Row), 
            good_by_coulmns(Solution).%, write(Solution), nl. 

tryToSolve(Domains, Solution) :- length(Solution, L), length(Domains, L), !, 
           maplist(createRow(Solution), Domains, Solution), 
           good_by_coulmns(Solution), 
           good_by_areas(Solution). 

必要であれば、私は行方不明のルールを与えることができますが、これは細かいSOFAR働いているので、私たちは、ビルディングブロックとしてこれらを使用することができます。

Answer 1

質問はA.Iのプログラミングについてです。

さて、あなたのスドクがより速く動作するためには、いくつかの制約が必要です。しかし制約がありますので、私は数学的な形で説明し、書くことになります。コードをどのように実装したかによって異なります。

アイデア：基本的な考え方は、いくつかのスードクを与えれば、すぐにいくつかの場所を埋めることができるので、多くのブランチプログラムでは深刻な状態にならず、失敗して戻ってくるでしょう。下の図を見てください。この制約を置くと、各行に9つの要素があるため、6つの場所でプロローグの方法をブロックし、3つの場所でのみ許可することができます。多くの場合、青色にマークされたノードは探索されません。制約がなければ、最後まで探索され、探索するブランチの数が増えます。

どのように？

ルール：すべての行、すべてのcolumとユニークな要素を持っているすべてのグリッドは、私たちは、数独の特性を利用します。

アルゴリズム：与えられたときに、2つの行のいずれかに同じ要素がある場合、最初の3行（0,1,2）をチェックする必要があります。たとえば、最初の行のすべての要素について、その要素が2番目または3番目の行にあるかどうかをチェックし、次に2番目の行に移動し、2番目と3番目の行にある要素を見つけようとする必要があります。

一致するものがありません：最初の3行に同じ要素がない場合は、次の3行（3,4,5）に移動して見つけて、次に行（6、 7,8）。

注：グリッド（3x3マトリックス）を形成する線のみをチェックする必要があります。たとえば、行（0,1,2）が一緒に（3,4,5） 6,7,8）が一緒です。

一致するものがあります。行（0,2）に一致するものがあるとします。各行は一意の要素を持つことができるので、この要素が行1にあるはずですが、結果の行が1であることをどのように知っているのですか。次を参照してください：

数学形式：あなたは常に減算によって結果の行を得ることができます。行0と行2で一致しました。これらの3つの行が一緒になっているので、行番号（0 + 1 + 2 = 3）の合計を取っています。私たちは変数を扱うので、あなたは（i = 0とj = 2）で一致し、あなたの合計は= 3

とsum- i - j = 1 so the new element should be in row 1です。この式は常に有効である：あなたが行番号(i = 4 and j = 5)で試合を持っていると思い、これら3行番号

の合計が、私たちはどの行たちに知っておく必要があり4 + 5 + 6 = 15あると15 - 4 -5 = 5.は、しかし別の方法があるが、我々は変数で作業減算します他の2つの行に一致する要素を配置する必要があります。

グリッドの決定：新しい要素がある行を決定したら、次のステップはすべての行が3つのグリッド（3x3行列）の一部であるため、どのグリッドが存在するかをチェックすることです。例えば、行0は第1グリッドの要素（0,1,2）、次に第2グリッドの（3,4,5）、次に第3グリッドの要素（6,7,8）を有する。

サブグリッドは合計で（0〜8）です。

サブグリッドとローの関係：私たちはローについての情報しか持っていないので、ローとグリッドナンバーの関係を見つける必要があります。グリッドの高さがグリッドの幅（3x3）に等しいので、行の長さが9でグリッドの長さが3であるため、3つのグリッドが一緒に3つのグリッドを形成することを意味するNxNマトリックスです例：行（0,1,2）は、0,1,2から始まる3つのガードを形成し、次に、別の3つのグリッドから行（4,5,6）：gridnumber（4,5,6）を形成する。

行0では列番号2と列番号2の列が一致し、グリッド0とグリッド1（respt）を取得する必要があります。最初のグリッド。グリッド0（colum：0 1 2）である。

我々は1次元リスト内のグリッド数を取得するには、この式を使用

(mod(x,9)/3) + 3*(x/27)

我々ができるようになりましたこと、グリッド1と2を知っています」すべてのグリッドで1から9までの固有のelemenが必要なので、この要素があります。したがって、グリッド0でなければなりません結果のグリッドを得るにはどうすればよいのでしょうか？3つの行番号の合計（=行数はグリッドの数と等しいため）を= 3とし、他の2つのグリッドのグリッド数を引きます0 + 1）グリッド2を取得します。

私たちはまだ完成していません。私たちは主に1次元のリストで作業するので、このものを1つのインデックスに変換する必要があります。したがって、この式は、正確な場所を与える：

式：X =（newRow）* 9 +（newGrid）* 3とXが私たちの場所です。この数式は値を入れて確認できます。ここで要素を配置できる場所に正確な3つのスロットがあります。この時点で、リスト[x] =リスト[i]またはリスト[x + 1] =リスト[i]またはリスト[x + 2] =リスト[i]のいずれかと言う。