🔴 Riddle #80 of 240
Four missionaries and four cannibals must cross a river. The boat now holds up to three people, but the old rule stands: on either bank, cannibals must never outnumber missionaries (when any missionary is present). How many crossings does the fastest safe plan take?
Think about it first. When you're ready:
9 crossings
Send 2 cannibals, return 1, send 3 cannibals, return 1, send 3 missionaries, return 1 missionary and 1 cannibal, send 2 missionaries, return 1 cannibal, send the last 3 cannibals; a breadth-first search confirms 9 is the minimum for a three-person boat.