当サイトを閲覧いただきありがとうございます。 本記事は論理クイズの最古参「川渡り問題」について解説します。
農夫がオオカミとヤギとキャベツを連れて川岸に立っています。舟には農夫のほかに1つしか載せられません。そして農夫が見ていないところでは、オオカミはヤギを食べ、ヤギはキャベツを食べてしまいます。さて、全員を無事に対岸へ運ぶにはどうすればよいでしょうか。子供でも遊べる素朴な問題ですが、これは1200年前の教科書に載っていた、記録に残る最古級の論理パズルであり、現代のAI研究の出発点のひとつでもあります。
川渡り問題とは
川渡り問題（英語では river crossing puzzle、この版は wolf, goat and cabbage problem）とは、輸送手段の容量と「同席させてはいけない組合せ」という2つの制約の下で、全員を対岸へ運ぶ手順を設計するパズルです。ルールを整理しておきます。
・農夫は、オオカミ・ヤギ・キャベツを全部対岸へ運びたい ・舟を漕げるのは農夫だけ。舟には農夫のほか1つしか載せられない ・農夫がいない岸で、オオカミとヤギを2人きりにしてはいけない（ヤギが食べられる） ・農夫がいない岸で、ヤギとキャベツを2人きりにしてはいけない（キャベツが食べられる）
最初の1手から、いきなりこのパズルの性格が見えてきます。オオカミを先に運ぶと、残された岸でヤギがキャベツを食べます。キャベツを先に運ぶと、オオカミがヤギを食べます。つまり初手はヤギを運ぶ一択です。問題は、その次です。2便目で何を運んでも、対岸に置いた瞬間にヤギとの危険なペアができてしまう。ここで多くの人の手が止まります。
カール大帝の宮廷学者が残した原典
このパズルの出典は驚くほど古く、8世紀のヨーロッパまで遡ります。フランク王国のカール大帝に仕えたイングランド出身の学者アルクィン（735年頃〜804年）の作とされる問題集『Propositiones ad Acuendos Juvenes（若者を鍛えるための命題集）』に、オオカミとヤギとキャベツの問題がそのまま収録されているのです。
この問題集はラテン語で書かれた50問あまりのパズル集で、現存する西洋最古級の数学パズル集と評価されています。アルクィンはカール大帝の宮廷学校を率いた当代随一の知識人で、大帝に宛てた手紙の中で「楽しみのための算術の問題」を送ると書き残しており、これがこの問題集の由来と考えられています。皇帝の教養のために作られたパズル集だったわけです。
面白いことに、問題集には川渡りの問題が3問も連続で収められています。17番が「嫉妬深い3人の夫」の問題。夫は自分がいない場で妻が他の男と同席することを許さない、という制約の下で3組の夫婦が2人乗りの舟で川を渡るもので、こちらは11手を要するかなりの難問です。18番が本記事のオオカミとヤギとキャベツ。そして19番は「体重の重い夫婦と2人の子供」の問題で、大人1人分の重さしか運べない舟で家族全員が渡る方法を問うています。制約の種類を変えながら同じ骨格の問題を並べるという構成は、現代の問題集とまったく同じ発想です。
1200年前の教師が、若者や皇帝の頭を鍛えるために川渡り問題を使っていた。パズルというジャンルの息の長さを象徴する事実だと思います。
答えは7手、鍵は4手目にある
最短の答えは7手です。手順を追ってみましょう。
①ヤギを対岸へ運ぶ ②農夫だけで戻る ③オオカミを対岸へ運ぶ ④ヤギを連れて戻る ⑤キャベツを対岸へ運ぶ ⑥農夫だけで戻る ⑦ヤギを対岸へ運ぶ
全体の白眉は、言うまでもなく④です。せっかく対岸へ運んだヤギを、わざわざ元の岸へ連れて戻す。この一見無駄な後退があるからこそ、オオカミとキャベツを安全に対岸へそろえられます。③でオオカミの代わりにキャベツを運ぶ対称形の解もあり、最短解はこの2通りだけです。
そして重要なのは、後退なしの解は存在しないということです。何かを連れ戻す手を禁止すると、この問題は解けなくなります。つまり④は苦肉の策ではなく、論理的に強制された唯一の道なのです。
遠回りが最短ルートになる構造を図で見る
なぜ後退が必須なのかは、パズルを状態の地図として描くとはっきり見えます。
各時点の状況は、オオカミ・ヤギ・キャベツ・農夫がそれぞれどちらの岸にいるかで決まります。組合せは2の4乗で16通り。そこから「ヤギが食べられる」「キャベツが食べられる」状態を除くと、安全な状態は10個だけ残ります。この10個の状態を点として描き、舟の1往復で移れる状態同士を線で結ぶと、スタートからゴールへの道はほぼ一本道になっており、その途中に④の後退が組み込まれていることが分かります。
この見方をすると、川渡り問題は「ひらめきの問題」から「地図上の最短経路の問題」に変わります。そしてこれこそが、コンピュータにパズルを解かせるときの基本戦略です。状態をすべて洗い出し、許される移動でつなぎ、スタートからゴールまでの経路を探索する。状態空間探索と呼ばれるこの枠組みは、人工知能研究の土台のひとつになりました。
実際、AI研究者ソール・アマレルが1968年に発表した古典論文は、川渡り問題の親戚である「宣教師と人食い人の問題」を題材に、問題の表現方法を変えるだけで探索の難しさが劇的に変わることを論じています。以来この種の川渡りパズルは、AIやアルゴリズムの教科書で状態空間探索の最初の例題として使われ続けています。ゲームAIが詰将棋を解くのも、カーナビが経路を探すのも、根っこは農夫とヤギの舟旅と同じなのです。
一時的な後退を許せるかが計画の質を決める
このパズルが日常に投げかける教訓は、前進だけを積み重ねても目的地に着けるとは限らないということだと思います。
たとえばソフトウェア開発のリファクタリングは、いったん動いているものを崩す④の一手です。山登りでは、目の前の斜面を直登するより、一度下って尾根を回り込む方が早いことがあります。キャリアでも、学び直しのための一時的な年収ダウンや役職オフが、長期では最短ルートだったという話は珍しくありません。毎手で成果が増えることを要求する評価は、後退を含む最短ルートを選択肢から消してしまうのです。
もうひとつの教訓は、「同席させてはいけない組合せをまず書き出す」という制約の整理術です。川渡り問題の実務版は、実は身近にあふれています。工程表で同時に走らせてはいけない作業、会議で同席させると紛糾する利害関係者、薬の飲み合わせ、サーバーの同居させてはいけないワークロード。容量の制約と相性の制約を分けて書き出すだけで、こうした段取り問題はぐっと解きやすくなります。
派生問題とコンピュータの解き方
舟に2つ載せられる場合
3手で終わります。①オオカミとキャベツを一緒に運ぶ ②農夫だけで戻る ③ヤギを運んで終了です。オオカミとキャベツは同席しても安全なペアであり、元の岸に残るヤギも1人では何も起こせません。危険人物のヤギを最後まで隔離しておけるので、後退の一手が丸ごと不要になります。制約が同じでも、輸送容量がひとつ増えるだけで難所が消滅するいい例です。
嫉妬深い夫たちと有名バリエーション
アルクィンの問題集に載る3組の夫婦版（2人乗りの舟で11手）のほか、宣教師と人食い人の問題（どの岸でも人食い人が宣教師より多くなってはいけない）が有名です。また、川渡りの親戚として「橋とたいまつの問題」もよく出題されます。渡るのに1分・2分・5分・10分かかる4人が、たいまつ1本と2人ずつの移動で17分で橋を渡り切れるか、という問題で、こちらも「速い2人を先に渡らせて1人を返す」という直感に反する一手が鍵になります。
コンピュータによる解き方
安全な状態を点、舟の移動を線とするグラフを作り、幅優先探索で最短経路を求めるのが定石です。川渡り問題は状態が10個しかないので一瞬で解けますが、同じ枠組みはルービックキューブや15パズルのような状態が膨大な問題にも拡張でき、そこでは枝刈りやヒューリスティック探索が主役になります。問題を状態と遷移に翻訳した時点で勝負の大半は終わっているというのが、アマレルの論文から続く教訓です。
関連する論理クイズ・パラドックス
道路を増やすとかえって渋滞するという交通版「急がば回れ」のブライスのパラドックス、計量手順の設計を問う「12枚のコインと天秤」、1ビットの合図で99人を救う「帽子のパズル」の記事です。
まとめ
本記事は論理クイズの最古参「川渡り問題」について解説しました。如何だったでしょうか。
1200年前にアルクィンが若者に出したこの問題は、初手が一択で、途中に強制された後退があり、最短はぴったり7手という、小さいのに完璧な構造を持っています。そして状態の地図として描き直せば、ひらめき頼みのなぞなぞが、探索アルゴリズムで機械的に解ける問題に変わる。この「表現を変えると難しさが変わる」という体験こそ、川渡り問題が現代まで生き残ってきた理由だと思います。
私は計画が行き詰まったとき、冗談半分で「ヤギを連れて戻る手はないか」と考えることにしています。後退に見える手が、実は唯一の前進かもしれないからです。
論理クイズ・確率パズルの一覧に戻りたい方は以下のリンクからどうぞ。
それでは次の記事も閲覧いただけると幸いです。
📚 シリーズ：論理クイズ・確率パズル（6/11）
