Cross the River: Cannibals and Missionaries

This question is easy to moderate. I somtimes ask it as an interview question.
3 missionaries and 3 cannibals are are one bank of a river and all need to cross it. There is a single boat which can old two people. The piranhas in the river have ruled out swimming for these wandering souls.
The catch (there's always a catch), is that if the cannibals ever outnumber the rather tasty missionaries on a particular bank, the outnumbered missionary(ies) will find themselves transfered up to the celestial branch office. How do you get all of them across (intact)?
--Mark

there is a game website with this particular problem in flash... i cannot remember the name, though. it also has the knight's tour and a couple other cool thought provoking games (one with elevators). i would love to see that site again if anyone knows what i am talking about.
the way their game works is that someone has to drive the boat, so there always has to be at least 1 cannibal or 1 missionary in the boat. as an added bonus, if you get to shore and the total number of cannibals (on shore and in boat) out-number the missionaries, then you lose.
i will give someone else a try since i have seen this before.

1 cannibal, 1 missionary cross
missionary returns
1 cannibal 1 missionary cross
cannibal returns
2 missionaries cross
cannibal returns
2 cannibals cross
1 cannibal returns
2 cannibal cross

Lets see if this adds up : x=cannibal; 0=missionary

Oh no , loose on the second crossing. Don't cannibals have a code of honor to maintain.Add an extra clause that that it is a race with a bonus at the end of it , so there's no time to be wasted eating fat missionary.
regards
[ August 17, 2003: Message edited by: HS Thomas ]

1 cannibal, 1 missionary cross
missionary returns
2 cannibals cross
cannibal returns
2 missionaries cross
cannibal returns
2 missionaries cross
1 cannibal returns
2 cannibal cross
This might work !
No it doesn't. This is hard.
[ August 17, 2003: Message edited by: HS Thomas ]

xx00       |     <-0     |x     
             |             |      
             |             |      
  000        |     <-x     |xx    
             |             |      
  0x         |     <-x0    |0x    
             |             |      
             |             |      
  xx         |     <-x     |000   
             |             |      
             |             |      
  x          |     <-x     |000x  
             |             |      
             |             |      
             |             |000xxx
             |             |      
1 cannibal, 1 missionary cross
missionary returns
-------------------------------------------
2 cannibals cross
cannibal returns
-------------------------------------------
2 missionaries cross
1 cannibal  1 missionary returns
-------------------------------------------
2 missionaries cross
1 cannibal returns
---------------------------------------------
2 cannibal cross
1 cannibal returns
---------------------------------------------
2 cannibals cross

x
U
[ August 17, 2003: Message edited by: HS Thomas ]

That is correct. Now some of the top candidates will note the following:

Originally posted by HS Thomas:
3C3M b 2C2M b 1C1M 2C3M b 1C 3M b 3C 1C3M b 2C 1C1M b 2C2M 2C2M b 1C1M 2C b 1C3M 3C b 3M 1C b 2C3M 2C b 1C3M b 3C3M

Now in this case, you made use of the asymmetry in the problem. But what can you can do is solve just have the problem (up to where I put the break). Then you note that the next step flips the state and you can simply reverse/reflect the steps to solve the second half.

--Mark

Bravo!
Note the attempt to furtively cook a cannibal should the mission to keep cannibal numbers less than missionary numbers fail ?
x <------------- cannibal
U <------------- blackened pot
^v^ <------------- fire
That's clever , Mark. I didn't realise that flipping the numbers would get there faster.
Now I can see the skewed mirror image in my example.

Is there a theory to explain that problem solving strategy ?
regards
[ August 17, 2003: Message edited by: HS Thomas ]

Originally posted by Greg Harris:
there is a game website with this particular problem in flash... i cannot remember the name, though. it also has the knight's tour and a couple other cool thought provoking games (one with elevators). i would love to see that site again if anyone knows what i am talking about.

It's Plastelina Games.
That elevator puzzle is really cool.

thanks, rafael! i have missed those games.
WOW... they have added a lot since i was there last.
[ August 18, 2003: Message edited by: Greg Harris ]