Three cannibals and three missionaries must cross a river. Their boat can only hold two people. If the cannibals outnumber the missionaries, on either side of the river, the missionaries are in trouble (I won't describe the results). Each missionary and each cannibal can row the boat. How can all six get across the river?
I can't find an algorithm for solving this problem using IDDFS (Iterative deepening depth-first search) and GreedyBFS (greedy best-first search). An idea on how to solve this would make me happy as well.
Edited:
I found an algorithm for IDDFS on wiki:
IDDFS(root, goal)
{
depth = 0
repeat
{
result = DLS(root, goal, depth)
if (result is a solution)
return result
depth = depth + 1
}
}
DLS(node, goal, depth)
{
if (depth == 0 and node == goal)
return node
else if (depth > 0)
for each child in expand(node)
DLS(child, goal, depth-1)
else
return no-solution
}
But I can't figure out what expand(node) in DLS() is supposed to accomplish in my problem. This is my Node class:
public class Node{
//x-no of missionaries
//y-no of cannibals
//z-position of boat
int x,y;
boolean z;
Node(int x,int y,boolean z){
this.x=x;
this.y=y;
this.z=z;
}
public int getM(){
return this.x;
}
public int getC(){
return this.y;
}
public boolean getB(){
return this.z;
}
public void setM(int x){
this.x=x;
}
public void setC(int y){
this.y=y;
}
public void setB(boolean z){
this.z=z;
}
}
I would appreciate any help.
How to solve it without algorithm? your model is small and it can be solve without any programming, first two cannibals going to the other side, then one of them backs with boat and takes another cannibal to other side, now there are 3 cannibals on the other side one of them backs and two missionary going to the other side (now 2 c and two m are in other side). in this time one c
with one m
comes back (2 c and 2 m in first place), and again 2 m going to the other side (3m in other side with one c), again the only c in the other side comes back and carries two c on the other side (2 c and 3 m in the other side), again one c comes back and moves latest c to the other side.
How to simulate it with algorithms like DFS? Create a digraph, there are 2^6 positions (all possible subsets of {1,2,3,4,5,6}), they are related to each other if you can go from one position to another by using available moves. some nodes are dead nodes (nodes which causes more cannibal in one side), you will remove this nodes from your graph, then your task is to check is there a way to go from node 0 {}, to node 63 {1,2,3,4,5,6}, which can be solve in too many ways like BFS, DFS.