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?

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