川渡り問題

川渡り問題（かわわたりもんだい）は、川岸にいる一団を特定の条件を満たしながら対岸に渡すパズルである。通常論理パズルに分類される。
川に架かっているすべての橋を一度だけ渡る経路を考える問題に関しては一筆書きを参照。
例題.
簡単な例.
1人の大人と2人の子供が岸にいて、ボートが1艘ある。ボートには、大人は1人だけが乗れ、子供は1人または2人が乗れる（ボートを漕ぐことは全員が可能）。全員が川を渡るにはどうすればよいか?
狼とヤギとキャベツ.
この問題は、8世紀にカンタベリーの大主教が提示した問題といわれている。
オオカミとヤギを連れ、キャベツを持った農夫が川岸にいる。川には1艘のボートがある。
すべてを無事に対岸に渡すにはどうしたらよいか?
オオカミを狐、ヤギをガチョウ、キャベツを豆の袋に替えた問題もある。
宣教師と先住民.
3人の宣教師と3人の先住民が川岸にいる。川には2人まで乗れるボートが1艘ある。
全員が無事に対岸に渡るにはどうしたらよいか?
考え方.
禁止されている状態にならないように移動させていれば、ほぼ一本道で解けてしまうこともある。
下記の点を考えるとうまくいくことが多い。
また、コンピュータプログラムで（普通のプログラミング言語で、あるいは論理プログラミングや何らかのソルバー等で）コンピュータに解かせようとする場合、問題の文としては明示されない（が、論理的に詰めてゆくと必要な）制約や可能な移動についての規則の追加が必要なこともある。
バリエーション.
一団の条件を変えれば新しい問題を作ることができる。嫉妬深い（自分がいないところで妻が他の男といるのが嫌という）夫婦たちの問題などが有名である。
また、
等で新しい問題を作ることもできる。
問題の性質.
解いてみなくても、次のことが分かる。
したがって、解を作成していて半数が渡ったら、その後はそこまでの手順を（こちら岸と向こう岸とを入れ替えて）逆にたどればよい。