論理パズルを解きながらPrologの勉強をするシリーズ。
今回は論理パズルや判断推理（コンサルや公務員の採用試験で出てくる問題）でよく見かける「グリッドパズル」を取り上げる。
グリッドパズルとは、いくつかの断片的な知識を組み合わせて、何が分かるかを問う問題である。今回取り上げた犯人探し問題などが有名な事例。ちなみになぜグリッドパズルというかというと、このクラスの問題はグリッド（表）にあらゆる選択肢を書き上げて一つ一つチェックしていくと解けるから、らしい。（グリッドパズルの言葉の由来はアレックス・ベロス『この数学パズル、解けますか？』を参照）
単純なグリッドパズルだと味気ないので、推理小説風の問題を取り上げてみた。
このクラスはかなりバリエーションがあるので今後も似たような問題を取り上げるかもしれない。
出典はこちらのサイト。
論理パズル「犯人はだれだ？」
■問題
犯行の現場に居合わせた青木、飯島、臼田、榎本、太田の5人。
刑事が「犯人はだれだ？」と尋ねたところ、それぞれ下記のように答えた。
- 青木「犯人は私ではありません。臼田でもありません」
- 飯島「犯人は私ではありません。青木でもありません」
- 臼田「犯人は青木か太田です」
- 榎本「犯人は飯島か太田です」
- 太田「犯人は臼田か榎本です」
この中には犯人が１人とウソをついた人が２人いる。
犯人は誰でウソをついたのはどの２人か？
一番シンプルな形だと、「犯人は1人かつその人がウソをついている」という問題になる。
今回は犯人がウソをついているかわからない上に、ウソをついたのは犯人以外にもう1人いることになっている。
しかし、犯人でもないのにウソをついた人は偽証罪にあたるのではないだろうか。。
ということは、「犯人でもないのにウソをついた人」もまた罪を問われるので（広義の）犯人であり、そうすると実は犯人は少なくとも2人いることになるのでは、などと考えてしまう。（問題および解答とは関係ない考察なので無視してください）
このクラスの問題を解くときに何が大変かというと、可能性の数が多すぎる点だろう。5人のうち1人が犯人で、5人のうち2人がウソをついているということは、5 x 10 = 50通りもの可能性が考えられるということだ。場合分けが多すぎて頭の中で推論するのはかなり大変になる。
ということで、Prologの出番。
実行環境
Prologをクイックに実行する環境として、SWISHを利用。これはクラウド上でSWI-Prologを実行できるので、Prologに興味を持った人は触ってみてください。
ちなみに、SWI-Prologとは、「多くのUNIXやMS-Windows で利用することが出来るエジンバラProlog (DEC-10 Prolog) 記法を採用したProlog処理系であり、ISO規格 にも準拠している」、らしい。（詳細はこちらを参照）
Prologコーディング
ウソつき問題をPrologで解いているコードを見つけられなかったので、今回はほぼスクラッチでコーディング。
状態の定義
まずはウソつき問題を定式化するための状態を定義する。
各人が犯人かどうかと、ウソをついているかどうかという二つの状態を持つので、二つのリストとして状態を定義することにする。例えば[lie, lie, true, true, true], [g, noG, noG, noG, noG]は、青木と飯島がウソをついていて他の人たちは真実を話しているうえに、青木は犯人でもある、という状態を表している。
よって、この問題は論理的矛盾が発生しないような2つのリストの値は何か？という質問にPrologが答えることで解決する。
ここではさらっと書いたが、実はこの定義に至るまでにちょっと時間がかかった。はじめは術語として「Xがウソをついている」ことをlie(X)とか、「Yが犯人である」ことをcriminal(Y)などと定義しようとしたがうまくいかなかった。この問題は一見「犯人（ウソつき）はだれか？」という質問に答えればいいように見えるが、実は「犯人（ウソつき）は誰で、それ以外は犯人ではない（ウソをついていない）状態は何か？」に答えなければいけないことにしばらくたってから気づいた。つまり、ウソをついている人だけでなく、ウソをついていない人も明示的にしなければ、彼らの証言を根拠に誰が犯人かを特定することができないのだ。なので単純にlie(X)のように「Xがウソをついているかどうか」について定義する術語ではなく、5人のうち誰と誰がウソをついていて、それ以外は本当のことを言っているか、ということを網羅的に明らかにすることが可能なリスト[lie, lie, true, true, true]を定義することにした。
制約条件の定義
「川渡り問題；オオカミとヒツジとキャベツ」と異なり、何かの初期状態からゴールの状態までの推移を求めたいわけではないので、ここでは推移規則ではなく制約条件を定義する。
- 各人の証言についての定義
- リストの中にある要素が何個あるかを数える術語の定義
- 犯人とウソつきを特定する術語の定義
1. 証言の定義
各人の証言については、testify(証言者、証言内容、ウソかどうか)という述語で定義する。証言内容については、誰が犯人かについてのリストとした。例えばXさんの証言内容が[g, noG, noG, noG, noG]なら、Xは青木が犯人であると証言した、ということになる。
また、ウソかどうかのバイナリ引数によって、Xの証言が本当かどうかを表すことにする。
% 証言
testify(aoki, [noG, _, noG, _, _] , true).
testify(aoki, [g, noG, noG, noG, noG], lie).
testify(aoki, [noG, noG, noG, g, noG], lie).
testify(iijima, [noG, noG, _, _, _], true).
testify(iijima, [g, noG, noG, noG, noG], lie).
testify(iijima, [noG, g, noG, noG, noG], lie).
testify(usuda, [g, noG, noG, noG, noG], true).
testify(usuda, [noG, noG, noG, noG, g], true).
testify(usuda, [noG, _, _, _, noG], lie).
testify(enomoto, [noG, g, noG, noG, noG], true).
testify(enomoto, [noG, noG, noG, noG, g], true).
testify(enomoto, [_, noG, _, _, noG], lie).
testify(ohta, [noG, noG, g, noG, noG], true).
testify(ohta, [noG, noG, noG, g, noG], true).
testify(ohta, [_, _, noG, noG, _], lie).
青木の証言が正しいとすると、[noG, _, noG, _, _]となり、青木と臼田は犯人ではないことになる。青木の証言がウソだとすると、[g, noG, noG, noG, noG] or[noG, noG, g, noG, noG]ということで、青木もしくは臼田が犯人だということなる。ここで、犯人は1人であることが分かっているので、もし青木が犯人だとそれ以外はみんな犯人でないことがわかる点も状態に含めてある。
もう少し簡便に記述する方法がある気がするが、現時点ではこれが精一杯だった。
2. リストの中にある要素が何個あるかを数える術語の定義
「犯人はだれだ？」問題に限った定義ではないが、あるリストの中に知りたい要素が何個あるかを数えることができる術語を定義した。
これは、「犯人は1人のみである」ことや「ウソつきは2人である」ことを担保する必要があるため。
% リストの中にある要素が何個あるかを数える
count(_, [], 0).
count(X, [X | Xs], M) :-
count(X, Xs, N), M is N + 1.
count(X, [Y |Xs], N) :-
X \= Y, count(X, Xs, N).
再帰定義を使って、リストの冒頭から一個ずつある要素に該当するかをチェックしながら合計要素数を積算するイメージ。
3. 犯人とウソつきを特定する術語の定義
最後に、各人の証言と、犯人は1人、ウソつきは2人であるという制約条件を同時に満たすような状態をPrologで探索するための術語を定義する。
% 犯人と嘘つきを推理
detective(State, [A, I, U, E, O]) :-
testify(aoki, State, A),
testify(iijima, State, I),
testify(usuda, State, U),
testify(enomoto,State, E),
testify(ohta, State, O),
count(g, State, 1),
count(lie, [A, I, U, E, O], 2).
detective(State, [A, I, U, E, O])のStateが犯人かどうかのリストであり、[A, I, U, E, O]が各人がウソをついているかどうかのリストになる。これらを所与とすると5人の証言（2人のウソ込み）を同時に満たすような犯人が誰であるかを確認していく。最後の2行のcount(・)で犯人は1人かどうか、ウソつきは2人かどうかをチェックしている。
答え出力
Prologの出力結果は以下である。
?- detective(State, [A, I, U, E, O])
A = I, I = O, O = true,
E = U, U = lie,
State = [noG, noG, noG, g, noG]
false
見やすいように書き直すと、下記のようになる。
| 犯人？ | 証言 | |
|---|---|---|
| 青木 | 無実 | 真実 |
| 飯島 | 無実 | 真実 |
| 臼田 | 無実 | ウソ |
| 榎本 | 犯人 | ウソ |
| 太田 | 無実 | 真実 |
よって、榎本が犯人で、臼田と榎本がウソをついていたことになる。興味のある方は問題と見比べながらこの答えが正しいことを確認してみてください。
最後の行のfalseは、上記以外の答えがないかを確認した結果になる。falseなので上記解が唯一の解であることが分かった。
余談だか、それぞれの証言をした背景を考えてみると推理小説ぽくて面白い。
答えを知ってから改めて証言を見てみると、太田はなかなかスルドい証言をしていることに気づく。一方で青木と飯島は「僕たちじゃない！」という保身の証言しかしていない。臼田はきっと榎本をかばおうとして捜査のかく乱目的にウソの証言をしたのだろう。
どのようなシチュエーションだったのかなと想像してみる。
人気のないほの暗い夜道、恋人との激しい口喧嘩をしていた榎本はうっかり恋人をつき飛ばし、打ち所の悪かった恋人を殺害してしまう。
そこに偶然通りがかった親友の臼田。一瞬で状況を察した臼田は榎本に自首を勧めるが、榎本は断固拒否する。二人はしばらく口論した後、とりあえず現場から逃げることにする。
事件の現場が見渡せる位置に太田の自宅があり、太田は眉をひそめて外の騒ぎを見ていた。ただ、暗がりでもあったので「誰かが口論しててうるさいな」程度しか分からなかった。
一方、飲み会帰り青木と飯島は、榎本と臼田の口論を遠くから目にする。しかし、泥酔していたのもあって特に気も留めず通り過ぎる。
翌日、事件が発覚し、各人は刑事の尋問を受けることになった。
参考
コーディングにあたっては下記文献およびサイトを参照した。