Prologコードを操作する

Question

Linux端末でswiplのhttps://swish.swi-prolog.org/example/clpfd_queens.plというコードをこのページで実行しようとしています。

:- use_module(library(clpfd)). 

n_queens(N, Qs) :- 
    length(Qs, N), 
    Qs ins 1..N, 
    safe_queens(Qs). 

safe_queens([]). 
safe_queens([Q|Qs]) :- 
    safe_queens(Qs, Q, 1), 
    safe_queens(Qs). 

safe_queens([], _, _). 
safe_queens([Q|Qs], Q0, D0) :- 
    Q0 #\= Q, 
    abs(Q0 - Q) #\= D0, 
    D1 #= D0 + 1, 
    safe_queens(Qs, Q0, D1). 

次のコマンド作品：

?- n_queens(4, Qs), labeling([ff], Qs). 

それだけではないn_queens(4, Qs)：

?- n_queens(4, Qs). 
Qs = [_G1470, _G1473, _G1476, _G1479], 
_G1470 in 1..4, 
abs(_G1470-_G1479)#\=3, 
_G1470#\=_G1479, 
abs(_G1470-_G1476)#\=2, 
_G1470#\=_G1476, 
abs(_G1470-_G1473)#\=1, 
_G1470#\=_G1473, 
_G1479 in 1..4, 
abs(_G1476-_G1479)#\=1, 
_G1476#\=_G1479, 
abs(_G1473-_G1479)#\=2, 
_G1473#\=_G1479, 
_G1476 in 1..4, 
abs(_G1473-_G1476)#\=1, 
_G1473#\=_G1476, 
_G1473 in 1..4. 

はなぜlabeling部分がここで必要ですか？ labelingの部分がなくても適切な出力が得られますか？より多くの場合

、1は、ソリューションの最初の部分のみを取得します。

?- n_queens(20, Qs), labeling([ff], Qs). 
Qs = [1, 3, 5, 14, 17, 4, 16, 7, 12|...] ; 
Qs = [1, 3, 5, 18, 16, 4, 10, 7, 14|...] ; 
... 

どのようにしてより多くの完全なリストの出力を得ることができますか？また、ソリューションごとにスペースバーを押さなくても、どのようにすべての数値を集めることができますか？ご協力いただきありがとうございます。 それは制約プログラミングの問題は構築：

Answer 1

​​はがないがN女王のためのNは-queens問題を解決し、それがN変数（女王の列）を構築し、間の制約を追加しますこれらのクイーンズ：例えば、2つのクイーンは同じ行に置くことも、同じ対角線に置くこともできません。我々はより便利な出力に問題のある出力を書き換える場合我々は、これを参照してください。

A in 1..4, 
abs(A-D)#\=3, 
A#\=D, 
abs(A-C)#\=2, 
A#\=C, 
abs(A-B)#\=1, 
A#\=B, 
D in 1..4, 
abs(C-D)#\=1, 
C#\=D, 
abs(B-D)#\=2, 
B#\=D, 
C in 1..4, 
abs(B-C)#\=1, 
B#\=C, 
B in 1..4. 

だから我々は4人の女王（A、B、CとD）を参照してください。各クイーンはドメイン1..4にある必要があります。また、最初のクイーンAが最後のクイーンDと列を共有しないように、A #\= Dのような等しくない制約があります。最終的には、最初のクイーンAと3番目のクイーンCが2つの列（診断攻撃）を異ならないように、abs(A-C) #\= 2のような制約があります。

次にlabeling/2は実際問題を解決する：それは弛緩（ドメインを減らす）、ならびに（値又は変数の値のサブレンジをピッキング）分岐と制約が失敗した場合にバックトラックを行います。それは解決策が見つかるまで続き、Prologのバックトラッキングメカニズムを使用してlabeling/2にもっと多くのソリューションを考えさせることができます。

labelingは、変数のリストを与えられ、ラベルに向けられます。すべての制約が満たされるような範囲外の値を割り当てます。

したがって、問題の構築部が実際に解決する部分に比べて非常に高速で、通常です：O（N）変数とO（N ）制約を生成するのは簡単ですが、それは指数関数的に取ることができます時間量O（D ^N）は、すべての制約を満たす解を思い付く。

また、ソリューションごとにスペースバーを押さなくても、どのようにすべての数値を集めることができますか？

あなたはそのためのメタ述語findall/3を使用することができます。

all_n_queens(N,LL) :- 
    findall(L,(n_queens(N,L), labeling([ff], L)),LL).

生成する：

?- all_n_queens(5,LL). 
LL = [[1, 3, 5, 2, 4], [1, 4, 2, 5, 3], [2, 4, 1, 3, 5], [2, 5, 3, 1, 4], [3, 1, 4, 2|...], [3, 5, 2|...], [4, 1|...], [4|...], [...|...]|...]. 

をどのように1は、より多くの完全なリストの出力を得ることができますか？

あなたはanswer_write_optionsフラグを設定することができます

?- set_prolog_flag(answer_write_options,[max_depth(0)]). 
true. 

?- all_n_queens(5,LL). 
LL = [[1,3,5,2,4],[1,4,2,5,3],[2,4,1,3,5],[2,5,3,1,4],[3,1,4,2,5],[3,5,2,4,1],[4,1,3,5,2],[4,2,5,3,1],[5,2,4,1,3],[5,3,1,4,2]].