8

私はswi-prologについて少し学ぼうとしています（基本的な役に立たないプログラムを超えて）。

この数独ソルバーと関連する関数が何をしているのか、誰でも (おそらく疑似コードで) 説明できますか? さらに参照が必要な場合は、swi-prolog の CLP(FD) パッケージにあります。

ありがとう！

 :- use_module(library(clpfd)).
 sudoku(Rows) :-                                                   
         length(Rows, 9), maplist(length_(9), Rows),                
         append(Rows, Vs), Vs ins 1..9,                             
         maplist(all_distinct, Rows),                               
         transpose(Rows, Columns), maplist(all_distinct, Columns),  
         Rows = [A,B,C,D,E,F,G,H,I],                                
         blocks(A, B, C), blocks(D, E, F), blocks(G, H, I).         


 length_(L, Ls) :- length(Ls, L).                                   

 blocks([], [], []).                                                
 blocks([A,B,C|Bs1], [D,E,F|Bs2], [G,H,I|Bs3]) :-                   
         all_distinct([A,B,C,D,E,F,G,H,I]),                         
         blocks(Bs1, Bs2, Bs3).                                     


 problem(1, [[_,_,_,_,_,_,_,_,_],                                   
             [_,_,_,_,_,3,_,8,5],                                   
             [_,_,1,_,2,_,_,_,_],                                   
             [_,_,_,5,_,7,_,_,_],                                   
             [_,_,4,_,_,_,1,_,_],                                   
             [_,9,_,_,_,_,_,_,_],                                  
             [5,_,_,_,_,_,_,7,3],                                  
             [_,_,2,_,1,_,_,_,_],                                   
             [_,_,_,_,4,_,_,_,9]]).
4

3 に答える 3

11

Prologは、プログラムについての別の考え方です。論理的に考えなければなりません。

まず、B AND C AND D が true の場合、 A が true (成功) であるA :- B, C, Dことを意味します。

投稿したコードのスニペットは、数独パズルの正しさをチェックします。3 つの条件があります。

  • 要素はすべて行ごとに異なります
  • 要素はすべて列ごとに異なります
  • 要素はすべて 3x3 ブロックによって異なります

それはどのように機能しますか？

次の場合、sudoku(Rows) は true です。

  1. length(Rows, 9)-> 行に 9 つの要素があります
  2. maplist(_length(9), Rows)->maplistリスト (2 番目のパラメーター) のすべての要素の述語 (1 番目のパラメーター) をチェックします。これは、すべての行の長さが 9 でなければならないことを意味します。
  3. maplist(all_distinct, Rows)-> 前と同じですが、すべての行に個別の (ペアごとに等しくない) 要素があるかどうかを確認します。
  4. transpose(Rows, Columns), maplist(all_distinct, Columns)-> 行を列に転置して、垂直方向に選択することによって、それらがすべて異なるかどうかを確認します
  5. Rows = [A,B,C,D,E,F,G,H,I]-> 行リストを分割し、それぞれを別の変数 A、B、C、D に配置します ... したがって、A が最初の行、B が 2 番目の行などになります。
  6. blocks(A, B, C), blocks(D, E, F), blocks(G, H, I)-> この述語は、行のトリプレットに対して真でなければなりません。

その部分について話しましょうblocks、それは理解するのがとても面白いです。すべての 3x3 ブロックに個別の値が含まれていることを確認します。どうすればそれができますか？

3 つの行があると仮定すると、すべての行 (最初の 3x3 ブロック) の最初の 3 つの要素、4 番目から 6 番目 (2 番目のブロック) および 7 番目から 9 番目 (3 番目のブロック) の要素に対して条件が真でなければなりません。

したがって、再帰的に考えることができます:blocks([],[],[])自明に真であり、空のリストがあります。

AT LEAST 3 要素のリストであるパラメーターを使用して述語を呼び出すと、ケースblocks([A,B,C|Bs1],[D,E,F|Bs2],[G,H,I|Bs3])が選択されます。blocksしたがって、A、B、C、D、E、F、G、H、I がすべて異なるかどうかを確認しblocks、残りのリスト (最初の 3 つの要素を除く) をパラメーターとして使用して再帰的に呼び出します。これがプロローグの目的です！

最初blocksに 9 要素の 3 行で呼び出され、すべての行の最初の 3 つが異なることを確認し、6 要素の 3 つのリストで自分自身を呼び出し、もう一度チェックして 3 要素の 3 つのリストで自分自身を呼び出し、もう一度チェックして、 3 つの空のリストで自分自身を呼び出します (常に成功する些細なケース)。

于 2009-11-21T16:14:49.323 に答える
3

sudoku/1 は基本的に Sudoku ソリューションが満たさなければならない制約を記述しており、ボードは長さ 9 の 9 つのリストのリストとして表されます。problem/2 は、部分的にインスタンス化されたボードを問題番号に割り当てます。それを使用するには、次のことを行う必要があります

?- 問題 (1、ボード)、数独 (ボード)。

ドキュメントで使用されている述語をよく読んでください。

于 2009-11-20T18:31:37.013 に答える
2

「append(Rows, Vs), Vs ins 1..9」について

http://www.swi-prolog.org/pldoc/man?predicate=append%2F2

これは、リストのリストのすべての要素がドメイン内になければならないことを意味します1..9。

于 2011-07-22T17:29:23.063 に答える