川渡り問題
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/03/05 08:22 UTC 版)
 | この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。（2016年12月） |
川渡り問題（かわわたりもんだい）は、川岸にいる一団を特定の条件を満たしながら対岸に渡すパズルである。通常論理パズルに分類される。
川に架かっているすべての橋を一度だけ渡る経路を考える問題に関しては一筆書きを参照。
ルール
- 川岸にいる一団を対岸に渡す。
- 川を渡る手段は小船だけであり、小さいので全員は乗れないため、小分けにして往復する必要がある。
- 「小船を漕げる者が限定されており、その者が小船に乗っていないと移動できない」という条件が与えられる場合もある。
- 特定の組み合わせがどちらかの岸にできてはいけない。
- 多くは「○○がいない状態で□□と△△を一緒にしてはいけない」という形で条件が与えられる。
例題
簡単な例
1人の大人と2人の子供が岸にいて、ボートが1艘ある。ボートには、大人は1人だけが乗れ、子供は1人または2人が乗れる（ボートを漕ぐことは全員が可能）。全員が川を渡るにはどうすればよいか?
狼とヤギとキャベツ
この問題は、8世紀にカンタベリーの大主教が提示した問題といわれている。
オオカミとヤギを連れ、キャベツを持った農夫が川岸にいる。川には1艘のボートがある。
- ボートを漕げるのは農夫のみ。
- ボートには農夫のほか、動物1頭かキャベツ1個しか乗せられない。
- 農夫がいないときにオオカミとヤギを岸に残すと、オオカミがヤギを食べてしまう。
- 農夫がいないときにヤギとキャベツを岸に残すと、ヤギがキャベツを食べてしまう。
すべてを無事に対岸に渡すにはどうしたらよいか?
オオカミを狐、ヤギをガチョウ、キャベツを豆の袋に替えた問題もある。
宣教師と先住民
3人の宣教師と3人の先住民が川岸にいる。川には2人まで乗れるボートが1艘ある。
- ボートを漕げるのは宣教師のうちの1人と、先住民のうちの1人だけである。
- どちらかの岸で先住民の数が宣教師の数より多くなると、先住民は反旗を翻し宣教師に襲い掛かる。
全員が無事に対岸に渡るにはどうしたらよいか?
考え方
禁止されている状態にならないように移動させていれば、ほぼ一本道で解けてしまうこともある。
下記の点を考えるとうまくいくことが多い。
- ボートをこげる人を確保する。
- 対岸に渡した人（物）を，後でもう一度連れて帰る。
- 最初は，2人以上（または1人と何か）で渡るしかない。
- もし1人だけで渡ると，その1人が戻って来るしかないので，始めの状態に戻ってしまうから。
また、コンピュータプログラムで（普通のプログラミング言語で、あるいは論理プログラミングや何らかのソルバー等で）コンピュータに解かせようとする場合、問題の文としては明示されない（が、論理的に詰めてゆくと必要な）制約や可能な移動についての規則の追加が必要なこともある[1]。
バリエーション
一団の条件を変えれば新しい問題を作ることができる。嫉妬深い（自分がいないところで妻が他の男といるのが嫌という）夫婦たちの問題などが有名である。
また、
- 川の途中に中州を設ける。（人や荷物を置くことができる）
- ボートの定員や台数を変える。
等で新しい問題を作ることもできる。
問題の性質
解いてみなくても、次のことが分かる。
- 解の手数（ボートの移動回数）は、奇数である。
- ボートは、初めはこちら岸にあり、最後は向こう岸に行く。初めから何度往復するにせよ、往復してボートがこちら岸に戻ったときのボートの移動は常に偶数回である。最後に向こう岸に渡るためにはもう1回移動するので、合計の移動回数は奇数回になる。
- 半数が渡るところを中心として、（最少手数で一意の）解は対称になる。
- 渡り切った最終状態から解を逆順にたどると、最初の状態に戻ることができる。その手順は、向こう岸からこちら岸への川渡り問題の解になっている。向こう岸とこちら岸とを入れ替えて考えると元の解と一致するので、解は対称になる。
したがって、解を作成していて半数が渡ったら、その後はそこまでの手順を（こちら岸と向こう岸とを入れ替えて）逆にたどればよい。
例題の解答
- 簡単な例
-
- 子供2人が渡る（ → 大人がこちら側、子供2人が向こう岸）
- 子供のうち1人だけが戻る（ → 大人と子供1人がこちら側、子供もう1人が向こう岸）
- 戻ったボートに大人が乗って渡る（ → 子供1人がこちら側、大人と子供もう1人が向こう岸）
- 子供1人が戻る（ → 子供2人がこちら側、大人が向こう岸）
- 子供2人が渡る（ → 全員が向こう岸）
- 農夫の問題
-
- ヤギを連れて渡る（ → オオカミとキャベツがこちら側、農夫とヤギが向こう岸）
- 戻る（ → 農夫とオオカミとキャベツがこちら側、ヤギが向こう岸）
- オオカミを連れて渡る（ → キャベツがこちら側、農夫とオオカミとヤギが向こう岸）
- ヤギを連れて戻る（ → 農夫とヤギとキャベツがこちら側、オオカミが向こう岸）
- キャベツを持って渡る（ → ヤギがこちら側、農夫とオオカミとキャベツが向こう岸）
- 戻る（ → 農夫とヤギがこちら側、オオカミとキャベツが向こう岸）
- ヤギを連れて渡る（ → 全員が向こう岸）
- 宣教師と先住民
- 以下、m はボートを漕げない宣教師、M はボートを漕げる宣教師、i はボートを漕げない先住民、I はボートを漕げる先住民とする。
- Ii が渡り、I が戻る。
- Ii が渡り、I が戻る。
- Mm が渡り、Mi が戻る。
- MI が渡り、Mi が戻る。
- Mm が渡り、I が戻る。
- Ii が渡り、I が戻る。
- Ii が渡る。
注
- ^ 一例として、ナイーブにコードを書くと宣教師の問題で「宣教師が0人」という状態を「宣教師の方が人数が少ない」として誤って不正解としてしまう、といったものがある。
- 川渡り問題のページへのリンク
