川渡り問題

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索

川渡り問題(かわわたりもんだい)は、川岸にいる一団を特定の条件を満たしながら対岸に渡すパズルである。通常論理パズルに分類される。

川に架かっているすべての橋を一度だけ渡る経路を考える問題に関しては一筆書きを参照。

ルール[編集]

  • 川岸にいる一団を対岸に渡す。
  • 川を渡る手段は小船だけであり、小さいので全員は乗れないため、小分けにして往復する必要がある。
    • 「小船を漕げる者が限定されており、その者が小船に乗っていないと移動できない」という条件が与えられる場合もある。
  • 特定の組み合わせがどちらかの岸にできてはいけない。
    • 多くは「○○がいない状態で□□と△△を一緒にしてはいけない」という形で条件が与えられる。

例題[編集]

簡単な例[編集]

1人の大人と2人の子供が岸にいる。ボートが1艘あるが大人1人か子供2人までしか乗れない(ボートを漕ぐことは全員が可能)。全員が川を渡るにはどうすればよいか?

狼とヤギとキャベツ[編集]

この問題は、8世紀にカンタベリーの大主教が提示した問題といわれている。

オオカミヤギを連れ、キャベツを持った農夫が川岸にいる。川には1艘のボートがある。

  • ボートを漕げるのは農夫のみ。
  • ボートには農夫のほか、動物1頭かキャベツ1個しか乗せられない。
  • 農夫がいないときにオオカミとヤギを岸に残すと、オオカミがヤギを食べてしまう。
  • 農夫がいないときにヤギとキャベツを岸に残すと、ヤギがキャベツを食べてしまう。

すべてを無事に対岸に渡すにはどうしたらよいか?

オオカミを狐、ヤギをガチョウ、キャベツを豆の袋に替えた問題もある。

宣教師と先住民[編集]

3人の宣教師と3人の先住民が川岸にいる。川には2人まで乗れるボートが1艘ある。

  • ボートを漕げるのは宣教師のうちの1人と、先住民のうちの1人だけである。
  • どちらかの岸で先住民の数が宣教師の数より多くなると、先住民は反旗を翻し宣教師に襲い掛かる。

全員が無事に対岸に渡るにはどうしたらよいか?

考え方[編集]

禁止されている状態にならないように移動させていればそのまま解けてしまうこともある。

他には

  • ボートをこげる人を確保する
  • 対岸に渡した人(物)をもう一度連れて帰る

といった点を考えるとうまくいくことが多い。

また、コンピュータプログラムで(普通のプログラミング言語で、あるいは論理プログラミングや何らかのソルバー等で)コンピュータに解かせようとする場合、問題の文としては明示されない(が、論理的に詰めてゆくと必要な)制約や可能な移動についての規則の追加が必要なこともある[1]

バリエーション[編集]

一団の条件を変えれば新しい問題を作ることができる。嫉妬深い(自分がいないところで妻が他の男といるのが嫌という)夫婦たちの問題などが有名である。

また、

  • 川の途中に中州を設ける。(人や荷物を置くことができる)
  • ボートの定員や台数を変える。

等で新しい問題を作ることもできる。

例題の解答[編集]

簡単な例
  1. 子供2人が渡る( → 大人がこちら側、子供2人が向こう岸)
  2. 子供のうち1人だけが戻る( → 大人と子供1人がこちら側、子供もう1人が向こう岸)
  3. 戻ったボートに大人が乗って渡る( → 子供1人がこちら側、大人と子供もう1人が向こう岸)
  4. 子供1人が戻る( → 子供2人がこちら側、大人が向こう岸)
  5. 子供2人が渡る( → 全員が向こう岸)
農夫の問題
  1. ヤギを連れて渡る( → オオカミとキャベツがこちら側、農夫とヤギが向こう岸)
  2. 戻る( → 農夫とオオカミとキャベツがこちら側、ヤギが向こう岸)
  3. オオカミを連れて渡る( → キャベツがこちら側、農夫とオオカミとヤギが向こう岸)
  4. ヤギを連れて戻る( → 農夫とヤギがこちら側、オオカミとキャベツが向こう岸)
  5. キャベツを持って渡る( → ヤギがこちら側、農夫とオオカミとキャベツが向こう岸)
  6. 戻る( → 農夫とヤギがこちら側、オオカミとキャベツが向こう岸)
  7. ヤギを連れて渡る( → 全員が向こう岸)
宣教師と先住民
以下、m はボートを漕げない宣教師、M はボートを漕げる宣教師、i はボートを漕げない先住民、I はボートを漕げる先住民とする。
  1. Ii が渡り、I が戻る。
  2. Ii が渡り、I が戻る。
  3. Mm が渡り、Mi が戻る。
  4. MI が渡り、Mi が戻る。
  5. Mm が渡り、I が戻る。
  6. Ii が渡り、I が戻る。
  7. Ii が渡る。

[編集]

  1. ^ 一例として、ナイーブにコードを書くと宣教師の問題で「宣教師が0人」という状態を「宣教師の方が人数が少ない」として誤って不正解としてしまう、といったものがある。