##
The Missionaries and Cannibals problem and AI
*July 27, 2008*

*Posted by razasayed in programming.*

Tags: Artificial Intelligence

35 comments

Tags: Artificial Intelligence

35 comments

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^{2}+0, 5 = 2^{2}+1 , 11=3^{2}+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^{2}+(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 😉

Vodpod videos no longer available.