All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > General
Missionaries and Cannibals (Posted on 2005-05-29) Difficulty: 3 of 5
Three missionaries and three cannibals are on one side of the river, wanting to get across.

Unfortunately, the only boat available can hold a maximum of two people. The missionaries, wanting to stay safe, can never be on a side with more cannibals than missionaries (even for a moment!). The boat cannot travel under its own power, so there must be at least one person on board for it to cross.

How can the missionaries get safely across?

See The Solution Submitted by Damion warren    
Rating: 3.0000 (7 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution Spoiler (without handcuffs...) | Comment 2 of 11 |
This problem is actually pretty trivial, since almost every move is forced.

Obviously we have to start by bringing two people across. This can't be two M's, or the C's will eat the 3rd M. So we bring either MC or CC across to bank 2.

If the first, we obviously can't bring C back across, so we bring M. If the second, we have to bring C. Either way, there are now MMMCC on bank 1 and C on bank 2.

Now, bringing one M to bank 2 will lead to one of the possibilities of move one, and bringing one C will lead to the other; either way it's circular, so we can't do that. Bringing MM across to bank 2 will lead to the third being eaten, so we can't do that. Our only move is to bring CC to bank 2.

Bringing CC back to bank 1 will be circular, so our only move is to bring C to bank 1.

Bringing M or MC to bank 2 is death, so our only move is to bring MM to bank 2.

Bringing MM to bank 1 is circular, bringing CC to bank 1 is death, and bringing any single person to bank 1 is death. Our only move is to bring MC to bank 1.

Now we just bring MM to bank 2 and we're done. If the Missionaries need the cannibals to help lead them through the swamps of doom at a later point, the third cannibal can simply ferry the other two over to bank 2, or they can stay there and go hungry.

So, as I said, every move is forced. Actually, this was one of the first prolog codes I had to write way back when...

To picture each move, where the = represents the boat:

--------
M
M
M
C
C
C
=
--------
--------
M      M  
M      C
C      =
C
--------
--------
M      C
M
M
C
C
=
--------
--------
M      C
M      C
M      C
        =
--------
--------
M      C
M      C
M
C
=
--------
--------
M      M
C      M
        C
        C
        =
--------
--------
M      M
M      C
C
C
=
--------
--------
C      M
C      M
        M
        C
        =
--------

...and the other two cannibals can cross if necessary.

Edited on May 29, 2005, 12:58 pm
  Posted by Sam on 2005-05-29 12:05:58

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (4)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2020 by Animus Pactum Consulting. All rights reserved. Privacy Information