river crossing - Strategy to solve the Missionaries and Cannibals problem

In the Missionaries and Cannibals problem:

Three missionaries and three cannibals must cross a river using a boat which can carry at most two people, under the constraint that, for both banks and the boat, if there are missionaries present on the bank (or the boat), they cannot be outnumbered by cannibals (if they were, the cannibals would eat the missionaries). The boat cannot cross the river by itself with no people on board.

The shortest solution for this puzzle has 11 one-way trips.

What should be the strategy to solve this puzzle for M missionaries and C cannibals, given that M is not less than C, or else the puzzle wouldn't be solvable.

Answer

Let's define a b * c d to represent the state of the river at any given time: a missionaries and b cannibals on the left, c missionaries and d cannibals on the right, and * being < if the boat is on the left and > if the boat is on the right.

The problem starts out in the state M C < 0 0, and we want to get 0 0 > M C.

For the case of M being more than C, here's an algorithm to transfer 1 missionary and 1 cannibal at a time:

• Bring 1 missionary and 1 cannibal over. (M-1 C-1 > 1 1)


• Bring the cannibal back. (M-1 C < 1 0; since M > C, M-1 >= C, as required.)


• Bring 1 missionary and 1 cannibal over again. (M-2 C-1 > 2 1)


• Bring a missionary back. (M-1 C-1 < 1 1).

And then you're left with the case of M-1 missionaries and C-1 cannibals on one side of the river. Just keep repeating this procedure (it works by induction) until you have only missionaries on the left side of the river. Then you're home free.

For M equal to C, I don't think you'll have a solution for M > 3, because the solution for M = 3 already depends on the fact that you can have only cannibals on one side and they won't be able to do anything to the missionaries no matter how many there are on one side.

The part of the solution where this applies looks something like this:

• 3 1 < 0 2


• 1 1 > 2 2


• 2 2 < 1 1


• 0 2 > 3 1

There's no way to get a similar arrangement for anything greater than three, because you can't send enough missionaries at once to balance out the rest of the cannibals.