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

*Posted by razasayed in programming.*

Tags: Artificial Intelligence

trackback

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 = 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.

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