jump to navigation

The Missionaries and Cannibals problem and AI July 27, 2008

Posted by razasayed in programming.
Tags:
trackback

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 = 12+0, 5 = 22+1 , 11=32+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 n2+(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.

Advertisements

Comments»

1. sindhu - August 1, 2008

hey! this a great post! this is just what i was looking for, thank you 🙂 am studying AI at college, so this has been very helpful.

2. 한국의대학생 - November 24, 2008

난 한국사람입니다. 이 포스트가 제가 찾고 있는거였습니다. 감사합니다. 참고하겠습니다.

3. bahman - January 16, 2009

hi! thank u reza!
kindly i need this puzzel’s source code in c or C++
can u help me about it plaese?
my email is b.kaardaan@gmail.com

sk - October 9, 2009

well.. just today I wrote a java code..

4. Tariku Birhanu - January 16, 2009

i want to know The Missionaries and Cannibals problem solving with A* search algorithm method

cr - March 8, 2012

Why would you want something as fancy as A*? As the river bank state set represent an undirected, unweighted graph, breadth-first-search would do nicely..

5. Tariku Birhanu - January 16, 2009

hi reza!
kindly i need this puzzel’s algorithm in A* searching algorithm.
can u help me about it plaese?My email is tarikubirhanu@yahoo.com

6. Roldan Leparto - February 5, 2009

Hi to all!!!!

I need the slide show in solving the problem o missionaries and cannibals!!!!!

Can u help me??????

7. JOJIT SORIA - February 10, 2009

hey man wazz up can u help me bout the cannibal and missionaries source code pls help me coz that is my final requirement in my course with out this source code i cant graduate this year… hope you will granted my request pls……….

8. Zainab Aafia - March 1, 2009

Hello…even am studying AI at college and i need d source code for this..can u help me plzzzz…my email id is zainab_a30@yahoo.com

9. jasirica - March 4, 2009

hello raza!
missionaries-cannibals problem is a fun game.
would you mind if i ask you the code of it in Amzi! Prolog…?
i’m just interested to run it using prolog,.
as of now, i got poor knowledge of prolog so i need viable code from
you to help me practice….
so,,ppllzzz…. i really hope i can have it…i would be very thankful.
thanks.
good day.
jasiricasilvano@yahoo.com

10. Nidhi - May 3, 2009

SO, Alright, imma ask you a question. I wrote the same code in prolog for 3 hens and 3 foxes. I’m only getting 2 solutions.

P = [[3,3,1],[2,2,0],[2,3,1],[0,3,0],[1,3,1],[1,1,0],[2,2,1],[2,0,0],[3,0,1],[1,0,0],[2,0,1],[0,0,0]|_] ? ;

P = [[3,3,1],[2,2,0],[2,3,1],[0,3,0],[1,3,1],[1,1,0],[2,2,1],[2,0,0],[3,0,1],[1,0,0],[1,1,1],[0,0,0]|_] ?

so I get 11 configurations. Each list is [F , H ,B] that is # of foxes and # hens and the state of the boat. This is only the left hand side of the configuration. I just wanted to know how many solutions are there in total. ^_^ that’s not like asking for help, just curious. I even tried working it on paper but idk what other way I can do it. That;s my blogspot right there. I dont write abt code on my blogs that’s geekish ^_^.

11. Idris - May 13, 2009

Hi Reza…

Thanks…this game is increasing my understanding about Artificial Intelligent

~ Idris

12. ananya - August 10, 2009

it can be solved in 9 moves

13. james - August 31, 2009

hi…
i have to this project in turbo prolog so if u have code for this project in prolog then please send me…
my email id is

jhere4u2009@yahoo.co.in

14. shashi kant - September 8, 2009

#include
#include
#include

using namespace std;

struct StateSTR
{
int Mlhs; //nr missionaries on LHS of river
int Clhs; //nr cannibals on LHS of river
int pos; //boat on LHS (0) or RHS(1) of river
int Mrhs; //nr missionaries on RHS of river
int Crhs; //nr cannibals on RHS of river
StateSTR *parent;//pointer to parent state
int opUsed;
bool operator==(const StateSTR & rhs) const
{
return ((Mlhs == rhs.Mlhs) && (Clhs == rhs.Clhs) &&
(Mrhs == rhs.Mrhs) && (Crhs == rhs.Crhs) &&
(pos == rhs.pos));
}
};

ostream & operator<< (ostream & out, const StateSTR & s)
{
out << "Mlhs:" << s.Mlhs << endl;
out << "Clhs:" << s.Clhs << endl;
out << "Boat:" << s.pos << endl;
out << "Mrhs:" << s.Mrhs << endl;
out << "Crhs:" << s.Crhs << endl << endl;
return out;
}

bool validState(StateSTR *S)
{
if(( (*S).Clhs 3)) return false;
if(( (*S).Crhs 3)) return false;
if(( (*S).Mlhs 3)) return false;
if(( (*S).Mrhs 3)) return false;
if(( (*S).pos != 0) && ( (*S).pos!= 1)) return false;
if( (( (*S).Clhs > (*S).Mlhs) && ( (*S).Mlhs > 0)) ||
(( (*S).Crhs > (*S).Mrhs) && ( (*S).Mrhs > 0)) )
return false;
return true;
}

//Apply each of ten possible operations to state.
// m c side(0=left,1=right)
//case 0: C(0,1,0) –> carry one cannibal to LHS
//case 1: C(0,2,0) –> carry two cannibals to LHS
//case 2: C(1,0,0)
//case 3: C(2,0,0)
//case 4: C(1,1,0)
//case 5: C(0,1,1)
//case 6: C(0,2,1)
//case 7: C(1,0,1) –> carry one missionary to RHS
//case 8: C(2,0,1)
//case 9: C(1,1,1)
StateSTR * nextState(StateSTR *Z, const int j)
{
StateSTR * S = new StateSTR();
(*S) = (*Z);
(*S).opUsed = j;
switch (j)
{
case 0: { (*S).pos -= 1;
(*S).Mlhs += 0;
(*S).Clhs += 1;
(*S).Mrhs -= 0;
(*S).Crhs -= 1;}
break;
case 1: { (*S).pos -= 1;
(*S).Mlhs += 0;
(*S).Clhs += 2;
(*S).Mrhs -= 0;
(*S).Crhs -= 2;}
break;
case 2: { (*S).pos -= 1;
(*S).Mlhs += 1;
(*S).Clhs += 0;
(*S).Mrhs -= 1;
(*S).Crhs -= 0;}
break;
case 3: { (*S).pos -= 1;
(*S).Mlhs += 2;
(*S).Clhs += 0;
(*S).Mrhs -= 2;
(*S).Crhs -= 0;}
break;
case 4: { (*S).pos -= 1;
(*S).Mlhs += 1;
(*S).Clhs += 1;
(*S).Mrhs -= 1;
(*S).Crhs -= 1;}
break;
case 5: { (*S).pos += 1;
(*S).Mrhs += 0;
(*S).Crhs += 1;
(*S).Mlhs -= 0;
(*S).Clhs -= 1;}
break;
case 6: { (*S).pos += 1;
(*S).Mrhs += 0;
(*S).Crhs += 2;
(*S).Mlhs -= 0;
(*S).Clhs -= 2;}
break;
case 7: { (*S).pos += 1;
(*S).Mrhs += 1;
(*S).Crhs += 0;
(*S).Mlhs -= 1;
(*S).Clhs -= 0;}
break;
case 8: { (*S).pos += 1;
(*S).Mrhs += 2;
(*S).Crhs += 0;
(*S).Mlhs -= 2;
(*S).Clhs -= 0;}
break;
case 9: { (*S).pos += 1;
(*S).Mrhs += 1;
(*S).Crhs += 1;
(*S).Mlhs -= 1;
(*S).Clhs -= 1;}
break;
}
return S;
}

bool notFound(StateSTR *Y, list OPEN,
list CLOSED)
{
list::iterator itr1 = OPEN.begin();
list::iterator itr2 = CLOSED.begin();
for(; itr1 != OPEN.end() ; itr1++)
if( (*(*itr1)) == (*Y) ) break;
for(; itr2 != CLOSED.end(); itr2++)
if( (*(*itr2)) == (*Y) ) break;

if( (itr1 == OPEN.end()) && (itr2 == CLOSED.end()) )
return true;
return false;
}

void addChildren(list & OPEN,
list & CLOSED,
StateSTR * Y )
{
StateSTR *tState;
for(int i = 0; i < 10; i++)
{
tState = nextState(Y, i);
if( (validState(tState)) &&
(notFound(tState, OPEN, CLOSED)) )
{
(*tState).parent = Y;
OPEN.push_front(tState);
}
else
delete tState;
}
return;
}

void printOP(int n)
{
switch (n)
{
case 0: cout << "C(0,1,0)" << endl; break;
case 1: cout << "C(0,2,0)" << endl; break;
case 2: cout << "C(1,0,0)" << endl; break;
case 3: cout << "C(2,0,0)" << endl; break;
case 4: cout << "C(1,1,0)" << endl; break;
case 5: cout << "C(0,1,1)" << endl; break;
case 6: cout << "C(0,2,1)" << endl; break;
case 7: cout << "C(1,0,1)" << endl; break;
case 8: cout << "C(2,0,1)" << endl; break;
case 9: cout << "C(1,1,1)" << endl; break;
}
}

//MAIN section
int main() {
bool searchResult = false;
stack opsUsed;
StateSTR START = {3,3,0,0,0,NULL,-1};
StateSTR GOAL = {0,0,1,3,3,NULL};
StateSTR *X;
StateSTR *tempState;
list OPEN;
list CLOSED;
OPEN.push_front(&START);

while(!OPEN.empty())
{
X = OPEN.front(); //stack-like operation
OPEN.pop_front(); //
if ((*X) == GOAL)
{
searchResult = true;
break;
}
else
{
addChildren(OPEN, CLOSED, X);
CLOSED.push_back(X);
}
}
//Display results
if(searchResult == true)
{
cout << endl << "PATH" << endl;
for(StateSTR * p = X; p!= NULL; p = (*p).parent)
opsUsed.push((*p).opUsed);
}
while(!opsUsed.empty())
{
printOP(opsUsed.top());
opsUsed.pop();
}
cout << endl;
return 0;
}

15. Anonymous - September 13, 2009

It can be solved if you allow more than 2 to cross on the boat for 4 cannibals and 4 missionaries, as you increase the number of missionaries and cannibals you get solutions if you increase the amount of people allowed on the boat

16. Chris - November 15, 2009

Haha Im glad I came across this as well. I kept running my program for 4 or more Cannibals and Missionaries and kept getting know solution. Needless to say I was getting really angry. Time to go prove facts about this problem under different situations for myself.

17. Anonymous - December 21, 2009

hello guys… i wan to know the solution to this problem in best first algorithm…. is there any code? please send me…
e-mail. t_theodoros@hotmail.com

18. ririn - March 27, 2010

solusi game missionaries and cannibals pake algoritma backtracking dalam bahasa pascal gimana ya???

19. suwandi - May 29, 2010

anyone can solve it using CLIPS ? and not use OOP ! thanks…

20. asha - August 28, 2010

hello guys can anyone mail me the source code of this game…please

21. ASHA - August 29, 2010

hi Reza!
kindly i need this puzzle’s source code in c or C++
can u help me about it please?
my email is asharam87@gmail.com

22. dpk - September 23, 2010

how many solutions are possible for this problem?

23. joerhen garrido - January 20, 2011

Hi! i`m a computer science student,here at the philippines…ahm. . .just want to know if you can help me do some case studies. . .i`ll send you the problem. . .after your reply. . .tnx!!

24. Gintarė - February 20, 2011

Hello,
Can you help me to make “missionaries and cannibals with bi-directional search method” algorithm in C or C++. Please, write to me: damidaviciuke@gmail.com
Thank you.

25. apit - March 13, 2011

hi Reza!
kindly i need this puzzle’s source code in java
can u help me about it please?
my email is apitmanu@gmail.com

26. nisha - April 21, 2011

plz send me program of man cannibal in prolog

27. nisha - April 21, 2011

plz send me progams of tower of hanoi, tic-tac-toe using min max, implement family trip, implement road connectivity of different cities, 8 queen problem, 8 puzzle using a* algo

28. dk - April 29, 2011

hey,
Can anyone send me d code of this using hill climb search………….
plz

29. Najeeb - May 4, 2011

Can anyone send me d code of this using iterative deepining search………….
plz

najeebullah2009@gmail.com

30. andy - October 30, 2011
31. Anonymous - November 18, 2011

ilike it guys

32. muhammad tahir - March 27, 2013

sir ye problem kaisa solve karna hy?

33. Andres Rivera - September 19, 2015

please someone help me with the source code for this problem by iterative search profused my email is anferiga23@gmail.com ….. thank you very much and I am from Colombia is not English speak please help


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: