制約プログラミングは、変数の範囲や変数間の関係を制約という形で宣言的に記述します。これがプログラムになり、それを「制約ソルバー」で実行し、制約を満たす解を探索します。制約プログラミングの分野としては、数理計画法 (Mathematical Programing)、制約充足問題 (CSP : Constraint Staisfaction Problem) や制約最適化問題 (COP : Constraint Optimization Problem) などがあります。
数理計画法は、変数に関する不等式や等式で表される制約の条件下で、目的の関数を最小 (あるいは最大) にする変数の値を求める問題です。特に、制約条件と目的関数が線形方程式で表される「線形計画法 (liner programming)」の分野では、「単体法 (simplex method)」という高速な解法アルゴリズムがあって、非常に広範囲な分野で使用されています。
また、変数の値が整数値しかとらない場合を「整数計画法 (integer programing)」といいます。特に、変数の値が 0 と 1 しかとらない場合を「0-1 整数計画法 (0-1 integer programming)」といいます。
CSP は、変数 xi の集合を X, xi の取り得る値 Diの集合を D, xi と xj の間の制約 Cij を表す集合を C とすると、X のすべての変数に対して制約 C をすべて満たす値の割り当てを求める問題になります。COP は制約をすべて満たした上で、ある値の最大値 (または最小値) を求める問題です。なお、整数計画法や CSP, COP は NP 問題になるので、変数の数や変数の領域 (domain) が大きくなると、現実的な時間で解を求めるのは大変困難になります。
制約論理プログラミングは 1987 年に IBM の Jaffer 氏と Lassez 氏によって理論化されました。これを CLP(X) といい、扱うデータによって次のように分類されます。
整数計画法や CSP の多くは CLP(FD) の範囲で取り扱うことができると思われます。本ページでは、これらの問題をメインに取り上げることにします。
それでは、clpfd を使ってみましょう。まず最初に、ライブラリ clpfd をロードしてください。
?- use_module(library(clpfd)). true. ?-
clpfd で求めることができるデータ型は整数だけです。制約を記述する一番簡単な方法は次に示す演算子を使うことです。
#=, #\=, #<, #=<, #>, #>=
これらの演算子は Prolog の演算子 =:=, =\=, <, =<, >, >= に対応しています。演算子の左辺式と右辺式は、変数や整数のほかに、次に示す算術演算子や関数を使うことができます。
+, -, *, //, mod, rem % 算術演算子 (// は整数の除算) abs(Expr) % 絶対値 min(Expr1, Expr2) % 最小値 max(Expr1, Expr2) % 最大値
関数の引数 Expr は式を表します。簡単な使用例を示しましょう。
?- X #> 0, X #=< 10. X in 1..10. ?-
これで変数 X の値は 1 から 10 までになります。解が複数ある場合、clpfd は変数の範囲や制約を返します。解が見つからない場合は false を返します。
X in 1..10. の in は変数の領域 (範囲, domain) を表す述語として使用することができます。
X in n .. m X in 数値 X in 範囲１ \/ 範囲２
X in n .. m は変数 X の範囲が n 以上 m 以下であることを表します。範囲は数値ををひとつ指定するだけでもかまいません。また、演算子 \/ で範囲をつなぐこともできます。この場合、X の範囲は範囲１と範囲２の和集合になります。\/ は複数つなげることもできます。
複数の変数に同じ領域を割り当てる場合は述語 ins を使います。
[変数, ...] ins 範囲
簡単な使用例を示しましょう。
?- X #= Y, X in 1 .. 3 \/ 6 .. 9, Y in 3. X = Y, Y = 3. ?- X #= Y, X in 1 .. 3 \/ 6 .. 9, Y in 6. X = Y, Y = 6. ?- X #= Y, X in 1 .. 3 \/ 6 .. 9, Y in 5. false. ?- X #= 2 * Y, [X, Y] ins 1 .. 3. X = 2, Y = 1. ?- X #= 4 * Y, [X, Y] ins 1 .. 3. false. ?- X #= Y, [X, Y] ins 1 .. 3. X = Y, Y in 1..3. ?-
解を探索する場合は述語 label を使います。
?- X in 1 .. 4, label([X]). X = 1 ; X = 2 ; X = 3 ; X = 4. ?- X #= Y, [X, Y] ins 1 .. 3, label([X,Y]). X = Y, Y = 1 ; X = Y, Y = 2 ; X = Y, Y = 3. ?-
label の引数はリストで、その中に値を求める変数を指定します。これで制約ソルバーを起動して解を探索します。
今まで説明したことだけで「鶴亀算」を解くことができます。
問題 1 は次の連立方程式を解けば求めることができます。
x + y = 100 2x + 4y = 272
?- X + Y #= 100, 2 * X + 4 * Y #= 272, [X, Y] ins 1..100. X = 64, Y = 36. ?-
問題 2 は次の連立方程式を解けば求めることができます。
x + y + z = 10 2x + 4y + 6z = 38 2x + 4z = 14
?- X + Y + Z #= 10, 2*X + 4*Y + 6*Z #= 38, 2*X + 4*Z #= 14, [X,Y,Z] ins 1..10. X in 1..5, X+2*Z#=7, X+2*Y+3*Z#=19, X+Y+Z#=10, Z in 1..3, Y in 3..7. ?- X + Y + Z #= 10, 2*X + 4*Y + 6*Z #= 38, 2*X + 4*Z #= 14, [X,Y,Z] ins 1..10, label([X,Y,Z]). X = 3, Y = 5, Z = 2 ; false. ?-
問題 3 は答えを 1 つに決めることはできませんが、制約を満たす解をすべて求めることができます。
?- X + Y + Z #= 24, 2*X + 4*Y + 8*Z #= 102, [X,Y,Z] ins 1 .. 24, label([X,Y,Z]). X = 1, Y = 21, Z = 2 ; X = Z, Z = 3, Y = 18 ; X = 5, Y = 15, Z = 4 ; X = 7, Y = 12, Z = 5 ; X = Y, Y = 9, Z = 6 ; X = 11, Y = 6, Z = 7 ; X = 13, Y = 3, Z = 8 ; false. ?-
正整数の範囲では、全部で 7 通りの解があります。
clpfd を使うと、簡単に順列を生成することができます。たとえば、1, 2, 3 の順列は次のように求めることができます。
?- Xs = [X, Y, Z], Xs ins 1..3, X #\= Y, X #\= Z, Y #\= Z, label(Xs). Xs = [1, 2, 3], X = 1, Y = 2, Z = 3 ; Xs = [1, 3, 2], X = 1, Y = 3, Z = 2 ; Xs = [2, 1, 3], X = 2, Y = 1, Z = 3 ; Xs = [2, 3, 1], X = 2, Y = 3, Z = 1 ; Xs = [3, 1, 2], X = 3, Y = 1, Z = 2 ; Xs = [3, 2, 1], X = 3, Y = 2, Z = 1. ?-
Xs にリスト [X, Y, Z] をマッチングさせ、X, Y, Z の範囲を ins で 1 から 3 に指定します。順列の条件は X, Y, Z で同じ値が出現しないことなので、その条件を演算子 #\= で指定します。これで順列を生成することができます。
ところで、変数 X, Y, Z をいちいち指定するのは面倒ですね。Xs の要素は無名変数でもいいはずです。このような場合、述語 length/2 を使うと便利です。
?- length(X, 5). X = [_, _, _, _, _]. ?- length(X, Y). X = [], Y = 0 ; X = [_], Y = 1 ; X = [_, _], Y = 2 ; X = [_, _, _], Y = 3 ; X = [_, _, _, _], Y = 4 ; X = [_, _, _, _, _], Y = 5 . ?-
append/2 や member/2 と同じく、length/2 も双方向の使い方ができます。
length/2 でリストを生成しても、一つ一つの変数に制約を指定できないと、順列を生成することはできませんね。この場合、cplfd に定義されている述語 all_different を使います。all_different は、引数のリストの要素がすべて異なっているとき成功します。
?- all_different([1,2,3]). true. ?- all_different([1,2,1]). false. ?-
リストの要素が自由変数の場合、all_different で変数の値がすべて異なるという制約を表すことができます。この述語を使うと、次のように順列を簡単に生成することができます。
?- length(Xs, 3), all_different(Xs), Xs ins 1..3, label(Xs). Xs = [1, 2, 3] ; Xs = [1, 3, 2] ; Xs = [2, 1, 3] ; Xs = [2, 3, 1] ; Xs = [3, 1, 2] ; Xs = [3, 2, 1]. ?-
組み合わせを生成する場合は、all_different のかわりに述語 chain/2 を使います。
chain(Xs, Pred).
chain/2 は Xs の隣り合ったすべての要素が述語 Pred を満たすとき成功します。なお、Pred に渡すことができる述語は #=, #=<, #>=, #<, #> だけです。
簡単な使用例を示しましょう。
?- chain([1,2,3], #<). true. ?- chain([1,2,3], #>). false. ?- chain([1,1,1], #=). true. ?-
chain を使うと、リストの隣り合った要素が Pred を満たす、という制約を簡単に表すことができます。組み合わせの生成は次のようになります。
?- length(Xs, 3), chain(Xs, #<), Xs ins 1..5, label(Xs). Xs = [1, 2, 3] ; Xs = [1, 2, 4] ; Xs = [1, 2, 5] ; Xs = [1, 3, 4] ; Xs = [1, 3, 5] ; Xs = [1, 4, 5] ; Xs = [2, 3, 4] ; Xs = [2, 3, 5] ; Xs = [2, 4, 5] ; Xs = [3, 4, 5]. ?-
chain/2 の第 2 引数に #< を渡せば、異なる値が昇順に並ぶことになり、組み合わせを簡単に生成することができます。
ここで簡単な例題を示しましょう。clpfd のマニュアルには覆面算 SEND + MORE = MONEY を解くサンプルプログラムがあるので、今回は次の覆面算を解くプログラムを作ってみましょう。なお、使用する数字は 1 から 9 までとします。
W R O N G
* M
-------------
R I G H T
図 : 小町覆面算
リスト : 小町覆面算 (hukumen1.pl)
:- use_module(library(clpfd)).
hukumen_solver :-
Xs = [W, R, O, N, G, M, I, H, T],
Xs ins 1..9,
all_different(Xs),
Wrong #= 10000*W + 1000*R + 100*O + 10*N + G,
Right #= 10000*R + 1000*I + 100*G + 10*H + T,
Wrong * M #= Right,
label(Xs),
format('~d * ~d = ~d~n', [Wrong, M, Right]),
fail.
プログラムは簡単で、1 から 9 までの数字の縦列を生成し、それが制約 Wrong * M = Right を満たしているかチェックするだけです。なお、clpfd を使ったプログラムでは、演算子 is を使うことはできません。is のかわりに #= を使ってください。
実行結果は次のようになります。
?- [hukumen1]. true. ?- hukumen_solver. 16958 * 4 = 67832 false. ?-
答えは 16958 * 4 = 67832 の 1 通りです。
もう一つ簡単な例題として、3 行 3 列の魔方陣を解くプログラムを作ってみましょう。
┌─┬─┬─┐ 式
│Ａ│Ｂ│Ｃ│ A + B + C = N, A + E + I = N
├─┼─┼─┤ D + E + F = N, C + E + G = N
│Ｄ│Ｅ│Ｆ│ G + H + I = N
├─┼─┼─┤ A + D + G = N
│Ｇ│Ｈ│Ｉ│ B + E + H = N
└─┴─┴─┘ C + F + I = N
図 : 魔方陣
上図の A から I の場所に 1 から 9 までの数字をひとつずつ配置します。縦横斜めの合計が等しくなるように数字を配置してください。
リスト : 魔方陣 (magic1.pl)
:- use_module(library(clpfd)).
mahou(Xs) :-
Xs = [A, B, C, D, E, F, G, H, I],
Xs ins 1..9,
all_different(Xs),
N #= A + B + C,
N #= D + E + F,
N #= G + H + I,
N #= A + D + G,
N #= B + E + H,
N #= C + F + I,
N #= A + E + I,
N #= C + E + G.
プログラムは単純な生成検定法と同じで、順列を生成して 8 本の直線の値が等しいかチェックするだけです。
実行結果は次のようになります。
?- time((mahou(Ans), label(Ans), write(Ans), nl, fail)). [2,7,6,9,5,1,4,3,8] [2,9,4,7,5,3,6,1,8] [4,3,8,9,5,1,2,7,6] [4,9,2,3,5,7,8,1,6] [6,1,8,7,5,3,2,9,4] [6,7,2,1,5,9,8,3,4] [8,1,6,3,5,7,4,9,2] [8,3,4,1,5,9,6,7,2] % 2,031,346 inferences, 0.221 CPU in 0.221 seconds (100% CPU, 9203417 Lips) false. ?-
解は 8 通り出力されましたが、重複解を取り除くと解は一通りしかありません。重複解のチェックは面倒だと思われる方もいるでしょう。ところが、下図のように四隅の大小関係を利用すると簡単です。
┌─┬─┬─┐
│Ａ│Ｂ│Ｃ│
├─┼─┼─┤ A < C < G
│Ｄ│Ｅ│Ｆ│
├─┼─┼─┤ A < I
│Ｇ│Ｈ│Ｉ│
└─┴─┴─┘
図 : 対称解のチェック
魔方陣の場合、回転解が 4 種類あって、鏡像解が 2 種類あります。四隅の大小関係をチェックすることで、これらの対称解を排除することができます。また、重複解のチェックを入れると枝刈りと同じ効果を得ることができます。CLPFD ならば、次のように制約条件を付け加えるだけです。
リスト : 魔方陣 (改)
mahou(Xs) :-
Xs = [A, B, C, D, E, F, G, H, I],
Xs ins 1..9,
all_different(Xs),
N #= A + B + C,
N #= D + E + F,
N #= G + H + I,
N #= A + D + G,
N #= B + E + H,
N #= C + F + I,
N #= A + E + I,
N #= C + E + G,
A #< C,
C #< G,
A #< I.
最後に、A #< C, C #< G, A #< I を付け加えているだけです。実行結果は次のようになります。
?- time((mahou(Ans), label(Ans), write(Ans), nl, fail)). [2,9,4,7,5,3,6,1,8] % 390,564 inferences, 0.044 CPU in 0.044 seconds (100% CPU, 8888231 Lips) false. ?-
制約を加えるだけでプログラムを簡単に改良できるなんて、制約プログラミングは面白いなあと思いました。興味のある方はいろいろ試してみてください。
次は clpfd の論理演算について説明します。cplfd の論理演算子は与えられた式を実行し、評価結果 (成功 / 失敗) を整数値 (0: 偽, 1: 真) に置き換えてから論理演算を行います。その結果が真 (1) であれば成功、偽 (0) であれば失敗となります。式には真偽値 (0 or 1) をそのまま与えてもかまいません。また、自由変数を渡すこともできます。その場合、変数の値は 0 または 1 のどちらかになります。
cplfd に用意されている論理演算子と真理値表を示します。
#\ Q : 否定, Not Q P #/\ Q : 論理積, P And Q P #\/ Q : 論理和, P Or Q P #\ Q : 排他的論理和, P Xor Q P #<==> Q : 同値, P Iff Q P #==> Q : 含意 (論理包含), P Imp Q P #<== Q : 含意 (論理包含), Q Imp P
真理値表
P : 0 0 1 1
Q : 0 1 0 1
--------+---------
Not P : 1 1 0 0
Not Q : 1 0 1 0
P And Q : 0 0 0 1
P Or Q : 0 1 1 1
P Xor Q : 0 1 1 0
P Iff Q : 1 0 0 1
P Imp Q : 1 1 0 1
Q Imp P : 1 0 1 1
これらの中で同値 (equivalence) や含意 (implication) はあまり見慣れない論理演算だと思います。同値は P と Q が同じ値 (0 と 0 または 1 と 1) のとき真となります。Iff は「if and only if」を略したものだそうです。P Imp Q は P が真ならば Q の結果に、P が偽ならば Q の結果にかかわらず真となります。詳しい説明は参考 URL 『同値 - Wikipedia』, 『論理包含 - Wikipedia』 をお読みくださいませ。
同値と含意の動作例を示します。
?- P #<==> Q, label([P, Q]). P = Q, Q = 0 ; P = Q, Q = 1. ?- P #==> Q, label([P, Q]). P = Q, Q = 0 ; P = 0, Q = 1 ; P = Q, Q = 1. ?- P #<== Q, label([P, Q]). P = Q, Q = 0 ; P = 1, Q = 0 ; P = Q, Q = 1. ?-
Prolog の場合、規則の体部は連言 (And) で、規則の定義が選言 (Or) に相当します。体部で制約を記述するとき、同値や含意を使ったほうが簡単にプログラムできることがあります。これは実際に使うところで説明しましょう。
ところで、否定は変数の領域にも適用することができます。簡単な例を示しましょう。
?- X #= 3. X = 3. ?- #\ X #= 3. X in inf..2\/4..sup. ?- #\ X in 1..4. X in inf..0\/5..sup. ?-
inf は負の無限大、sup は正の無限大を表します。
それでは簡単な例題として論理パズルを解いてみましょう。
３人の友達が、あるプログラミング競技会で１位、２位、３位になった。この３人は、名前も、好きなスポーツも、国籍も異なる。Michael はバスケットが好きで、アメリカ人よりも上位であった。イスラエル人の Simon はテニスをする者よりも上位であった。クリケットをするものが１位であった。誰がオーストラリア人か？ Richard はどのようなスポーツをするか？
拙作のページ「お気楽 Prolog プログラミング入門」では、論理パズルを取り上げたことがなかったので、まず最初に clpfd を使わないでプログラムを作ってみましょう。なお、clpfd を使ったプログラムと比較しやすいように、「Prolog の技芸」のプログラムよりも単純なプログラムを作ります。興味のある方は「Prolog の技芸」のプログラムと比較してみてください。
最初にデータ構造とそれを生成する述語を定義します。データは複合項で表します。
person(順位, 国籍, スポーツ).
このデータを述語 make_person で作成します。次のリストを見てください。
リスト : データの作成 % 国 nation(us). nation(il). nation(au). % スポーツ sports(tennis). sports(cricket). sports(basket). % 順位 rank(1). rank(2). rank(3). % データの作成 make_person(person(R, N, S)) :- rank(R), nation(N), sports(S).
順位を rank (1, 2, 3)、国籍を nation (us, il, au)、スポーツを sports (basket, cricket, tennis) で定義します。make_person では rank(R), natio(N), sports(S) で要素を一つ選びます。バックトラックすると異なる要素が選ばれて、新しいデータが生成されます。
それでは実際に試してみましょう。
?- make_person(X). X = person(1, us, tennis) ; X = person(1, us, cricket) ; X = person(1, us, basket) ; X = person(1, il, tennis) ; X = person(1, il, cricket) ; X = person(1, il, basket) . ?-
正常に動作していますね。
次は問題を解くための補助的な述語を作ります。
リスト : 補助的な述語の定義
% 3 つのデータが全部異なる
check_data(person(A, B, C),
person(D, E, F),
person(G, H, I)) :-
A \== D, A \== G, D \== G,
B \== E, B \== H, E \== H,
C \== F, C \== I, F \== I.
% アクセス用述語
get_rank(person(A, _, _), A).
get_nation(person(_, B, _), B).
get_sports(person(_, _, C), C).
% 検索
search_sports(S, [person(R, N, S) | _], person(R, N, S)) :- !.
search_sports(S, [_| Ps], P) :- search_sports(S, Ps, P).
search_nation(N, [person(R, N, S) | _], person(R, N, S)) :- !.
search_nation(N, [_| Ps], P) :- search_nation(N, Ps, P).
述語 check_data は 3 人のデータを受け取り、順位、国籍、スポーツの中で、重複したデータがないかチェックします。述語 get_rank, get_nation, get_sports は person() から順位、国籍、スポーツを取り出します。述語 search_sports はリストからスポーツ S が好きな人のデータを返します。述語 search_nation はリストから国籍が N の人のデータを返します。
論理パズルの解法プログラムは次のようになります。
リスト : 論理パズルの解法
solver :-
make_person(M), % Michel
make_person(S), % Simon
make_person(R), % Richard
check_data(M, S, R),
get_sports(M, Ms),
Ms == basket, % 条件 1
get_nation(M, Mn),
Mn \== us, % 条件 2
search_nation(us, [M,S,R], U),
get_rank(U, Ur),
get_rank(M, Mr),
Mr < Ur, % 条件 3
get_nation(S, Sn),
Sn == il, % 条件 4
search_sports(tennis, [M,S,R], T),
get_rank(S, Sr),
get_rank(T, Tr),
Sr < Tr, % 条件 5
search_sports(cricket, [M,S,R], C),
get_rank(C, Cr),
Cr =:= 1, % 条件 6
writeln(M),
writeln(S),
writeln(R),
nl,
fail.
最初に make_person でデータを作成し、変数 M (Michel), S (Simon), R (Richard) にセットします。そして、check_data で順位、国籍、スポーツで要素が重複していないかチェックします。あとは問題の条件をチェックしていくだけです。
条件を満たさない場合はバックトラックして新しいデータを生成します。最後に、見つけた解を出力します。単純な生成検定法のプログラムですね。実行結果は次のようになります。
?- solver. person(2,au,basket) person(1,il,cricket) person(3,us,tennis) false.
解は 1 通りで、１位が Simon, ２位が Michael, ３位が Richard になります。
次は clpfd を使ってプログラムを作りましょう。プログラムは次のようになります。
リスト : 論理パズル (clpfd 版)
:- use_module(library(clpfd)).
solver :-
M = [Mr, Mn, Ms], % Michel
S = [Sr, Sn, Ss], % Simon
R = [Rr, Rn, Rs], % Richard
% 順位の設定
Rank = [Mr, Sr, Rr],
Rank ins 1 .. 3,
all_different(Rank),
% 国籍の設定 (4: US, 5: IL, 6: AU)
Nation = [Mn, Sn, Rn],
Nation ins 4 .. 6,
all_different(Nation),
% スポーツの設定 (7: basket, 8: tennis, 9: cricket)
Sports = [Ms, Ss, Rs],
Sports ins 7 .. 9,
all_different(Sports),
% 条件のチェック
Ms #= 7, % 条件 1
Mn #\= 4, % 条件 2
Sn #= 4 #==> Sr #> Mr, % 条件 3
Rn #= 4 #==> Rr #> Mr,
Sn #= 5, % 条件 4
Ms #= 8 #==> Mr #> Sr, % 条件 5
Rs #= 8 #==> Rr #> Sr,
Ms #= 9 #==> Mr #= 1, % 条件 6
Ss #= 9 #==> Sr #= 1,
Rs #= 9 #==> Rr #= 1,
label(M),
label(S),
label(R),
writeln(M),
writeln(S),
writeln(R),
fail.
変数 M, S, R にはランク、国籍、スポーツを格納したリストをセットします。順位、国籍、スポーツの設定は all_different を使えば簡単です。条件のチェックも簡単です。条件 3 は Imp を 2 つ並べるだけです。Simon が US であれば、右辺式をチェックします。左辺が偽であれば Imp は無条件に成功するので、次の制約である Richard が US かチェックします。Prolog の場合、体部は連言 (And) なのですが、Imp を使えば条件を並べるだけで簡単に制約を記述することができます。条件 5, 6 も同じです。
実行結果は次のようになります。
?- solver. [2,6,7] [1,5,9] [3,4,8] false. ?-
最後にもう一つ、簡単な論理パズルを出題しましょう。
Baker, Cooper, Fletcher, Miller と Smith は五階建てアパートの異る階に住んでいる。Baker は最上階に住むのではない。Cooper は最下階に住むのではない。Fletcher は最上階にも最下階にも住むのではない。Miller は Cooper より上の階に住んでいる。Smith は Fletcher の隣の階に住むのではない。Fletcher は Cooper の隣の階に住むのではない。それぞれはどの階に住んでいるか。
この問題は clpfd を使わなくても簡単にプログラムすることができます。興味のある方は挑戦してみてください。
リスト : 論理パズルの解法 (Prolog 版)
% 国
nation(us).
nation(il).
nation(au).
% スポーツ
sports(tennis).
sports(cricket).
sports(basket).
% 順位
rank(1).
rank(2).
rank(3).
% データの作成
make_person(person(R, N, S)) :- rank(R), nation(N), sports(S).
% 3 つのデータが全部異なる
check_data(person(A, B, C),
person(D, E, F),
person(G, H, I)) :-
A \== D, A \== G, D \== G,
B \== E, B \== H, E \== H,
C \== F, C \== I, F \== I.
% アクセス用述語
get_rank(person(A, _, _), A).
get_nation(person(_, B, _), B).
get_sports(person(_, _, C), C).
% 検索
search_sports(S, [person(R, N, S) | _], person(R, N, S)) :- !.
search_sports(S, [_| Ps], P) :- search_sports(S, Ps, P).
search_nation(N, [person(R, N, S) | _], person(R, N, S)) :- !.
search_nation(N, [_| Ps], P) :- search_nation(N, Ps, P).
% 解法
solver :-
make_person(M), % Michel
make_person(S), % Simon
make_person(R), % Richard
check_data(M, S, R),
get_sports(M, Ms),
Ms == basket,
get_nation(M, Mn),
Mn \== us,
search_nation(us, [M, S, R], U),
get_rank(U, Ur),
get_rank(M, Mr),
Mr < Ur,
get_nation(S, Sn),
Sn == il,
search_sports(tennis, [M, S, R], T),
get_rank(S, Sr),
get_rank(T, Tr),
Sr < Tr,
search_sports(cricket, [M, S, R], C),
get_rank(C, Cr),
Cr =:= 1,
writeln(M),
writeln(S),
writeln(R),
nl,
fail.
リスト : 論理パズル (Dinesman, 1968)
:- use_module(library(clpfd)).
% Prolog 版
solver :-
Ps = [Baker, Cooper, Fletcher, Miller, Smith],
permutation([1,2,3,4,5], Ps),
Baker =\= 5,
Cooper =\= 1,
Fletcher =\= 5,
Fletcher =\= 1,
Miller > Cooper,
abs(Smith - Fletcher) =\= 1,
abs(Fletcher - Cooper) =\= 1,
writeln(Ps),
nl,
fail.
% clpfd 版
solver1 :-
Ps = [Baker, Cooper, Fletcher, Miller, Smith],
Ps ins 1 .. 5,
all_different(Ps),
Baker #\= 5,
Cooper #\= 1,
Fletcher #\= 5,
Fletcher #\= 1,
Miller #> Cooper,
abs(Smith - Fletcher) #\= 1,
abs(Fletcher - Cooper) #\= 1,
label(Ps),
writeln(Ps),
nl,
fail.
?- solver. [3,2,4,5,1] false. ?- solver1. [3,2,4,5,1] false. ?-