Prolog には「差分リスト (difference list)」という独自のデータ構造があります。差分リストという特別なデータ型があるわけではありません。普通のリストには違いないのですが、考え方がちょっとひねくれています。
例として [a, b, c] というリストを考えてみましょう。このリストを 2 つのリストの違いで表してみます。[a, b, c, d, e] から [d, e] を取り除くと [a, b, c] になりますね。また、[a, b, c, f] から [f]、もしくは [a, b, c] から [ ] を取り除いても [a, b, c] を表すことができます。
このように、2 つのリストの差分 [Xs, Ys] で一つのリストを表すことから、差分リストと呼ばれているのです。Xs を差分リストの「頭部」、Ys を差分リストの「尾部」と呼びます。次に示すリストは、すべて [a, b, c] というリストを表しています。
[ [a, b, c, d, e], [d, e] ] [ [a, b, c, f], [f] ] [ [a, b, c], [ ] ] [ [a, b, c | X], X]
最後の例のように、変数を使って差分リストを表現する方法はとくに重要です。変数は何にでもマッチングしますので、上記の 3 つの例はすべて最後の例とマッチングします。
?- [[a, b, c, d, e], [d, e]] = [[a , b, c | X], X]. X = [d, e]. ?- [[a, b, c, f], [f]] = [[a , b, c | X], X]. X = [f]. ?- [[a, b, c], []] = [[a , b, c | X], X]. X = []. ?-
= はマッチングを行う述語です。一般に差分リストを使う場合、差分を表すデータには興味がありませんから、最後の例のように変数を使って表します。
差分リストは、通常のリストに比べてリスト操作が簡単になる、という利点があります。簡単な例題として、差分リストを結合する述語 append_dl を作ってみましょう。第 1 引数と第 2 引数に結合する差分リストを与え、第 3 引数に結果を求めます。リストの結合 append に比べて簡単に定義することができます。
リスト : 差分リストの結合 append_dl([Xs, Ys], [Ys, Zs], [Xs, Zs]).
差分リストを連結する場合、第 1 引数の尾部と第 2 引数の頭部がマッチングしないといけません。Ys が連結器の役割をしていると考えればいいでしょう。それでは実行してみます。
?- append_dl([[a, b, c | X], X], [[d, e | Y], Y], Z). X = [d, e|Y], Z = [[a, b, c, d, e|Y], Y]. ?-
変数 Z には、2 つの差分リストを連結した差分リストが求まっていますね。それでは、プログラムの動作を詳しく説明しましょう。差分リストのポイントは、Prolog の特徴である「自由変数同士のパターンマッチングは成功する」ことにあります。まず、第 1 引数のマッチングを見てみましょう。
[[a, b, c | X], X] = [Xs ,Ys]. Xs = [a, b, c | X] Ys = X
X と Ys は自由変数なので、パターンマッチングに成功します。この場合、X と Ys は自由変数のままであることに注意してください。したがって、X か Ys のどちらかがパターンマッチングに成功すれば、X と Ys の値が定まることになります。次に、第 2 引数のマッチングを見てみましょう。
[[d, e | Y], Y] = [Ys, Zs]. Ys = [d, e | Y] Zs = Y
Y と Zs は自由変数のままです。Ys がマッチングしたので、X の値が [d, e | Zs] になって、Xs の値は [a, b, c, d, e | Zs] となります。Y と Zs は自由変数のままです。 最後に、第 3 引数のマッチングを見てみましょう。
Z = [Xs, Zs]. => [[a, b, c, d, e | Zs], Zs]
Zs は自由変数のままです。変数 Y は Zs のことです。プログラムをコンパイルすると、変数名は Prolog の都合のいいように変換されます。このように、差分リストは自由変数の性質を上手に使っていて、Prolog らしいデータ構造といえるでしょう。
実際に差分リストを使う場合は、このような述語を使わずに直接リストを操作します。簡単な例題として、リストから整数を取り出す述語 take_integer を、差分リストを使って書き直してみましょう。
リスト : take_integer (差分リスト版)
take_integer(X, Y) :- take_int_sub(X, [Y, []]).
take_int_sub([X | Xs], [Ys, Zs]) :-
take_int_sub(X, [Ys, Ys1]), take_int_sub(Xs, [Ys1, Zs]), !.
take_int_sub(X, [[X | Xs], Xs]) :- integer(X), !.
take_int_sub(X, [Ys, Ys]).
take_int_sub は差分リストを使ってリストを結合します。take-integer はその結果を取り出します。take_int_sub の第 2 引数が差分リストです。3 行目の差分リスト [Ys, Ys1] と [Ys1, Zs] を、2 行目の [Ys, Zs] で結合します。この場合、Ys1 が連結器の役割をしています。
3 番目の規則で、X が整数の場合には、要素が一つの差分リストを作ります。最後の規則で、整数以外のデータは空の差分リストを作ります。差分リストは、頭部と尾部が等しい場合が空になりますので、[Ys, Ys] となります。
それでは実行してみましょう。
?- take_integer([a, 1, [b, 2]], Z). Z = [1, 2]. ?-
正常に動作していますね。リストを結合する場合、append よりも差分リストを使った方が効率は良くなります。リストを分解して再構築するプログラムでは、差分リストを使ってみるといいでしょう。
Prolog は、バックトラックすることで、すべての解を見つけることができます。それでは、バックトラックによって見つけた解を、リストにまとめたい場合はどうするのでしょうか。たとえば、拙作のページ「簡単な例題 : 家系図」で示した家系図を例に考えてみましょう。
┌─── 三郎
幸子 │
┃──┤
┌── 一郎 │
太郎 │ └─── 洋子
┃──┼── 次郎
花子 │
└── 友子
図：家系図
父親 X の子供をすべてリスト Ls に求めようとして、次のようなプログラムを作りました。
リスト : 父親 X の子供をすべて L に求める all_children(X, Ls) :- children_sub(X, [], Ls). children_sub(X, C, Ls) :- father_of(X, C1), not(member(C1, C)), !, children_sub(X, [C1 | C], Ls). children_sub(_, Ls, Ls).
2 番目の規則で、father_of(X, C1) が成功する間は、第 2 引数のリストに子供を追加していきます。このとき、member を使って解が重複していないかチェックします。それでは実行してみましょう。
?- all_children(taro, L). L = [tomoko, jiro, ichiro]. ?- all_children(ichiro, L). L = [youko, saburo]. ?-
父親の名前を指定すると、うまく動作します。それでは、父親を変数にすると、どうなるでしょうか。実際に試してみましょう。
?- all_children(X, L). X = taro, L = [tomoko, jiro, ichiro]. ?-
父親が一郎の場合の関係を求めることができません。カットをはずすとバックトラックすることはできますが、正しい解を求めることはできません。また、バックトラックしたとしても、このままでは、すべての解をリストにまとめるということはできません。
このような場合、findall という述語を使います。まずは実行例を見てください。
?- findall(Y, father_of(X, Y), Ls). Ls = [ichiro, jiro, tomoko, saburo, youko]. ?-
findall は第 2 引数をゴールとして実行し、そのときの第 1 引数の値をリスト Ls に追加します。そして、ゴールが失敗するまで繰り返します。
この例では、まず father_of(X, Y) を失敗するまで繰り返し実行します。成功した場合は第 1 引数 Y の値、つまり father_of(X, Y) の Y の値をリスト Ls に追加します。もし、ゴールの実行が一度でも成功しなかった場合は、Ls の値は空リストになります。
findall は「集合述語」と呼ばれます。ほかの述語と組み合わせることで、大変便利に使うことができます。このほかにも、SWI-Prolog には bagof と setof という集合述語が用意されています。使用する機会がありましたら、詳しく説明したいと思います。
今回は Prolog の簡単な応用例として、「ハノイの塔」を解くプログラムを作りましょう。ハノイの塔は、棒に刺さっている大きさが異なる複数の円盤を、次の規則に従ってほかの棒に移動させるパズルです。
ハノイの塔は、再帰を使えば簡単に解ける問題です。たとえば、3 枚の円盤が左の棒に刺さっているとします。この場合、いちばん大きな円盤を中央の棒に移すには、その上の 2 枚の円盤を右の棒に移しておけばいいですね。いちばん大きな円盤を中央に移したら、右の棒に移した 2 枚の円盤を中央の棒に移すことを考えればよいわけです。したがって、n 枚の円盤を左から中央の棒に移すプログラムは次のように表現できます。
これを素直にプログラムすると次のようになります。
リスト : ハノイの塔
hanoi(N, From, To, Via) :-
N > 1,
N1 is N - 1,
hanoi(N1, From, Via, To),
write([From, to, To]), nl,
hanoi(N1, Via, To, From).
hanoi(1, From, To, _) :- write([From, to, To]), nl.
N は動かす円盤の枚数、From は最初に円盤が刺さっている棒、To は円盤を移す棒、Via は残りの棒を示します。最後の規則が、動かす円盤の枚数が 1 枚の場合に対応し、再帰の停止条件になっています。
最初の規則は、円盤が複数枚ある場合に対応します。まず、円盤の枚数 N から 1 引いた値を N1 とします。次に hanoi を再帰呼び出しして、N1 枚の円盤を棒 Via に移動します。棒 From に残った円盤は 1 枚なので、それを棒 To に移動します。これを write で出力します。nl は改行するための述語です。最後に、棒 Via に移した円盤を棒 To に移動します。ここでも再帰呼び出しが行われます。
これで完成です。それでは実行してみましょう。
?- hanoi(3, a, b, c). [a,to,b] [a,to,c] [b,to,c] [a,to,b] [c,to,a] [c,to,b] [a,to,b] true. ?-
きれいに印字したい場合は述語 format を使いましょう。この述語はＣ言語の関数 printf や Common Lisp の関数 format に相当する働きをします。format は表示に関していろいろな指定を行うことができますが、その分使い方が少しだけ複雑になります。
format('書式文字列', 引数リスト).
第 1 引数は書式文字列で、出力に関する様々な指定を行います。これにはアトムを使います。format はアトムをそのまま出力するのですが、文字列の途中にチルダ ~ が表れると、その後ろの文字を変換指示子として理解し、引数リストのデータをその指示に従って表示します。よく使われる指示子を表に示します。
| 指示子 | 機能 |
|---|---|
| a | アトムを表示する |
| d | 整数を表示 (10進) |
| e, f, g | 浮動小数点数を表示 (Ｃ言語 printf と同じ) |
| r | 整数を表示 (2 - 32 までの基数を指定する) |
| n | 改行 |
| t | タブ |
| ~ | チルダ |
簡単な例を示しましょう。
?- format('number ~d , ~8r, ~16r~n', [256, 256, 256]).
number 256 , 400, 100
true.
?-
書式文字列の中には、複数の変換指示子を設定することができます。チルダの前までは、そのまま文字を表示します。チルダ ~ の次の文字 d, r, n が変換指示子です。d と r は整数値を表示する指示子で、n は改行を表す指示子です。r の場合、~ の後ろに基数を指定することができます。与えるデータと指示子の数が合わないとエラーになります。ご注意くださいませ。
アトムを表示する場合は a 変換指示子を使い、チルダを出力したい場合は ~~ と続けて書きます。このほかにも、浮動小数点数を表示する指示子などがあります。それらの機能は、必要になった時点で説明することにしましょう。
format を使ってプログラムを書き換えると、次のようになります。
リスト : ハノイの塔
hanoi(N, From, To, Via) :-
N > 1,
N1 is N - 1,
hanoi(N1, From, Via, To),
format('~a to ~a~n', [From, To]),
hanoi(N1, Via, To, From).
hanoi(1, From, To, _) :- format('~a to ~a~n', [From, To]).
それでは実行してみましょう。
?- hanoi(3, a, b, c). a to b a to c b to c a to b c to a c to b a to b true. ?-
次に示す述語を定義してください。
組み合わせの数 \({}_n \mathrm{C}_r\) を求めるには、次の公式を使えば簡単です。
皆さんお馴染みの公式ですね。(1) と (2) の公式を使うと簡単に (高速に) 答えを求めることができます。ただし、(3) の公式をそのままプログラムすると二重再帰になるので、大きな値を求めると時間がかかってしまうことに注意してください。
?- [user]. |: combination_number(N, N, 1) :- !. |: combination_number(_, 0, 1) :- !. |: combination_number(N, R, C) :- |: R > 0, R1 is R - 1, combination_number(N, R1, C1), C is C1 * (N - R + 1) // R. |: ^D true.
?- combination_number(0, 0, X). X = 1. ?- combination_number(10, 10, X). X = 1. ?- combination_number(10, 0, X). X = 1. ?- between(10, 30, R), N is R * 2, combination_number(N, R, C), write(C), nl, fail. 184756 705432 2704156 10400600 40116600 155117520 601080390 2333606220 9075135300 35345263800 137846528820 538257874440 2104098963720 8233430727600 32247603683100 126410606437752 495918532948104 1946939425648112 7648690600760440 30067266499541040 118264581564861424 false.
１ 0Ｃ0
／ ＼ ／ ＼
１ １ 1Ｃ0 1Ｃ1
／ ＼ ／ ＼ ／ ＼ ／ ＼
１ ２ １ 2Ｃ0 2Ｃ1 2Ｃ2
／ ＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼
１ ３ ３ １ 3Ｃ0 3Ｃ1 3Ｃ2 3Ｃ3
／ ＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼
１ ４ ６ ４ １ 4Ｃ0 4Ｃ1 4Ｃ2 4Ｃ3 4Ｃ4
図 : パスカルの三角形
パスカルの三角形は、左側の図のように両側がすべて 1 で、内側の数はその左上と右上の和になっています。これは \((a + b)^n\) を展開したときの各項の係数を表しています。そして、その値は右側の図のように組み合わせの数 \({}_n \mathrm{C}_r\) に対応しています。
きれいな三角形にはなりませんが、簡単なプログラムを示します。
?- [user]. |: pascal_sub([X, Y | Xs], [Z | Ys]) :- Z is X + Y, pascal_sub([Y | Xs], Ys). |: pascal_sub([1], [1]). |: ^D true. ?- pascal_sub([0, 1], Xs). Xs = [1, 1]. ?- pascal_sub([0, 1, 1], Xs). Xs = [1, 2, 1] ; false. ?- pascal_sub([0, 1, 2, 1], Xs). Xs = [1, 3, 3, 1] ; false.
?- [user]. |: pascal(N, Xs) :- N > 0, pascal_sub([0 | Xs], Ys), write(Ys), nl, N1 is N - 1, pascal(N1, Ys). |: pascal(0, _) :- nl. |: pascal(N) :- write([1]), nl, pascal(N, [1]). |: ^D true.
?- pascal(10). [1] [1,1] [1,2,1] [1,3,3,1] [1,4,6,4,1] [1,5,10,10,5,1] [1,6,15,20,15,6,1] [1,7,21,35,35,21,7,1] [1,8,28,56,70,56,28,8,1] [1,9,36,84,126,126,84,36,9,1] [1,10,45,120,210,252,210,120,45,10,1] true ; false. ?- pascal(15). [1] [1,1] [1,2,1] [1,3,3,1] [1,4,6,4,1] [1,5,10,10,5,1] [1,6,15,20,15,6,1] [1,7,21,35,35,21,7,1] [1,8,28,56,70,56,28,8,1] [1,9,36,84,126,126,84,36,9,1] [1,10,45,120,210,252,210,120,45,10,1] [1,11,55,165,330,462,462,330,165,55,11,1] [1,12,66,220,495,792,924,792,495,220,66,12,1] [1,13,78,286,715,1287,1716,1716,1287,715,286,78,13,1] [1,14,91,364,1001,2002,3003,3432,3003,2002,1001,364,91,14,1] [1,15,105,455,1365,3003,5005,6435,6435,5005,3003,1365,455,105,15,1] true ; false.
ソートはある規則に従ってデータを順番に並べることです。たとえば、データが整数であれば、大きい順かもしくは小さい順に並べます。ソートは昔から研究されている分野で、優秀なアルゴリズムが確立しています。その中でも「クイックソート (quick sort)」は高速のアルゴリズムとして有名です。もちろん、Prolog でもクイックソートをプログラムすることができます。今回は要素が整数のリストをクイックソートしてみることにしましょう。
クイックソートはある値を基準にして、要素をそれより大きいものと小さいものの 2 つに分割していくことでソートを行います。基準になる値のことを「枢軸 (pivot)」といいます。枢軸は、要素の中から適当な値を選んでいいのですが、リストの場合は、配列のように任意の箇所を簡単に選ぶことができません。この場合、一番簡単に求めることができる先頭の要素を枢軸とします。
リストを 2 つに分けたら、それらを同様にソートします。これは、再帰を使えば簡単に実現できます。その結果を枢軸を挟んで結合します。これを図に表すと次のようになります。
5 3 7 6 9 8 1 2 4
5 を枢軸に分割
(3 1 2 4) 5 (7 6 9 8)
3を枢軸に分割 7を枢軸に分割
(1 2) 3 (4) | 5 | (6) 7 (9 8)
・・・分割を繰り返していく・・・
図 : クイックソート
このようにリストを分割していくと、最後は空リストになります。ここが再帰の停止条件になります。あとは分割したリストを append で結合していけばいいわけです。プログラムは次のようになります。
リスト : クイックソート
quicksort([X | Xs], Ys) :-
partition(Xs, X, Littles, Bigs),
quicksort(Littles, Ls),
quicksort(Bigs, Bs),
append(Ls, [X | Bs], Ys).
quicksort([], []).
述語 quicksort は、リストをソートした結果を Ys にセットします。述語 partition は、リスト Xs を X より小さい Littles と、X より大きい Bigs に 2 分割します。そして、2 分割したリストに対して quicksort を再帰呼び出しします。最後に、append でソート済みのリスト Ls と Bs を枢軸 X を挟んで結合します。quicksort([ ], [ ]) が再帰呼び出しの停止条件です。
ここまではクイックソートの動作説明と同じなので簡単だと思います。リストを分割する partition はちょっとだけ複雑です。
リスト : 分割 (Y が枢軸となる)
partition([X | Xs], Y, [X | Ls], Bs) :-
X =< Y, partition(Xs, Y, Ls, Bs).
partition([X | Xs], Y, Ls, [X | Bs]) :-
X > Y, partition(Xs, Y, Ls, Bs).
partition([], Y, [], []).
第 1 引数のリストから先頭の要素 X を取り出して枢軸 Y と比較します。もし、枢軸より小さければ Ls に追加し、大きければ Bs に追加します。最初の規則が枢軸より小さい場合で、2 番目の規則が枢軸より大きい場合です。最後が空リストの場合で、これが再帰の停止条件になります。
プログラムはこれで完成です。それでは実行してみましょう。
?- quicksort([5, 3, 7, 6, 9, 8, 1, 2, 4], X). X = [1, 2, 3, 4, 5, 6, 7, 8, 9] ; false. ?- quicksort([9, 8, 7, 6, 5, 4, 3, 2, 1], X). X = [1, 2, 3, 4, 5, 6, 7, 8, 9] ; false. ?- quicksort([1, 2, 3, 4, 5, 6, 7, 8, 9], X). X = [1, 2, 3, 4, 5, 6, 7, 8, 9]. ?-
正常に動作していますね。このプログラムは、差分リストを使うとリストの結合が簡単になります。差分リストに変更したプログラムを示しましょう。
リスト : 差分リストを使ったクイックソート
quicksort1(Xs, Ys) :- quick_sub(Xs, [Ys, []]).
quick_sub([X | Xs], [Ys, Zs]) :-
partition(Xs, X, Littles, Bigs),
quick_sub(Littles, [Ys, [X | Ys1]]),
quick_sub(Bigs, [Ys1, Zs]).
quick_sub([], [Xs, Xs]).
?- quicksort1([5, 3, 7, 6, 9, 8, 1, 2, 4], X). X = [1, 2, 3, 4, 5, 6, 7, 8, 9] ; false. ?- quicksort1([9, 8, 7, 6, 5, 4, 3, 2, 1], X). X = [1, 2, 3, 4, 5, 6, 7, 8, 9] ; false. ?- quicksort1([1, 2, 3, 4, 5, 6, 7, 8, 9], X). X = [1, 2, 3, 4, 5, 6, 7, 8, 9]. ?-
quick_sub は差分リストを使ってリストを組み立てます。2 番目の規則では、Ys が差分リストの頭部で、Zs が尾部を表します。partition を呼び出して、リストを Littles と Bigs に分けるのは同じです。差分リスト [Ys, Zs] を [Ys, Ys1] + [Ys1, Zs] と考えて、再帰呼び出しを行います。
ただし、このままでは枢軸 X が仲間はずれですね。X を差分リストの後ろに追加するには、差分リストの尾部を [Ys, [X | Ys1]] とします。これで X が追加できるなんて不思議ですね。たとえば、X の値が 3 で Littles をソートした結果が [[1, 2 | Foo], Foo] とし、Bigs をソートした結果が [[4, 5 | Bar], Bar] だったとしましょう。マッチングは次のようになります。
[Ys , [3 | Ys1]] = [[1, 2 | Foo], Foo] Ys = [1, 2 | Foo] [3 | Ys1] = Foo => Ys = [1, 2, 3 | Ys1] [Ys1, Zs] = [[4, 5 | Bar], Bar] Ys1 = [4, 5 | Bar] Bar = Zs => Ys = [1, 2, 3, 4, 5 | Zs]
このように、枢軸 3 がきちんと追加されています。差分リストの扱いに慣れていないと、ちょっと難しいところだと思います。なお、今回は例題にクイックソートを取り上げましたが、リストをソートするならば「マージソート (merge sort)」の方が適しています。興味のある方は拙作のページ「Algorithms with Python: 整列 [3]」をお読みくださいませ。
次に示す述語を定義してください。
リスト : 要素の挿入 insert_item(X, [Y | Ys], [X, Y | Ys]) :- X =< Y, !. insert_item(X, [Y | Ys], [Y | Zs]) :- insert_item(X, Ys, Zs). insert_item(X, [], [X]).
?- insert_item(1, [1,2,3,4,5], Xs). Xs = [1, 1, 2, 3, 4, 5]. ?- insert_item(3, [1,2,3,4,5], Xs). Xs = [1, 2, 3, 3, 4, 5] ; false. ?- insert_item(5, [1,2,3,4,5], Xs). Xs = [1, 2, 3, 4, 5, 5] ; false. ?- insert_item(6, [1,2,3,4,5], Xs). Xs = [1, 2, 3, 4, 5, 6] ; false.
リスト : 挿入ソート insert_sort([X | Xs], Ys) :- insert_sort(Xs, Zs), insert_item(X, Zs, Ys). insert_sort([], []).
?- insert_sort([3,4,2,5,1], Xs). Xs = [1, 2, 3, 4, 5] ; false. ?- insert_sort([5,4,3,2,1], Xs). Xs = [1, 2, 3, 4, 5] ; false. ?- insert_sort([1,2,3,4,5], Xs). Xs = [1, 2, 3, 4, 5].
リスト : リストのマージ merge_list([X | Xs], [Y | Ys], [X | Zs]) :- X =< Y, !, merge_list(Xs, [Y | Ys], Zs). merge_list([X | Xs], [Y | Ys], [Y | Zs]) :- merge_list([X | Xs], Ys, Zs). merge_list([], Ys, Ys). merge_list(Xs, [], Xs).
?- merge_list([1,3,5,7], [2,4,6,8], Xs). Xs = [1, 2, 3, 4, 5, 6, 7, 8] ; false. ?- merge_list([1,2,3,4], [5,6,7,8], Xs). Xs = [1, 2, 3, 4, 5, 6, 7, 8] ; false. ?- merge_list([5,6,7,8], [1,2,3,4], Xs). Xs = [1, 2, 3, 4, 5, 6, 7, 8] ; false. ?- merge_list([1,2,3,4], [], Xs). Xs = [1, 2, 3, 4]. ?- merge_list([], [1,2,3,4], Xs). Xs = [1, 2, 3, 4] ; false.
リスト : マージソート
drop([_ | Xs], N, Ys) :- N > 0, N1 is N - 1, drop(Xs, N1, Ys).
drop(Xs, 0, Xs).
merge_sort(N, Xs, Ys) :-
N > 1,
M1 is N // 2,
merge_sort(M1, Xs, Zs1),
M2 is N - M1,
drop(Xs, M1, Xs1),
merge_sort(M2, Xs1, Zs2),
merge_list(Zs1, Zs2, Ys).
merge_sort(1, [X | _], [X]).
merge_sort(_, [], []).
merge_sort(Xs, Ys) :- length(Xs, N), merge_sort(N, Xs, Ys).
?- merge_sort([3,4,2,5,1,6], Xs). Xs = [1, 2, 3, 4, 5, 6] ; false. ?- merge_sort([1,2,3,4,5,6], Xs). Xs = [1, 2, 3, 4, 5, 6] ; false. ?- merge_sort([6,5,4,3,2,1], Xs). Xs = [1, 2, 3, 4, 5, 6] ; false.
8 クイーンはコンピュータに解かせるパズルでは特に有名な問題です。8 クイーンは 8 行 8 列のチェスの升目に、8 個のクイーンを互いの利き筋が重ならないように配置する問題です。クイーンは将棋の飛車と角をあわせた駒で、縦横斜めに任意に動くことができます。解答の一例を次に示します。
列
1 2 3 4 5 6 7 8
*-----------------*
1 | Q . . . . . . . |
2 | . . . . Q . . . |
3 | . . . . . . . Q |
行 4 | . . . . . Q . . |
5 | . . Q . . . . . |
6 | . . . . . . Q . |
7 | . Q . . . . . . |
8 | . . . Q . . . . |
*-----------------*
図 : 8 クイーンの解答例
8 クイーンを解くには、すべての置き方を試してみるしか方法はありません。最初のクイーンは、盤上の好きなところへ置くことができるので、64 通りの置き方があります。次のクイーンは 63 通り、その次は 62 通りあります。したがって、置き方の総数は 64 から 57 までの整数を掛け算した 178462987637760 通りもあります。これはとても大きな数ですね。
ところが、解答例を見ればわかるように、同じ行と列に 2 つ以上のクイーンを置くことはできません。上図の解答例をリストを使って表すと、 次のようになります。
1 2 3 4 5 6 7 8 <--- 列の位置
---------------------------
[1, 7, 5, 8, 2, 4, 6, 3] <--- 要素が行の位置を表す
図 : リストでの行と列の表現方法
列をリストの位置に、行番号を要素に対応させれば、各要素には 1 から 8 までの数字が重複しないで入ることになります。すなわち、1 から 8 までの順列の総数である 8! = 40320 通りの置き方を調べればよいことになります。ぐっと数が減りましたね。パズルを解く場合は、そのパズル固有の性質をうまく使って、調べなければならない場合の数を減らすように工夫することが大切です。
順列を生成するプログラムは簡単に作成することができます。あとは、その順列が 8 クイーンの条件を満たしているかチェックすればいいわけです。このように、正解の可能性があるデータを作りそれをチェックするという方法を「生成検定法 (generate and test)」といいます。可能性のあるデータをもれなく作るのに、バックトラックは最適です。ただし、生成するデータ数が多くなると時間がとてもかかる、という弱点があるので注意してください。
それではプログラムを作りましょう。最初に順列を発生する述語 perm を作ります。述語 perm(L, Z) は、リスト L の要素の順列を生成し、それを変数 Z にセットします。
リスト : 順列の生成 perm([],[]). perm(Xs, [Z | Zs]) :- select(Z, Xs, Ys), perm(Ys, Zs).
述語 select を使ってリスト Xs から要素を一つ選びます。その要素 Z をリストの先頭に加えます。次に、残りのリスト Ys の中から要素を一つ取り出してリストに加えます。この処理は再帰を使えば簡単ですね。あとはリストの要素がなくなるまで、この処理を繰り返せばいいわけです。最初の規則が再帰呼び出しの停止条件です。
これでバックトラックが発生すれば、新しい順列を生成することができます。それでは実際に実行してみましょう。
?- perm([1, 2, 3], Z), write(Z), nl, fail. [1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1] false. ?-
1, 2, 3 の順列ですから全部で 6 通りあります。正常に動作していますね。
あとは perm で生成した順列が、条件を満たすかチェックすれば良いのです。チェックする述語を safe とすると、8 クイーンを解くプログラムは次のようになります。
queen(Q) :- perm([1,2,3,4,5,6,7,8], Q), safe(Q).
perm でデータを生成し safe で条件をチェックする、というたいへん簡単な構造になっています。これが生成検定法の基本型です。それでは safe を作りましょう。
リスト : 利き筋が重なっていないか safe([Qt | Qr]) :- not(attack(Qt, Qr)), safe(Qr). safe([]).
リストの先頭の要素からチェックしていきます。衝突のチェックは斜めの利き筋を調るだけです。端にあるクイーンから順番に調べるとすると、斜めの利き筋は次のように表せます。
1 2 3 --> 調べる方向
*-------------
| . . . . . .
| . . . -3. . 5 - 3 = 2
| . . -2. . . 5 - 2 = 3
| . -1. . . . 5 - 1 = 4
| Q . . . . . Q の位置は 5
| . +1. . . . 5 + 1 = 6
| . . +2. . . 5 + 2 = 7
| . . . +3. . 5 + 2 = 8
*-------------
図 : 衝突の検出
図を見てもらえばおわかりのように、Q が行 5 にある場合、一つ隣の列は 4 と 6 が利き筋に当たります。2 つ隣の列の場合は 3 と 7 が利き筋に当たります。このように単純な足し算と引き算で、利き筋を計算することができます。これをプログラムすると次のようになります。
リスト : 衝突の検出 attack(X, Xs) :- attack_sub(X, 1, Xs). attack_sub(X, N, [Y|Ys]) :- (X =:= Y + N ; X =:= Y - N). attack_sub(X, N, [Y|Ys]) :- N1 is N + 1, attack_sub(X, N1, Ys).
attack は、斜めの利き筋に当たった場合に成功する述語です。attack_sub は、リストの先頭から斜めの利き筋に当たるか調べます。第 1 引数がクイーンの位置、第 2 引数が位置の差分、第 3 引数がリストになります。
2 番目の規則で、リストから先頭の要素 Y を取りだし、利き筋に当たるか調べます。これは、Y + N または Y - N が X と等しいかチェックするだけです。衝突していない場合は失敗するので、3 番目の規則が選択されます。この規則はリストを分解して差分を一つ増やし、attack_sub を再帰呼び出しするだけです。これで次のクイーンをチェックすることができます。
これでプログラムは完成です。それでは実行してみましょう。
?- time((queen(Q), write(Q), nl, fail)). [1,5,8,6,3,7,2,4] [1,6,8,3,7,4,2,5] [1,7,4,6,8,2,5,3] ・・・・・省略・・・・・ [8,2,5,3,1,7,4,6] [8,3,1,6,2,5,7,4] [8,4,1,3,6,2,7,5] % 1,460,048 inferences, 0.168 CPU in 0.168 seconds (100% CPU, 8710241 Lips) false. ?-
解は全部で 92 通りあります。実行時間は約 0.17 秒でした。今のパソコンは高性能なので、8 クイーンであれば簡単に解くことができます。ところが、クイーンの個数を増やすと、実行時間は極端に遅くなります。実はこのプログラム、とても非効率なことをやっているのです。
実行速度が遅くなる理由は、失敗することがわかっている順列も生成してしまうからです。
たとえば、最初 (1, 1) の位置にクイーンを置くと、次のクイーンは (2, 2) の位置に置くことはできませんね。したがって、[1, 2, X, X, X, X, X, X,] という配置はすべて失敗するのですが、順列を発生させてからチェックする方法では、このような無駄を省くことができません。
そこで、クイーンの配置を決めるたびに衝突のチェックを行うことにします。これをプログラムすると次のようになります。
リスト : 8 クイーン (改良版)
queen_f(Q) :- queen_sub([1,2,3,4,5,6,7,8], [], Q).
queen_sub(L, SafeQs, Q) :-
select(X, L, RestQs),
not(attack(X, SafeQs)),
queen_sub(RestQs, [X | SafeQs], Q).
queen_sub([], Q, Q).
queen_sub は第 2 引数のリストに 8 クイーンの配置を格納します。まず select でリスト L から一つの要素 X を選び、それが SafeQs に格納されているクイーンと利き筋が重ならないかチェックします。衝突しないことを確認したら、X をリスト SafeQs に加えて queen_sub を再帰呼び出します。最後の規則が再帰呼び出しの停止条件です。
このように、できるだけ早い段階でチェックを入れることで、無駄なデータをカットすることを「枝刈り」と呼びます。バックトラックを使って問題を解く場合、この枝刈りのよしあしによって実行時間が大きく左右されるのです。
それでは実行結果を示します。
?- time((queen_f(Q), write(Q), nl, fail)). [4,2,7,3,6,8,5,1] [5,2,4,7,3,8,6,1] [3,5,2,8,6,4,7,1] ・・・・・省略・・・・・ [6,4,7,1,3,5,2,8] [4,7,5,2,6,1,3,8] [5,7,2,6,3,1,4,8] % 90,300 inferences, 0.021 CPU in 0.021 seconds (100% CPU, 4271261 Lips) false. ?-
実行時間は約 0.021 秒まで短縮しました。ところで、今回は単純にリストを出力するだけなので、ちょっと面白くありません。最初に示した図のように、クイーンの配置を表示するプログラムを作るといいでしょう。これは簡単にプログラムできるので、皆さんにお任せいたします。いい練習問題になると思います。
次に示す述語を定義してください。
?- [user]. |: permutation(N, Xs, [X | Ys]) :- N > 0, N1 is N - 1, select(X, Xs, Zs), permutation(N1, Zs, Ys). |: permutation(0, _, []). |: ^D true.
?- permutation(2, [1,2,3,4], Xs). Xs = [1, 2] ; Xs = [1, 3] ; Xs = [1, 4] ; Xs = [2, 1] ; Xs = [2, 3] ; Xs = [2, 4] ; Xs = [3, 1] ; Xs = [3, 2] ; Xs = [3, 4] ; Xs = [4, 1] ; Xs = [4, 2] ; Xs = [4, 3]. ?- permutation(3, [1,2,3], 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].
?- [user]. |: combination(N, [X | Xs], [X | Ys]) :- N > 0, N1 is N - 1, combination(N1, Xs, Ys). |: combination(N, [_ | Xs], Ys) :- N > 0, combination(N, Xs, Ys). |: combination(0, _, []). |: ^D true. ?- combination(3, [1,2,3,4,5], 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] ; false. ?- combination(2, [1,2,3,4,5], Xs). Xs = [1, 2] ; Xs = [1, 3] ; Xs = [1, 4] ; Xs = [1, 5] ; Xs = [2, 3] ; Xs = [2, 4] ; Xs = [2, 5] ; Xs = [3, 4] ; Xs = [3, 5] ; Xs = [4, 5] ; false.
?- [user]. |: repeat_perm(N, Xs, [X | Ys]) :- N > 0, N1 is N - 1, member(X, Xs), repeat_perm(N1, Xs, Ys). |: repeat_perm(0, _, []). |: ^D true.
?- repeat_perm(2, [1,2,3], Xs). Xs = [1, 1] ; Xs = [1, 2] ; Xs = [1, 3] ; Xs = [2, 1] ; Xs = [2, 2] ; Xs = [2, 3] ; Xs = [3, 1] ; Xs = [3, 2] ; Xs = [3, 3].
?- [user]. |: repeat_comb(N, [X | Xs], [X | Ys]) :- N > 0, N1 is N - 1, repeat_comb(N1, [X | Xs], Ys). |: repeat_comb(N, [_ | Xs], Ys) :- N > 0, repeat_comb(N, Xs, Ys). |: repeat_comb(0, _, []). |: ^D true.
?- repeat_comb(3, [1,2,3,4], Xs). Xs = [1, 1, 1] ; Xs = [1, 1, 2] ; Xs = [1, 1, 3] ; Xs = [1, 1, 4] ; Xs = [1, 2, 2] ; Xs = [1, 2, 3] ; Xs = [1, 2, 4] ; Xs = [1, 3, 3] ; Xs = [1, 3, 4] ; Xs = [1, 4, 4] ; Xs = [2, 2, 2] ; Xs = [2, 2, 3] ; Xs = [2, 2, 4] ; Xs = [2, 3, 3] ; Xs = [2, 3, 4] ; Xs = [2, 4, 4] ; Xs = [3, 3, 3] ; Xs = [3, 3, 4] ; Xs = [3, 4, 4] ; Xs = [4, 4, 4] ; false.