論理パズルを解きながらPrologの勉強をするシリーズ。
前回に引き続き、今回もグリッドパズルを取り上げたいと思う。
今回は、グリッドパズルの中で一番有名（らしい）シマウマのパズル。この問題は1962年アメリカの雑誌『ライフ・インターナショナル』に載っていたらしい。アインシュタインが作ったという噂があり、「アインシュタインの難問」とも呼ばれていたそう。問題見て頂くとわかると思うが、パっと見、うんざりするような問題です。
出典は、アレックス・ベロス『この数学パズル、解けますか？』を参照）です。この本は様々な論理パズルを扱っていて面白い。著者が日本人ではないからかもしれないが、あまり日本語では見かけないようなパズルもあってそれもまた一興。今後もこの本から何個かパズルを取り上げる予定。
論理パズル「シマウマのパズル」
■問題
家が5軒一列に並んで建っている。
5軒の家はそれぞれ違う色に塗られていて、住んでいる人はそれぞれ生まれた国、飼っているペット、飲み物、履物の種類が違う。
- スコットランド人は赤い家に住んでいる。
- ギリシャ人は犬を飼っている。
- コーヒーを飲むのは緑色の家の人。
- ボリビア人はお茶を飲む。
- 緑色の家はクリーム色の家のすぐ右隣りにある。
- 革靴を履いている人はカタツムリを飼っている。
- 厚底靴を履くのは黄色の家の人。
- 牛乳を飲むのは真ん中の家の人。
- デンマーク人は左端の家に住んでいる。
- 革サンダルを履いている人は、キツネを飼っている人の隣の家に住んでいる。
- 厚底靴を履いている人はの家は、ウマを飼っている家の隣。
- スリッパを履いている人はオレンジジュースを飲む。
- 日本人はビーチサンダルを履いている。
- デンマーク人は青い家の隣に住んでいる。
さて、水を飲むのは誰？また、シマウマを飼っているのは誰？
どうですか？ウンザリしませんか？
ちなみに僕は手で解くのをあきらめた。Prologが出力する答えをチェックするのはそれほど大変ではない（NP問題ですね）ので、手で解いてなくても特に問題はないが、「アインシュタインの難問」という名前を冠しているくらいの難問なので、論理パズル好きな方は是非手で解いてみてください。
しかし、飼ってるペットが奇妙極まりない。シマウマってそもそも飼っていいのだろうか？そしてそれと同列にカタツムリが並べられているが、それはいいのだろうか？
英語の問題なので頭文字が被らないように腐心した結果ということは分かるが、それでもカタツムリとは。。せめてsnakeではないかと思う。
実行環境
Prologをクイックに実行する環境として、SWISHを利用。これはクラウド上でSWI-Prologを実行できるので、Prologに興味を持った人は触ってみてください。
ちなみに、SWI-Prologとは、「多くのUNIXやMS-Windows で利用することが出来るエジンバラProlog (DEC-10 Prolog) 記法を採用したProlog処理系であり、ISO規格 にも準拠している」、らしい。（詳細はこちらを参照）
Prologコーディング
前回と同様、ほぼスクラッチでコーディング。
状態の定義
まずはシマウマのパズルを定式化するための状態を定義する。
実はここで結構ハマった。5つの家庭が持つ6つ状態（家の配置、家の色、国籍、ペット、飲み物、履物）をリスト化すればいい所に気づいたのは半日くらい悩んだあと。
この問題は、全ての状態（5 x 6 = 30）を同時に考える必要があるため、状態も30個の要素を持つリストになる。そのままだと操作しにくいので、家庭毎に6つの要素をリスト化して、5つの家庭群を更にリスト化する形にした。
$$ [[1番左、色、国、ペット、飲物、履物]、[左から2番目、色、国、ペット、飲物、履物]、...] $$
制約条件の定義
制約条件を定義する。
- 事実の定義
- 置換ルールの定義
- 各家庭の要素を特定する術語の定義
1. 事実の定義
14個ある事実を定義していく。
事実群を正しく定式化するのに1日くらいかかった。例えば「スコットランド人は赤い家に住んでいる」という事実があるが、これは「ある家がスコットランド人ならばその家の色は赤い」と定義するべきなのかなど考えたりした。その場合color(House, red) :- nation(House, scottish))のように定義しようと検討したがうまくいかなかった。
この問題の難しい所は、5つある家庭の中で「スコットランド人は赤い家に住んでいる」という事実が成り立つ家庭は1つしか存在しなく、そしてその家庭がどれかはほかの事実と組み合わせないとわからない、という点だろう。上記のような定義をしてしまうと、Houseを特定しない場合には、すべての家庭において、家は赤くスコットランド人が住んでいる」という言説になってしまうし、Houseを特定しようにも、ほかの事実を所与としない限り特定できない。
ということで、色々試行錯誤した結果、memberという組込み術語を利用すればいいことに気づいた。memberは特定の定数（アトム）があるリストに含まれているかを判定する術語である。例としてmember(a, [a,b,c])の時、「aは[a,b,c]に含まれているか」を確認して（この場合）trueを返す。各事実を定義するのに、このmemberを利用した。
% 事実（Housesは全ての家庭の状態が入ったリスト）
fact1(Houses) :- member([_ ,red ,scottish,_ ,_ ,_ ], Houses).
fact2(Houses) :- member([_ ,_ ,greece ,dog ,_ ,_ ], Houses).
fact3(Houses) :- member([_ ,green ,_ ,_ ,coffee,_ ], Houses).
fact4(Houses) :- member([_ ,_ ,bolivian,_ ,tea ,_ ], Houses).
fact5(Houses) :- member([N ,green ,_ ,_ ,_ ,_ ], Houses),
member([M ,cream ,_ ,_ ,_ ,_ ], Houses), N - M =:= 1.
fact6(Houses) :- member([_ ,_ ,_ ,snails,_ ,leather ], Houses).
fact7(Houses) :- member([_ ,yellow,_ ,_ ,_ ,platform], Houses).
fact8(Houses) :- member([3 ,_ ,_ ,_ ,milk ,_ ], Houses).
fact9(Houses) :- member([1 ,_ ,denmark ,_ ,_ ,_ ], Houses).
fact10(Houses) :- member([N ,_ ,_ ,_ ,_ ,leatherS], Houses),
member([M ,_ ,_ ,fox ,_ ,_ ], Houses), (N - M =:= 1; M - N =:= 1).
fact11(Houses) :- member([N ,_ ,_ ,_ ,_ ,platform], Houses),
member([M ,_ ,_ ,horse ,_ ,_ ], Houses), (N - M =:= 1; M - N =:= 1).
fact12(Houses) :- member([_ ,_ ,_ ,_ ,orange,slipper ], Houses).
fact13(Houses) :- member([_ ,_ ,japanese,_ ,_ ,beachS ], Houses).
fact14(Houses) :- member([N ,_ ,denmark ,_ ,_ ,platform], Houses),
member([M ,blue ,_ ,horse ,_ ,_ ], Houses), (N - M =:= 1; M - N =:= 1).
facts(Houses) :-
fact1(Houses), fact2(Houses), fact3(Houses), fact4(Houses), fact5(Houses),
fact6(Houses), fact7(Houses), fact8(Houses), fact9(Houses), fact10(Houses),
fact11(Houses), fact12(Houses), fact13(Houses), fact14(Houses).
一例として、1つ目の事実「赤い家にはスコットランド人が住んでいる」を取り上げる。左記を定義するため、fact1(Houses) :- member([_ ,red ,scottish,_ ,_ ,_ ], Houses).とした。Housesは5家庭をリスト化していて、各家庭はさらに6つの要素を持つリストとなっている。memberを使って、色がredかつ、国籍がscottishな家庭が全家庭リストに含まれることを保証した。
その他13個の事実についても同様。
最後のfacts(Houses)については、これらの事実をまとめた方が見やすくなると思い定義した。
2. 置換ルールの定義
事実に加えて、各要素（例えばペット）は家庭間で重複がない、という条件を設定するための置換ルールを定義した。
% 置換
permutation([], []).
permutation(L, [X|L2]) :-
del(X, L, L1),
permutation(L1, L2).
del(X, [X|L], L).
del(X, [Y|L], [Y|L1]) :-
del(X, L, L1).
例えば、permutation([a,b,c], [b,a,c])だと「[a,b,c]と[b,a,c]は置換可能か」を判定してくれる。（この場合もちろんtrue）
この述語を使うことで、全家庭のペットがペットの一覧リストと置換可能かをチェックすることで重複可能性を排除できる。（dogが2つの家庭で現れたらペットリストとは置換ができないのでdogは一度しか現れてはいけない、など）
del()術語はpermutation上でリストからある要素を削除する処理を入れたいため別途定義した。
3. 各家庭の要素を特定する術語の定義
仕上げに、全家庭の要素を特定するための術語を定義する。
% 家の組み合わせ探索
houseList([1, X12, X13, X14, X15, X16],
[2, X22, X23, X24, X25, X26],
[3, X32, X33, X34, X35, X36],
[4, X42, X43, X44, X45, X46],
[5, X52, X53, X54, X55, X56]) :-
facts([[1, X12, X13, X14, X15, X16],
[2, X22, X23, X24, X25, X26],
[3, X32, X33, X34, X35, X36],
[4, X42, X43, X44, X45, X46],
[5, X52, X53, X54, X55, X56]]),
permutation([X12,X22,X32,X42,X52], [blue, green, red, yellow, cream]),
permutation([X13,X23,X33,X43,X53], [denmark, japanese, bolivian, scottish, greece]),
permutation([X14,X24,X34,X44,X54], [snails, dog, horse, fox, zebra]),
permutation([X15,X25,X35,X45,X55], [tea, orange, milk, coffee, water]),
permutation([X16,X26,X36,X46,X56], [leather, slipper, leatherS, beachS, platform]),
write([1, X12, X13, X14, X15, X16]), nl,
write([2, X22, X23, X24, X25, X26]), nl,
write([3, X32, X33, X34, X35, X36]), nl,
write([4, X42, X43, X44, X45, X46]), nl,
write([5, X52, X53, X54, X55, X56]).
全ての要素を特定したいので、30個の要素を明示的に扱った。ただし、家の配置についてはデフォルトとして各家庭に[1,2,3,4,5]を割り振った。（1が左端で、5が右端）。よって特定するべき要素は25個となる。
25個の要素に関して、まず事実群が成立するかをチェックし、その後各要素（家の色や国籍など）に重複がないかをpermutation()でチェックした。さいどのwrite達は見栄えのよい出力を得るための術語。
実は当初、facts()の前にpermutation()達を定義してしまい、探索が終わらない問題に突き当たってしまった。Prologでは記入した順番通りに探索を実行するので、先にpermutation()を定義してしまうと、まず各要素にランダムに値を代入して、それが事実群を満たすかどうかをチェックする、という非常に非効率な探索を実施してしまっていた。5x5の要素群の場合の数は120 x 120 x 120 x 120 x 120の約2,500億通りもあるため、それをランダムに探索するのがいかに非効率化は押して図るべしだろう。
途中で気づいて、facts()をpermutation()の前に置いたら一瞬で探索が終わった。facts()を満たすようにあらかじめいくつかの要素を埋めておいて、残りに対してpermutation()をかける、というアプローチがいかに効率的かを実感できるいい機会ではあった。
答え出力
Prologの出力結果は以下である。
ちなみに、下記以外にすべてのX12, X13,...に対して1行ずつ出力を得たが、そちらは見づらいため省略した。
?- houseList([1, X12, X13, X14, X15, X16],
[2, X22, X23, X24, X25, X26],
[3, X32, X33, X34, X35, X36],
[4, X42, X43, X44, X45, X46],
[5, X52, X53, X54, X55, X56])
[1, yellow, denmark, fox, water, platform]
[2, blue, bolivian, horse, tea, leatherS]
[3, red, scottish, snails, milk, leather]
[4, cream, greece, dog, orange, slipper]
[5, green, japanese, zebra, coffee, beachS]
false
他の解答がないかについてはfalseだったので、これが唯一の解であることが保証された。
上記でも十分見やすいとは思うが、一応表としてまとめた。
| 配置 | 家の色 | 国籍 | ペット | 飲物 | 履物 |
|---|---|---|---|---|---|
| 左端 | 黄 | デンマーク | キツネ | 水 | 厚底靴 |
| 左から2番目 | 青 | ボリビア | ウマ | 紅茶 | 革サンダル |
| 真ん中 | 赤 | スコットランド | カタツムリ | ミルク | 革靴 |
| 右から2番目 | クリーム | ギリシャ | イヌ | オレンジ | スリッパ |
| 右端 | 緑 | 日本 | シマウマ | コーヒー | ビーチサンダル |
問題の解答としては、
- 水を飲むのはデンマーク人
- シマウマを飼っているのは日本人
ということになる。
これまでPrologで解いてきた中で一番時間がかかった気がする。はじめに問題を見たときには「いかにもPrologが得意そうな問題だ。すぐ出来るか」と甘い見積もりをしてしまった。
14個の事実に加え、複数の状態（5つの家庭の6つの要素）を同時に決定しなければいけないため、途中かなり迷走したが、いい勉強になったとは思う。
しかしビーチサンダルを履いてコーヒーを飲みながら緑の家でシマウマを飼っている日本人て。。
参考
コーディングにあたっては下記文献およびサイトを参照した。
補足
Qiita上で既にシマウマのパズルPrologで解いている投稿が2つありました。（リサーチ不足ですみません）こちらもご参照ください。
- Prologで解くZebraPuzzle
-
Prolog実践入門 - AIに特化した老舗言語
他の方のコードを見ると勉強になりますね。リストを極力使わず結構シンプルに記述されている印象。パズルの問題に答えることを目的としてるので、ルールのヘッドがzebra(X)などとなっている点は潔くていいですね。僕はすべての状態を求めるために結構重たいヘッドになってしまった。