# When do missionaries and cannibals problems have solutions?

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, if there are missionaries present on the bank, they cannot be outnumbered by cannibals (if they were, the cannibals would eat the missionaries).

Is there are way to know when a missionaries or cannibals problem has a solution or not (that is assuming that a solution means that no missionaries can be eaten and that boats can only carry two people)?

I have written a program that uses bfs to find possible solutions, and cannot seem to find a solution for 5 missionaries and 5 cannibals. It has worked for other missionaries and cannibals problems, so I'm not sure if my program is flawed or if there is just no solution. Its pretty obvious that in some situations (i.e. 1 missionary, 10 cannibals) there is no solution.

As a follow-up, would it be possible to shed some light on the situations in which missionaries must be eaten. Is there a way to find the minimum number of missionaries that can be eaten in a certain missionaries or cannibals problem?

• This question is very closely related to puzzling.stackexchange.com/questions/131/… -- though the accepted answer to that one doesn't so far as I can see prove that there's no solutions in the cases it implicitly says are insoluble. Sep 17, 2017 at 2:10
• Can you please state your problem in a more general notation (like a programming puzzle or something)? Also, can you also specify the boat capacity in your problem (I assume it's 2)? Sep 17, 2017 at 5:16
• Don't assume we know the missionaries and cannibals problem Sep 17, 2017 at 16:53

I think there is a solution to the Missionaries and Cannibals problem when there are five of each, illustrated below, where everyone starts on the left bank, and the center spaces represent the boat and the right represents the opposite bank.

MMMMMCCCCC __ __________
MMMMMCCC   CC __________
MMMMMCCC   C_ C
MMMMCCC    CM C
MMMMCCC    C_ MC
MMMCCC     CM MC
MMMCCC     C_ MMC
MMMCC      CC MMC
MMMCC      C_ MMCC
MMCC       CM MMCC
MMCC       C_ MMMCC
MMC        CC MMMCC
MMC        C_ MMMCCC
MC         CM MMMCCC
MC         C_ MMMMCCC
C          CM MMMMCCC
C          C_ MMMMMCCC
__________ CC MMMMMCCC
__________ __ MMMMMCCCCC

If you want to go through and check my logic, you can, but I think the trick is to always have a cannibal in the boat, that way, on both banks there is either an equal number of cannibals and missionaries, or there is one more missionary than cannibal. (Except in the first few steps to set this up, where there is one cannibal by themselves).

That's kind of the reason for the (outdated and kinda racist) choice of Missionaries and Cannibals as the things going back and forth. Both are capable of piloting the boat on their own.

Other versions of river crossing puzzles have different constraints on how the boat can be moved. For example, this one reminded me of a setup with a farmer trying to move sheep and wolves, where the wolves cannot outnumber the sheep. The difference there is that the farmer steers the boat, and this allows 'empty' crossings, where the boat is on the other side of the river despite not carrying a sheep or a wolf there. Similarly, you could do people and wolves, which is again slightly different from the Cannibal problem, because a wolf cannot cross the river on its own.

• On your third "trip" (sending CM to the right), doesn't that leave two cannibals and one missionary on the right bank (even though it's only until one rows back)? Isn't that a violation, or did I misinterpret the rules? Sep 18, 2017 at 21:57
• there is no solution for more than 3 Ms and Cs. dont even attempt
– Oray
Sep 19, 2017 at 5:19
• @MisterB Maybe I misinterpreted the rules? Does everyone get out of the boat when you row to the other side? If so, that probably needs to be clarified in the question. Sep 19, 2017 at 13:27

The real idea behind the missionaries (Ms) and cannibals (Cs) is actually taking all missionaries to the other side first then the cannibals. Here is a small diagram to show how more than 3 on both side makes the problem impossible:

To do that you first attempt taking two Cs to the other side (let's call it side B), and go back take another C as you see in the first two lines. after getting 2 Cs on side B, the only way taking any M to the side B taking two Ms. so lastly we do that. Actually there is also one more possibility which requires moving M and C at the beginning, but the actual idea (putting two Cs to the other side) does not change.

As a result there is a little equilibrium where you can only take M and C to the beginning side:

so After going back with M and C, the only possible way to move back to the side B is with two Ms. Any other combination will kill an M at least. And at the same time, you will have no Ms left on the side A and the rest is just taking all Cs one by one.

So adding even one M and C to the team will make the game impossible. Because in the second figure, you see the equilibrium and put one M and C to the first side. So you will never take the last M whatever you do actually. Let's see why with figure:

This is where you cannot do anything. You cannot move alone C, you cannot move alone M, the only possible movement becomes M and C to the sides.

As a result:

It is impossible to solve this problem with more than $3$ Ms and Cs and the maximum amount of M you can take to the side B is $3$ whatever setup you have where there are of course the same amount of Ms and Cs.

• What you've shown here is that one strategy for getting them all across doesn't work with more than 3 of each. That's not the same as saying that no strategy can do it. Sep 17, 2017 at 13:04
• @GarethMcCaughan there is no other strategy to solve this. This is the only way to solve this problem.
– Oray
Sep 17, 2017 at 13:12
• @Oray - I think the point of this question is how do we know that there is no other strategy. Sep 18, 2017 at 15:38
• @Oray In your assertion, it sounds as if there could be an uneven number of missionaries and cannibals. So, is it safe to say that we can have M > C and still have a solution, as long as C <= 3? Sep 3, 2021 at 19:31

A sufficient condition to have a solution is when

There are 2 more missionaries than cannibals.

This is how:

One missionary enters the boat, then he ferries one missionary, one cannibal, one missionary, one cannibal, etc, finishing with one missionary.

I believe with only one more missionary than cannibals you cannot have arbitrarily large groups.

But GoblinGuide did even better:

In fact with just one extra missionary there still is a solution.

The following diagram demonstrates his trick:

MCMCMCM
>CM>
MCMCM            CM
<C<
MCMCMC            M
>MC>
MCMC            MCM
<M<
MCMCM            CM
>CM>
MCM            CMCM
<C<
MCMC            MCM
>MC>
MC            MCMCM
<M<
MCM            CMCM
>CM>
M            CMCMCM
<C
MC            MCMCM
MC>
MCMCMCM

• You can do it with n cannibals and n+1 missionaries, you just have to alternate who brings the boat back each time. Feb 15 at 18:34