The Missionaries and Cannibals problem and AI July 27, 2008
Posted by razasayed in programming.Tags: Artificial Intelligence
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.
Raza's Weblog 
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.
난 한국사람입니다. 이 포스트가 제가 찾고 있는거였습니다. 감사합니다. 참고하겠습니다.
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
well.. just today I wrote a java code..
i want to know The Missionaries and Cannibals problem solving with A* search algorithm method
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..
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
Hi to all!!!!
I need the slide show in solving the problem o missionaries and cannibals!!!!!
Can u help me??????
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……….
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…
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
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 ^_^.
Hi Reza…
Thanks…this game is increasing my understanding about Artificial Intelligent
~ Idris
it can be solved in 9 moves
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
#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;
}
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
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.
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
solusi game missionaries and cannibals pake algoritma backtracking dalam bahasa pascal gimana ya???
anyone can solve it using CLIPS ? and not use OOP ! thanks…
hello guys can anyone mail me the source code of this game…please
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
how many solutions are possible for this problem?
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!!
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.
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
plz send me program of man cannibal in prolog
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
hey,
Can anyone send me d code of this using hill climb search………….
plz
Can anyone send me d code of this using iterative deepining search………….
plz
najeebullah2009@gmail.com
It can be solved in 9 steps for n=3
http://en.wikipedia.org/wiki/Missionaries_and_cannibals_problem
ilike it guys
sir ye problem kaisa solve karna hy?
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