[Prologで論理パズル] 川渡り問題；危険な家族

論理パズルを解きながらPrologの勉強をするシリーズ。
論理学にある程度親しんでいると、「かつ（∧）」「または（∨）」「ならば（⇒）」などの命題論理記号を活用することでかなり幅広い論理的推論ができることを実感できる。
Prologは（規則を適切に設定できれば）論理的な推論を自動で実行してくれるのでとても楽だ。

今回は川渡り問題クラスの中でも難易度が高いバージョン、「危険な家族」問題を解いてみる。
このサイトによれば、「日本では、「クイズ大陸」さん等の紹介で、ロジックパズルを代表する問題になりました。」とのこと。2003年時点の記事なので、ずいぶん前に一世風靡したパズルのようですね。

論理パズル「危険な家族」

■問題
ある家族が、舟で川を左岸から右岸へ渡ろうとしている。
家族は父、母、息子A、息子B、娘C、娘D、執事、犬の8人(犬も1人と数える)。
舟は1艘しかないが、1度に2人まで乗ることができる。
舟を漕げるのは父、母、執事の3人だけである。
父は、母がそばにいないと娘たちを殺してしまう。
母は、父がそばにいないと息子たちを殺してしまう。
犬は、執事ががそばにいないと家族全員を殺してしまう。
全員が無事に川を渡り切るには、どうすればよいだろうか?

かなり危険な家族。恐らく息子たちは父の連れ子、娘たちは母の連れ子で、川を渡った先に遺産相続が待っている、とかそんな状況なのだろう。
不可解なのは犬。ペットとしても番犬としても役に立たないのになぜ飼っているのだろうか。

論理パズとしてはかなり難しい部類に入るのではないか。紙と鉛筆なしで解くことができる人はすごいと思う。パズルとしても面白いのでPrologに興味がない人も解いて頂ければと思います。
ヒントとしては、執事が初期と最後の方で思わぬ活躍をすることですかね。

実行環境

Prologをクイックに実行する環境として、SWISHを利用。
これはクラウド上でSWI-Prologを実行できるので、Prologに興味を持った人は触ってみてください。
ちなみに、SWI-Prologとは、「多くのUNIXやMS-Windows で利用することが出来るエジンバラProlog (DEC-10 Prolog) 記法を採用したProlog処理系であり、ISO規格 にも準拠している」、らしい。（詳細はこちらを参照）

Prologコーディング

「川渡り問題；オオカミとヒツジとキャベツ」で活用したコードをベースにお気楽 Prolog プログラミング入門; パズル「農夫と狼と山羊とキャベツ」というサイトを参考にしながらコーディングしました。（毎度お世話になります。）

状態の定義

まずは危険な家族問題を定式化するための状態を定義する。
「川渡り問題；オオカミとヒツジとキャベツ」と同様、各人が左岸にいるか、右岸にいるかをリストとして定義する。ただし、今回は舟を漕ぐことができる人が3人いるため、舟がどこにあるかも状態として記憶しておく必要がある。そうじゃないと、父が舟で右岸に行った直後、（舟が勝手に左岸に戻り）母が舟で右岸に行く、ということも起こり得てしまう。
ということで、父、母、息子A、息子B、娘C、娘D、執事、犬、舟の9要素を持つリストを状態として定義する。例えば[left, left, left, left, left, left, right, right, right]は、父、母、息子たち、娘たちは左岸にいて、執事と犬と舟が右岸にいる状態を表す。

これにより、パズルの初期状態が[left, left, left, left, left, left, left, left, left]であり、実行可能な推論規則を使ってゴールの状態である[right, right, right, right, right, right, right, right, right]へ辿り着くことが、この問題の解答となる。

推移規則の定義

「川渡り問題；オオカミとヒツジとキャベツ」と同様、推移規則については下記の要素に分けることができる。
1. 舟を使った移動によりある状態から次の状態へ推移する規則の定義
2. 息子が母に殺されたり、娘が父に殺されたり、犬が誰かを食べたりしない状況の定義
3. （上記を所与として）どのような条件が満たされると次の状態への推移が成功し、最終的にゴールの状態へとたどり着くことが可能かの定義
4. 出力の定義

