川渡りパズル10選｜論理的に考える渡河問題集
川渡りパズルは、特定の制約条件のもとで人や物を川の向こう岸に渡す方法を考える論理パズルです。中世ヨーロッパから伝わる古典的なパズルで、プログラミングの教材としても活用されています。シンプルな設定の中に意外な難しさがあり、論理的思考力を鍛える絶好の問題です。
この記事では、代表的な川渡りパズルを10問紹介します。それぞれの問題にじっくり取り組んでから解答を確認してください。
問題編
第1問：農夫の渡河（難易度：初級）
農夫がオオカミ、ヤギ、キャベツを連れて川を渡ろうとしています。ボートには農夫のほかに1つだけ載せられます。農夫がいないと、オオカミはヤギを食べ、ヤギはキャベツを食べてしまいます。全員を無事に渡すにはどうすればよいでしょうか？
第2問：家族の渡河（難易度：初級）
父、母、息子2人、娘2人の6人家族が川を渡ります。ボートは2人乗りで、ボートを漕げるのは父と母だけです。全員を渡すための最小手順を考えてください。
第3問：3組のカップル（難易度：中級）
3組のカップル（夫婦）が川を渡ります。ボートは2人乗りです。どの妻も、自分の夫がいない場所で他の夫と2人きりになってはいけません。最小何回の渡河で全員を渡せるでしょうか？
第4問：ろうそくの橋渡り（難易度：中級）
4人が夜に橋を渡ります。橋は同時に2人までしか渡れず、懐中電灯が1本だけ必要です。渡る速度はそれぞれ1分、2分、5分、10分で、2人で渡るときは遅い方の速度になります。全員が17分以内に渡るにはどうすればよいでしょうか？
第5問：兵士と子供（難易度：初級）
川岸に2人の子供と多数の兵士がいます。ボートは子供2人か大人1人しか乗れません。兵士を全員渡すにはどうすればよいでしょうか？
第6問：3人の嫉妬深い夫（難易度：上級）
問題3の発展版です。3組の夫婦が川を渡りますが、ボートは2人乗りです。どの妻も自分の夫なしに他の男性がいる場所にいてはなりません（ボートの中も含む）。最小手順を求めてください。
第7問：宣教師と人食い人種（難易度：中級）
3人の宣教師と3人の人食い人種が川を渡ります。ボートは2人乗りです。どちらの岸でも人食い人種の数が宣教師の数を上回ってはいけません（宣教師が0人の場合は除く）。全員を渡す手順を考えてください。
第8問：重さ制限の渡河（難易度：中級）
4人の体重がそれぞれ50kg、60kg、70kg、80kgで、ボートの重量制限は130kgです。最大2人まで乗れます。全員を渡すための最小手順は？
第9問：島経由の渡河（難易度：上級）
川の中央に島があります。3人の夫婦が川を渡りますが、ボートは2人乗りで、各岸と島でも「妻が夫なしに他の男性といてはならない」ルールが適用されます。解法を考えてください。
第10問：時間制限付き渡河（難易度：上級）
5人が川を渡ります。渡る速度はそれぞれ1分、3分、6分、8分、12分です。ボートは2人乗りで懐中電灯は1本。2人で渡るときは遅い方の速度です。全員が渡る最短時間は何分でしょうか？
解答編
第1問の解答
- 農夫がヤギを渡す
- 農夫が戻る
- 農夫がオオカミを渡す
- 農夫がヤギを連れて戻る
- 農夫がキャベツを渡す
- 農夫が戻る
- 農夫がヤギを渡す
解説: ポイントはヤギを一度連れ戻すことです。ヤギはオオカミにもキャベツにも関係するため、ヤギの位置管理が鍵になります。この問題は8世紀の学者アルクインの著書にも登場する歴史ある問題です。
第2問の解答
この問題は実は標準的な条件では解けません。ボートを漕げるのが父と母だけであるため、子供だけでボートを戻すことができないのです。条件を「子供もボートを漕げる」と変更すれば解けるようになります。その場合は9回の渡河で全員を渡せます。
第3問の解答
最小11回の渡河で解けます。
- 夫A・妻Aが渡る → 2. 夫Aが戻る → 3. 妻B・妻Cが渡る → 4. 妻Aが戻る → 5. 夫A・夫Bが渡る → 6. 夫B・妻Bが戻る → 7. 夫B・夫Cが渡る → 8. 妻Aが戻る → 9. 妻A・妻Bが渡る → 10. 妻Cが戻る → 11. 妻A・妻Cが渡る（一例）
解説: 制約条件を満たしながらの渡河は手順が多くなります。ポイントは夫婦のペアを崩さざるを得ない場面でどう対処するかです。
第4問の解答
17分で渡る手順:
- 1分と2分が渡る（2分経過、合計2分）
- 1分が戻る（1分経過、合計3分）
- 5分と10分が渡る（10分経過、合計13分）
- 2分が戻る（2分経過、合計15分）
- 1分と2分が渡る（2分経過、合計17分）
解説: 直感的には速い人が何度も往復すべきと思いがちですが、遅い2人を同時に渡らせることが最適解の鍵です。5分と10分を別々に渡すと15分＋5分＝20分かかりますが、一緒に渡せば10分で済みます。
第5問の解答
- 子供2人が向こう岸へ渡る
- 子供1人がボートを持って戻る
- 兵士1人が向こう岸へ渡る
- 向こう岸の子供がボートを持って戻る
- 手順1〜4を兵士全員分繰り返す
解説: 子供2人がシャトル役を務めます。兵士1人を渡すのに4回の渡河が必要です。兵士がN人いる場合、合計4N+1回の渡河が必要になります。
第6問の解答
ボートの中も条件に含む場合、3組では解けないケースがあります。島が中央にある条件を追加するか、ボートの定員を3人にすれば解けるようになります。この問題は制約条件の厳しさによって解の有無が変わる興味深い例です。
第7問の解答
- 人食い2人が渡る → 2. 人食い1人が戻る → 3. 人食い2人が渡る → 4. 人食い1人が戻る → 5. 宣教師2人が渡る → 6. 宣教師1人・人食い1人が戻る → 7. 宣教師2人が渡る → 8. 人食い1人が戻る → 9. 人食い2人が渡る → 10. 人食い1人が戻る → 11. 人食い2人が渡る
解説: 各段階で両岸の宣教師と人食い人種の数を確認しながら進める必要があります。11回の渡河が最小手順です。
第8問の解答
50kgと60kgの2人がペアを組めます（合計110kg、制限内）。
- 50kgと60kgが渡る → 2. 50kgが戻る → 3. 50kgと70kgが渡る → 4. 50kgが戻る → 5. 50kgと80kgが渡る（しかし130kgなのでギリギリOK）
合計5回です。50kgの人がシャトル役になるのが効率的です。
第9問の解答
島を中継地点として使うことで、3組の嫉妬深い夫の問題が解けるようになります。島を一時的な待機場所にして、制約条件を満たしながら段階的に渡河します。手順は長くなりますが、島があることで柔軟な配置が可能になります。
第10問の解答
最短29分で全員が渡れます。基本戦略は問題4と同じで、もっとも速い2人がシャトル役を務め、遅い人同士をペアにして渡らせます。
解説: 6分と8分をペアに、8分と12分をペアにするなど、遅い人の組み合わせを工夫することで合計時間を最小化できます。
まとめ
川渡りパズルは、限られた条件の中で最適な解を見つける論理的思考力が試される問題です。一見シンプルに見える問題でも、制約条件を正確に把握し、すべての段階で条件を満たしているかを確認する注意力が必要です。
これらの問題は古くから多くの人に愛されてきた名問揃いです。紙とペンを使って人の配置を書き出しながら解くと、思考が整理しやすくなります。ぜひじっくり取り組んでみてください。