ネットで見つけた以下の川渡り問題をPrologで解いてみました。

おなじみのやつですね。

Art of Prologとかm.hiroiさんのホームページでも載っていました。

問題：

ある家族がいて、舟を使って川を向こう岸へ渡ろうとしています。
この家族は父、母、息子１、息子２、娘１、娘２、メイド、犬、じっちゃん、
赤ん坊の１０人家族(犬も１人と数えます)です。
舟は１艘(そう)しかなく、１度に２人まで乗ることができます。
また、この舟をこげるのは父と母とメイドとじっちゃんの４人です。

父は、母がいなくなると娘を殺してしまいます。
母は、父がいなくなると息子を殺してしまいます。
じっちゃんは、親がいないと息子や娘、赤ん坊を殺してしまいます。
息子や娘は、親がいないと赤ん坊を殺してしまいます。
犬は、メイドがいないと家族をみんな殺してしまいます。

みんなが無事に川を渡り切るには、どのような手順で渡ればよいでしょうか？

プログラム解説：

盤面生成→チェック → 再帰で次の盤面生成 → チェック → … → クリアするまで繰り返し
失敗すれば バックトラックで次の選択肢を試す
Prologで何も考えずに深さ優先探索で解いています。
枝刈りを行っていず効率の悪いプログラムですが、この程度の問題だと全然問題ないようです。

現在の状態は以下の形式のcompound termで表しています。

state(左岸にいる人のリスト,船に乗っている人のリスト,右岸にいる人のリスト,船の位置(left , right , crossing のいずれか))

assertで生成したstateを登録するようにして、登録済のstateには遷移しないようにしています(意味のない行ったり来たりを防ぐ)

assertする際 順列ではなく組み合わせで登録したいため、リスト内をソートしてから登録しています。

この程度のプログラムだとあまり考えず機械的作業で量産できるようになってきた。

プログラム：

実行結果：
（下から上に答えに近づいていきます）