Write a Java program to solve the Cannibals and Missionaries

Write a Java program to solve the Cannibals and Missionaries problem: Three missionaries and three cannibals are on one side of a river, along with a boat that can hold one or two people. Find a way to get everyone to the other side without ever leaving a group of missionaries in one place outnumbered by the cannibals in that place. Implement and solve this problem by generating a tree structure and then use iterative deepening search to search the tree. Once a solution is found, please output the order of the steps taken to reach the solution. For example, the output could look something like:

3M, 3C, 1 for 3 missionaries, 3 cannibals and the boat all on the 1 or starting side

3M, 2C, 0 for 3 missionaries, and 2 cannibals on the starting side and the boat is now on side 0 or the other side of the river

Continue pattern untill solution which will be 0M, 0C, 0 where everyone is on the other side including the boat

Solution

Solution for the Problem in (JAVA) :-

Program :-

import java.util.Scanner;
class FindPath
{
   public static void main(String args[])
   {
       int m,c,dif;
       System.out.println(\"Travelling starting from side 0\ \");
       System.out.println(\"Enter number of missionaries on side 0 : \");
       Scanner in =new Scanner(System.in);
       m=in.nextInt();
       System.out.println(\"Enter number of cannibals on side 1 : \");
       c=in.nextInt();
       dif=m-c;
       if(dif<=-2 || dif>=2)
       {
           System.out.println(\"Not possible\ \");
       }
       else if(dif==0)
       {
           dif=(m+c)/2;
           System.out.println(\"Possible by \"+(dif+dif)+\"moves with maximium people travel in the boat.\ \");
          
       }
       else
       {
           if(m>c)
           {
               dif=((m+c)/2)+1;
               System.out.println(\"Possible by \"+dif+\" rides only one person allowed to travel in first ride then\ maximium people can travel in the boat for all rides.\ \");
           }
           else
           {
               dif=((m+c)/2)+2;
               System.out.println(\"Possible by \"+dif+\" rides only one person allowed to travel in first ride then\ maximium people can travel in the boat for all rides.\ \");
           }

       }
   }
}

Output1 :-

D:\\java>javac FindPath.java

D:\\java>java FindPath
Travelling starting from side 0

Enter number of missionaries on side 0 :
2
Enter number of cannibals on side 1 :
3
Possible by 4 rides only one person allowed to travel in first ride then
maximium people can travel in the boat for all rides.

Output 2 :-

D:\\java>java FindPath
Travelling starting from side 0

Enter number of missionaries on side 0 :
2
Enter number of cannibals on side 1 :
3
Possible by 3 rides only one person allowed to travel in first ride then
maximium people can travel in the boat for all rides.

Output 3:-

D:\\java>java FindPath
Travelling starting from side 0

Enter number of missionaries on side 0 :
6
Enter number of cannibals on side 1 :
6
Possible by 12moves with maximium people travel in the boat.

_Output4:-

D:\\java>java FindPath
Travelling starting from side 0

Enter number of missionaries on side 0 :
6
Enter number of cannibals on side 1 :
4
Not possible

_{Note :- In above solution the program not only work for 3 and 2 people on two sides it will work for any number of people on both side if not possible to move it prints not possible if possible it prints possible along with number of moves and the number of people can travelling in every ride.}

_{Thank you!}