# Iterative deepening depth-first search heuristics to solve "3 Missionary And Cannibal" challenge

Missionaries and cannibals problem is a well known Toy Problem to learn basic AI techniques.

I implemented it using iterative deepening depth-first search algorithm. My state is represented by a 3-element vector <A,B,C> where A represents the side of the boat (0/1), B and C represents the number of cannibals and missionary on the left hand side of the bank.

#include <bits/stdc++.h>

using namespace std;
/*
SOLUTION TO 3 CANNIBAL and 3 MISSIONARIES PROBLEM
USING ITERATIVE DEEPENING DEPTH FIRST SEARCH
https://en.wikipedia.org/wiki/Missionaries_and_cannibals_problem
*/

//state initial state (0,3,3) Side Of the Boat 0->Right/1 /Cannibal/Missionary on right hand side
vector < pair < int, pair<int,int> > > newStatesSet(pair< int, pair < int, int > > state){
//generating all possible states from a given initial state
vector < pair< int, pair< int, int> > > newStatesSet;
int C = state.second.first, M = state.second.second;

if(state.first==0){
if(C>=1)
newStatesSet.push_back(make_pair(1, make_pair( C-1 ,M  )));
if(M>=1)
newStatesSet.push_back(make_pair(1, make_pair( C   ,M-1)));
if(C >= 2)
newStatesSet.push_back(make_pair(1, make_pair( C-2, M   )));
if(C >= 1 && M >=1 )
newStatesSet.push_back(make_pair(1, make_pair( C-1, M-1 )));
if(M >= 2)
newStatesSet.push_back(make_pair(1, make_pair( C  , M-2 )));
}
else{
C = 3- C;
M = 3- M;

if(C >= 1)
newStatesSet.push_back(make_pair(0, make_pair(3- C+ 1 ,3- M  )));
if(M >= 1)
newStatesSet.push_back(make_pair(0, make_pair(3- C   ,3- M+ 1)));
if(C >= 2)
newStatesSet.push_back(make_pair(0, make_pair(3- C+ 2, 3- M   )));
if(C >= 1 && M >=1 )
newStatesSet.push_back(make_pair(0, make_pair(3- C+ 1, 3- M+ 1 )));
if(M >= 2)
newStatesSet.push_back(make_pair(0, make_pair(3- C  , 3- M+ 2)));
}
return newStatesSet;
}

bool validState(pair<int, pair<int, int> > state){
int C = state.second.first, M = state.second.second;
if(C > M && M!=0)
return false;
C = 3- C, M = 3- M;
if(C > M && M!=0)
return false;
return true;
}

//source node , goal node , depth , answer if found is stored here
bool  depthLimitedSearch(pair<int, pair<int, int> > source, pair<int, pair<int, int> > goal, int depth, vector<pair<int, pair<int,int> > > &ans){

if(source==goal)
return true;

if(depth<=0)
return false;

vector <pair<int, pair<int,int> > > leafs = newStatesSet(source);
for(int i=0; i<leafs.size(); i++)
if(validState(leafs[i])){
if(depthLimitedSearch(leafs[i], goal, depth-1, ans)){
ans.push_back(leafs[i]);
return true;
}
}
}

string form(int stateNos,string character){
string rep="";
for(int i=1; i<=3; i++)
if(stateNos>=i)
rep.append(character);
else
rep.append(" ");
return rep;
}

void displayState(pair<int, pair<int, int> > state){
string rep = "";
rep.append(form(state.second.first,"C"));
rep.append(form(state.second.second,"M"));
for(int i=1; i<=6; i++){
if(state.first==0 && i==2)
rep.append("B");
else
if(state.first==1 && i==5)
rep.append("B");
else
rep.append(" ");
}
rep.append(form(3-state.second.first,"C"));
rep.append(form(3-state.second.second,"M"));
cout<<rep<<endl;
}

void iterativeDeepeningSearch(pair<int, pair<int, int> > source, pair<int, pair<int, int> > goal){

vector< pair<int , pair<int, int> > > ans;
for(int i=1 ; i <= 25 ;i++){
vector<pair<int, pair<int, int> > >vec;
depthLimitedSearch(source,goal,i,vec);
if(vec.size()>0){
ans=vec;
break;
}
}
cout<<"C and M represents cannibals and Missionaries \n respectively and B represents the location of boat\n";
displayState(source);
for(int i=ans.size()-1; i>=0; i--)
displayState(ans[i]);
}

int main()
{
pair<int, pair<int, int> > source = make_pair(0,make_pair(3, 3 ));
pair<int, pair<int, int> > goal   = make_pair(1,make_pair(0, 0 ));
iterativeDeepeningSearch(source,goal);
}


It produces the following output:

CCCMMM B
C  MMM    B CC
CC MMM B    C
MMM    B CCC
C  MMM B    CC
C  M      B CC MM
CC MM  B    C  M
CC        B C  MMM
CCC    B       MMM
C         B CC MMM
CC     B    C  MMM
B CCCMMM


What do you think is wrong with this code, and how can it be improved? What edge cases have I overlooked, if any? How can I make it less complicated?

• Is this not a bad state? C M B CC MM  Seems lime the M on the left back is being eaten. Sep 16, 2015 at 14:05
• No, If the number of C's and M's are equal on any side then it is considered a good state. Ie Nos(C)== Nos(M) is a good state. Sep 16, 2015 at 14:24

First and foremost, do not use namespace::std. Please google for it, you will find a lot of answers.

Please include all the necessary headers. A first glance tells me that the following is missing:

#include <string> // std::string
#include <utility> // std::pair
#include <vector> // std::vector


Why are you using pair>? Have a look at tuples: http://www.cplusplus.com/reference/tuple/tuple/

std::tuple<bool, size_t, size_t>


Have a look at your function arguments and declare those const who are not modified. Also you are always passing a copy rather a reference so you should either be dooing one of the following.

foo(const type &bar)
foo(type &bar)


Try to add a space between control flow instructions like for, while and friends. Therewith you can readily differentiate them from functions.

Depending on the C++ version you are using you want to consider using range based loops for C++11 and higher. Then a loop like this one:

vector <pair<int, pair<int,int> > > leafs = newStatesSet(source);
for(int i=0; i<leafs.size(); i++)
if(validState(leafs[i])) {
if(depthLimitedSearch(leafs[i], goal, depth-1, ans)){
ans.push_back(leafs[i]);
return true;
}
}
}


becomes this

std::vector<std::tuple<bool, size_t, size_t> > leafs = newStatesSet(source);
for (auto &leaf : leafs)
if (validState(leaf)) {
if (depthLimitedSearch(leaf, goal, depth-1, ans)){
ans.push_back(leaf);
return true;
}
}
}


If you need the index often or reverse loops, then use iterators

for (int i=ans.size()-1; i>=0; i--)
displayState(ans[i]);


then becomes

for (auto it=ans.rbegin(); it != ans.rend(); ++it)
displayState(*it);


More a personal thing than anything else but still. Your if ladders are really confusing. Whenever i see stuff like

if (C >= 1)
// Stuff C==1
if (C >= 2)
// Stuff C>=1


I cringe inwardly. In that setting it is really easy to miss the first clause for C >= 2. So why not do

if (C == 1)
// Stuff C==1
else if (C >= 2)
// Stuff C==1
// Stuff C>=1


I know it is repetitive, but at least the control flow is really clear.