3
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Gareth McCaughan Sep 17 '17 at 2:10
  • $\begingroup$ 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)? $\endgroup$ – Laschet Jain Sep 17 '17 at 5:16
  • 3
    $\begingroup$ Don't assume we know the missionaries and cannibals problem $\endgroup$ – paparazzo Sep 17 '17 at 16:53
1
$\begingroup$

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:

enter image description here

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:

enter image description here

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:

enter image description here

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Gareth McCaughan Sep 17 '17 at 13:04
  • $\begingroup$ @GarethMcCaughan there is no other strategy to solve this. This is the only way to solve this problem. $\endgroup$ – Oray Sep 17 '17 at 13:12
  • 2
    $\begingroup$ @Oray - I think the point of this question is how do we know that there is no other strategy. $\endgroup$ – mbeckish Sep 18 '17 at 15:38
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Mister B Sep 18 '17 at 21:57
  • $\begingroup$ there is no solution for more than 3 Ms and Cs. dont even attempt $\endgroup$ – Oray Sep 19 '17 at 5:19
  • $\begingroup$ @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. $\endgroup$ – MMAdams Sep 19 '17 at 13:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.