1. 移動の定義

移動については、move(元の状態、行動、行動後の状態)という述語で定義する。この述語で元の状態から「ある行動」を選択することにより行動後の状態へと推移することを記述する。
「誰が」「誰を連れて」「どちらの岸に行くか」という要素ごとにmoveがあるので、かなり多くのmoveを定義する必要がある。

% 父の移動
move([F ,M, Sa, Sb, Dc, Dd, B, D, F]  ,   Action,   [NF ,M, Sa, Sb, Dc, Dd, B, D, NF] ) :-
    (F == left -> Action = f2Right, NF = right; Action = f2Left, NF = left).        %父のみ移動
move([F ,F, Sa, Sb, Dc, Dd, B, D, F]  ,   Action,   [NF ,NF, Sa, Sb, Dc, Dd, B, D, NF] ) :-
    (F == left -> Action = fM2Right, NF = right; Action = fM2Left, NF = left).      %父と母移動
move([F ,M, Sa, Sb, Dc, Dd, F, D, F]  ,   Action,   [NF ,M, Sa, Sb, Dc, Dd, NF, D, NF] ) :-
    (F == left -> Action = fB2Right, NF = right; Action = fB2Left, NF = left).      %父と執事移動
move([F ,M, F, Sb, Dc, Dd, B, D, F]  ,   Action,   [NF ,M, NF, Sb, Dc, Dd, B, D, NF] ) :-
    (F == left -> Action = fSa2Right, NF = right; Action = fSa2Left, NF = left).    %父と息子A移動
move([F ,M, Sa, F, Dc, Dd, B, D, F]  ,   Action,   [NF ,M, Sa, NF, Dc, Dd, B, D, NF] ) :-
    (F == left -> Action = fSb2Right, NF = right; Action = fSb2Left, NF = left).    %父と息子B移動

% 母の移動    
move([F ,M, Sa, Sb, Dc, Dd, B, D, M]  ,   Action,   [F ,NM, Sa, Sb, Dc, Dd, B, D, NM] ) :-
    (M == left -> Action = m2Right, NM = right; Action = m2Left, NM = left).        %母のみ移動
move([F ,M, Sa, Sb, Dc, Dd, M, D, M]  ,   Action,   [F ,NM, Sa, Sb, Dc, Dd, NM, D, NM] ) :-
    (M == left -> Action = mB2Right, NM = right; Action = mB2Left, NM = left).      %母と執事移動
move([F ,M, Sa, Sb, M, Dd, B, D, M]  ,   Action,   [F ,NM, Sa, Sb, NM, Dd, B, D, NM] ) :-
    (M == left -> Action = mDc2Right, NM = right; Action = mDc2Left, NM = left).    %母と娘C移動
move([F ,M, Sa, Sb, Dc, M, B, D, M]  ,   Action,   [F ,NM, Sa, Sb, Dc, NM, B, D, NM] ) :-
    (M == left -> Action = mDd2Right, NM = right; Action = mDd2Left, NM = left).    %母と娘D移動

% 執事の移動    
move([F ,M, Sa, Sb, Dc, Dd, B, D, B]  ,   Action,  [F ,M, Sa, Sb, Dc, Dd, NB, D, NB] ) :-
    (B == left -> Action = b2Right, NB = right; Action = b2Left, NB = left).        %執事のみ移動
move([F ,M, B, Sb, Dc, Dd, B, D, B]  ,   Action,   [F ,M, NB, Sb, Dc, Dd, NB, D, NB] ) :-
    (B == left -> Action = bSa2Right, NB = right; Action = bSa2Left, NB = left).    %執事と息子A移動
move([F ,M, Sa, B, Dc, Dd, B, D, B]  ,   Action,   [F ,M, Sa, NB, Dc, Dd, NB, D, NB] ) :-
    (B == left -> Action = bSb2Right, NB = right; Action = bSb2Left, NB = left).    %執事と息子B移動
