Raza’s Weblog

The Missionaries and Cannibals problem is a cute little puzzle, which involves moving 3 missionaries and 3 cannibals from one end of the shore to another  in a boat which can accomodate at most two people at a time . Also, if the cannibals outnumber the missionaries on one side then the missionaries get eaten up by the cannibals.

Well, this sounds like just another one of those river-crossing problems which most people are familiar with since childhood ,  so whats so special about this one ?. Actually, the missionaries and cannibals problem is a famous toy problem in AI (Artificial Intelligence), because it was the first paper that approached problem formulation from an analytical standpoint . Many computer science students might already be familiar with this problem, and also others like the Towers of Hanoi, n-queens problem, the knights tour etc…

I have posted the puzzle below , so that you can have some fun with it  . Its actually a simple problem and i managed to solve it in 11 moves, see if you can do it in less than that  .  If you do, then hats off to you , because i dont think it can be done in less than 11 moves . Because,with 1 missionary and 1 cannibal 1 move is required,with a pair of each 5 moves, and here in a case of 3 each, i required 11 moves.So it seems that there is a pattern in the minimum number of moves required. 1 = 1²+0, 5 = 2²+1 , 11=3²+2 .

I thought it would be fun trying to develop an algorithm to solve the problem for the general case of n missionaries and n cannibals  , for which i thought the minimum number of moves required would be n²+(n-1). But luckily for me, before i embarked on my search for the solution , i came across some information related to the problem (thanks google ! ), which pointed to the fact that my search would never end ! . The special thing about this problem is that it does not scale up ! . For 4 or more missionaries and cannibals, the problem has no solution ! .

Alright, enough of math !!…let the game begin