川渡りパズルのはなし

農夫がオオカミとヤギとキャベツを連れて川を渡ります。船には農夫のほかに、1つしか乗せられません。 農夫がいない岸でオオカミとヤギを一緒にするとヤギが食べられ、ヤギとキャベツを一緒にするとキャベツが食べられてしまいます。 どう運べばよいでしょうか。答えを見つける鍵は、「運ぶ」だけでなく「連れて戻る」ことです。

最短は7回、鍵は「連れて戻る」

まずヤギを渡します。残った岸は、オオカミとキャベツだけなので安全です。次に農夫が1人で戻り、オオカミ（かキャベツ）を渡します。 ここで、ヤギを連れて戻ります。ヤギを置いたままだと、向こう岸でヤギとオオカミ（かキャベツ）が一緒になってしまうからです。 戻ったら、ヤギをおろしてキャベツ（かオオカミ）を渡し、農夫は1人で戻り、最後にヤギを渡します。合計7回です。 オオカミとキャベツの順番を入れかえても、同じ7回で運べます。

物語は「戻ってはいけない」とは言っていません。それでも、せっかく渡したものを連れ戻すのは、なかなか思いつきません。

このサイトのプログラムで、あり得る状態をすべて調べました。はじめから進んでいける状態のうち、食べられずに済むのは10通りだけで、最短が7回であることも確かめました。

1000年以上前の問題集にある

この種のパズルは、ラテン語の問題集『若者を鍛える問題集』に載っています。残っている最古の写本は9世紀の後半のものです。 そこにはオオカミ・ヤギ・キャベツのほか、いくつかの川渡りの問題があります。この本は、ヨークのアルクインという学者が書いたと伝えられていますが、本当にそうなのかは、はっきりしていません。

これは「現在残っている記録のなかでは最も古いものの一つ」という意味で、もっと前から遊ばれていた可能性はあります。

登場人物だけが着せ替わる

同じしくみのパズルは、時代や場所によって、別の登場人物で語られてきました。 アルクインの本には、兄弟と姉妹の組が出てきます。のちの時代には、夫婦が出てくる「嫉妬深い夫」の形になった、とされています。 さらに19世紀の終わりごろには、別の2種類の登場人物を使った形が現れ、のちにAI（人工知能）の入門でよく取り上げられました。 ただ、その題材は特定の人々のイメージを遊びに持ち込みかねないため、このサイトでは使いません。中立な題材だけを使います。

アフリカの各地の民話や、日本の「虎の子渡し」の絵にも、似た話があるとされています。動物や食べ物は違っても、「一緒にしてはいけない組がある」という形は同じです。

このサイトの「操縦士とドローン」は、そのような組をなくした、中立な川渡りです。操縦士とドローンを、船は1〜2人（台）ずつ運びます。 どちらの岸でも、操縦士がいるならドローンの数が操縦士の数を超えてはいけません。 各2のときは5回、各3のときは11回が最短です。どちらもプログラムで確かめました。

状態の地図にする

AIの世界では、このパズルは「状態の地図」で解く定番の題材です。誰がどちらの岸にいるかを1つの「状態」とし、船で渡って変わる関係を線で結びます。 食べられてしまう状態は地図から外します。あとは、はじめの状態から終わりの状態までの道を探すだけです。人が頭の中でやっていることを、点と線に置きかえたものです。 作品ページでは、この地図を見ながら、いま自分がどこにいるかを確かめられます。

解くときの考え方

• 何を運ぶかより、何を残すかを見る。船に乗せるものより、留守の岸に残るものが安全かどうかが大切です。
• 両方の禁止に関わるものを探す。オオカミ・ヤギ・キャベツでは、ヤギがどちらの組にも入っています。だから、ヤギは最初に運び、途中で連れて戻ります。
• 戻る手も使う。1歩下がることが、行き詰まりをほどくことがあります。
• どちらの岸も確認する。操縦士とドローンのように、両岸にルールがあるときは、船が着いた側だけでなく出発した側も見ます。

行き詰まったら、作品ページの「ヒント」で考え方から順に見られます。最後のヒントは、最短の道の次の1手を教えてくれます。