move([F ,M, Sa, Sb, B, Dd, B, D, B]  ,   Action,   [F ,M, Sa, Sb, NB, Dd, NB, D, NB] ) :-
    (B == left -> Action = bDc2Right, NB = right; Action = bDc2Left, NB = left).    %執事と娘C移動
move([F ,M, Sa, Sb, Dc, B, B, D, B]  ,   Action,   [F ,M, Sa, Sb, Dc, NB, NB, D, NB] ) :-
    (B == left -> Action = bDd2Right, NB = right; Action = bDd2Left, NB = left).    %執事と娘D移動
move([F ,M, Sa, Sb, Dc, Dd, B, B, B]  ,   Action,  [F ,M, Sa, Sb, Dc, Dd, NB, NB, NB] ) :-
    (B == left -> Action = bD2Right, NB = right; Action = bD2Left, NB = left).      %執事と犬移動

左岸に行くか、右岸に行くかについては元の状態と行動後の状態を逆にすればいいだけなので、一つの術語の中の分岐として定義した。記法はお気楽 Prolog プログラミング入門; パズル「農夫と狼と山羊とキャベツ」を参考にした。
父の移動を例にとると、「父が単独で移動する場合」「父が母と移動する場合」「父が執事と移動する場合」「父が息子と移動する場合」を定義してある。「父が娘と移動する場合」と「父が犬と移動する場合」を定義していないのは、舟の上で惨劇が発生してしまうからである。同様に母の移動と執事の移動も定義した。

2. 「誰も殺されない」状態の定義

次に、誰も殺されない状態を定義する。「オオカミとヒツジとキャベツ」問題では、何かが食べられる状態を定義してそれの否定形を条件として挿入したが、今回は誰も殺されない状態を定義した。

% 誰も殺されない状況
safe(State) :-
    safeSons(State),
    safeDaughters(State),
    safeFromDog(State).

safeSons([F ,M, Sa, Sb, _, _, _, _,_]) :- M == F; (M \== Sa, M \== Sb) .
safeDaughters([F ,M, _, _, Dc, Dd, _, _,_]) :- F == M; (F \== Dc, F \== Dd).
safeFromDog([F ,M, Sa, Sb, Dc, Dd, B, D,_]) :- D == B; (D \== F, D \== M, D \== Sa, D \== Sb, D \== Dc, D \== Dd).

後半のsafeSons(・)、safeDaughters(・)、safeFromDog(・)術語でそれぞれ、母が息子を殺さない状態、父が娘を殺さない状態、犬が誰も殺さない状態を定義し、それを連言として接合したのがsafe(State)である。犬に誰も殺されない状態の定義をもっと簡便にできないか四苦八苦したが残念ながら現在の力ではこれが限界だった。

3. ゴールまでの推移の定義

ある状態から最終的にゴールの状態まで正しく推移できるパスを記述する。

% ゴールまでの推移
cross([[Action | State] | History]) :- 
    State == [right, right, right, right, right, right, right, right, right], !, 
    printAnswer([[Action | State] | History]).

cross([[Action | State] | History]) :-
    move(State, NewAction, NewState),
    safe(State),
    not(member([_ | NewState], History)),
    cross([[NewAction | NewState], [Action | State] | History]).

「オオカミとヒツジとキャベツ」問題とほぼ変更はなし。ただ、not(eat***(・))という「食べられる状況ではない」状態の定義ではなく、safe(State)と「安全な」状態の定義へと変更した。

4. 出力の定義

最後に出力を見やすくするための定義を付けた。
こちらは「オオカミとヒツジとキャベツ」問題から全く変更なし。

% 出力
printAnswer([]) :- !.
printAnswer([[Action | State] | Rest]) :-
    printAnswer(Rest), 
    write(Action), write( ' ' ), write( ==> ), write( ' ' ), write(State), nl. 

答え出力

Prologの出力結果は以下である。

?- cross([[start| [left,left,left,left,left,left,left,left,left]]])
start ==> [left, left, left, left, left, left, left, left, left]
bD2Right ==> [left, left, left, left, left, left, right, right, right]
b2Left ==> [left, left, left, left, left, left, left, right, left]
bSa2Right ==> [left, left, right, left, left, left, right, right, right]
bD2Left ==> [left, left, right, left, left, left, left, left, left]
fSb2Right ==> [right, left, right, right, left, left, left, left, right]
f2Left ==> [left, left, right, right, left, left, left, left, left]
fM2Right ==> [right, right, right, right, left, left, left, left, right]
m2Left ==> [right, left, right, right, left, left, left, left, left]
bD2Right ==> [right, left, right, right, left, left, right, right, right]
f2Left ==> [left, left, right, right, left, left, right, right, left]
fM2Right ==> [right, right, right, right, left, left, right, right, right]
m2Left ==> [right, left, right, right, left, left, right, right, left]
mDc2Right ==> [right, right, right, right, right, left, right, right, right]
bD2Left ==> [right, right, right, right, right, left, left, left, left]
bDd2Right ==> [right, right, right, right, right, right, right, left, right]
b2Left ==> [right, right, right, right, right, right, left, left, left]
bD2Right ==> [right, right, right, right, right, right, right, right, right]
true

全部で17ステップかかった。恐らくこれが最短経路であるはず。
Prolog出力だけでは読みにくいと思うので、解答パスと右岸の状態を下記に記した。

step	行動	右岸の状態
1	執事と犬：右岸へ	[執事、犬]
2	執事：左岸へ	[犬]
3	執事と息子A：右岸へ	[息子A、執事、犬]
4	執事と犬：左岸へ	[息子A]
5	父と息子B：右岸へ	[父、息子A、息子B]
6	父：左岸へ	[息子A、息子B]
7	父と母：右岸へ	[父、母、息子A、息子B]
8	母：左岸へ	[父、息子A、息子B]
9	執事と犬：右岸へ	[父、息子A、息子B、執事、犬]
10	父：左岸へ	[息子A、息子B、執事、犬]
11	父と母：右岸へ	[父、母、息子A、息子B、執事、犬]
12	母：左岸へ	[父、息子A、息子B、執事、犬]
13	母と娘C：右岸へ	[父、母、息子A、息子B、娘C、執事、犬]
14	執事と犬：左岸へ	[父、母、息子A、息子B、娘C]
15	執事と娘D：右岸へ	[父、母、息子A、息子B、娘C、娘D、執事]
16	執事：左岸へ	[父、母、息子A、息子B、娘C、娘D]
17	執事と犬：右岸へ	[父、母、息子A、息子B、娘C、娘D、執事、犬]

　　
5ステップ目と8ステップ目で一見同じ状態を繰り返しているように見えるが、舟の状態が異なる。5ステップ目は舟は右岸にあるが、8ステップ目は舟が左岸にあるので、Prolog上では同じ状態とは認識されない。

はじめに執事と犬で右岸に移動して執事が戻ってきた後、執事が息子Aを連れて再び右岸に行くのが一つ目のポイントといえる。そうすると、左岸に残る息子はあと1人となるので、父の行動の制約が減ることになり、中盤父が頻繁に移動することが可能になる。また、大半の子供たちが右岸に移動した最終局面で、再び執事と犬が左岸に戻ることで、執事の自由度を確保している。（左岸で犬に誰かが食べられてしまうリスクが減少したため。）この辺が2つ目のポイントとなっているのだろう。

当然だが、息子Aと息子B、娘Cと娘Dは完全に互換的だし、さらに息子と娘も構造上同じなのでこれ以外の類似の解答は何通りも存在する。
Prologはコーディングした順番通りに推論を実行するので、今回息子に関する移動を娘よりも先に記述し、息子Aよりも息子Bを先に記述したため、執事が初めに連れていく子供が息子Aとなっている。

論理パズルとして難しめの問題もProlog上では比較的簡単に実装できた上に、実行速度の観点からも「オオカミとヒツジとキャベツ」問題と大差なかった点は素晴らしいと思う。

参考文献

コーディングにあたっては下記文献およびサイトを参照した。
- Ivan Bratko(1990)「Prologへの入門 (PrologとAI) 」, 近代科学社
- お気楽 Prolog プログラミング入門; パズル「農夫と狼と山羊とキャベツ」