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 an appropriate 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

SolutionProvider S = new SolutionProvider();
ArrayList Solution = S.getSolutionStates(new State(\"Root\", 3, 3, false,1),
new State(\"Goal\", 0, 0, true,999999));
printSolutions(Solution);
private static void printSolutions(ArrayList Solution)
{
if (Solution.Count == 0)
{
Console.WriteLine(\"\ \ NO SOLUTIONS HAVE BEEN FOUND\ \ \");
}
else
{
int Solfound = 1;
for (int i = 0; i < Solution.Count; i++)
{
State s = (State)Solution[i];
Console.WriteLine(\"=====FOUND SOLUTION [\" +
Solfound++ + \"]=====\ \ \");
Console.WriteLine(\"This solution was found at level [\" +
s.getStateLevel() + \"]\ \ \");
s.Print();
Console.WriteLine(\"\ \ \");
}
}
}
using System;
using System.Collections.Generic;
using System.Collections;
using System.Text;

namespace MissCanApp
{
#region SolutionProvider CLASS
class SolutionProvider
{
private int CURRENT_ROOT_STATE = 0;
private ArrayList searchAgenda = new ArrayList();
public SolutionProvider()
private void addStateToAgenda(String StateName,State parent,
int nMiss, int nCan)
{

// BoatDirection holds either 1 or -1, depending on the side.
int BoatDirection = parent.Side ? 1 : -1;

String newStateName = parent.getStateName() + StateName;
State newState = new State(newStateName,
parent.nMiss + nMiss * BoatDirection,
parent.nCan + nCan * BoatDirection,
!parent.Side,
parent, parent.getStateLevel() + 1);
}
private void addStateToAgenda(State newState)
{
if (newState.InvalidState())
return;
searchAgenda.Add(newState);
}
public ArrayList getSolutionStates(State StartState, State EndState)
{
int optimalSolfoundAtLevel = 0;
bool allOptimalSolutionsFound = false;
bool foundFirstSolution = false;
ArrayList Solutions = new ArrayList();
addStateToAgenda(StartState);
while (searchAgenda.Count > 0 && !allOptimalSolutionsFound)
{
State CurState = (State)searchAgenda[CURRENT_ROOT_STATE];
searchAgenda.RemoveAt(CURRENT_ROOT_STATE);
if (CurState.Equals(EndState))
if (foundFirstSolution) {
if (CurState.getStateLevel() <= optimalSolfoundAtLevel) {
Solutions.Add(CurState);
}
else {
allOptimalSolutionsFound =true;
}
}
else {
foundFirstSolution=true;
optimalSolfoundAtLevel = CurState.getStateLevel();
Solutions.Add(CurState);
}
}
else {
generateSucessors(CurState);
}

}
  
private void generateSucessors(State CurState) {
int nCan, nMiss =0;
int stateName =1;
for (int i = 0; i <= Program.boatsize; i++)
{
for (int j = 0; j <= Program.boatsize; j++)
{
if (i==0 && j ==0)
continue;
if (i + j > Program.boatsize)
break;
nMiss = i;
nCan = j;
addStateToAgenda(\"_\" + stateName++, CurState, nMiss, nCan);
}
}
}

}
#endregion
}

using System;
using System.Collections.Generic;
using System.Text;

namespace MissCanApp
{
#region State CLASS
class State
{
public int nMiss, nCan;
public bool Side;
private int NumOfEachAtStart = 3;
private String Name;
private State PrevState;
private int StateLevel=0;
public State(String Name, int nMiss, int nCan, bool Side,
int stateLevel) : this(Name, nMiss, nCan,
Side, null, )
public State(String Name, int nMiss, int nCan, bool Side,
State PrevState, int StateLevel)
this.Name = Name;
this.nMiss = nMiss;
this.nCan = nCan;
this.Side = Side;
this.PrevState = PrevState;
this.stateLevel = stateLevel;
}
public int getStateLevel()
{
return this.stateLevel;
}
public String getStateName()
{
return this.Name;
}
public void Print()
{
if (PrevState != null) {
PrevState.Print();
}
String WhatSide = Side ? \" BOAT RIGHT->\" : \"<-BOAT LEFT \";
Console.WriteLine(nMiss + \"M/\" + nCan + \"C \" + WhatSide + \" \" +
(NumOfEachAtStart - nMiss) + \"M/\" +
(NumOfEachAtStart - nCan) + \"C\");

}
public bool Equals(State StateToCheck)
{
return (nMiss == StateToCheck.nMiss &&
nCan == StateToCheck.nCan &&
Side == StateToCheck.Side);
}
public bool InvalidState()
{
int PersonType1 = 0;
int PersonType2 = 0;
if (Program.CanOutnumberMiss)
{
PersonType1 = nCan;
PersonType2 = nMiss;
}

else
{
PersonType1 = nMiss;
PersonType2 = nCan;
}
  
if (nMiss < 0 || nCan < 0 ||
nMiss > NumOfEachAtStart ||
nCan > NumOfEachAtStart)
return true;
  
if (PersonType1 < PersonType2 && PersonType1 > 0)
return
if ( (NumOfEachAtStart - PersonType1 <
NumOfEachAtStart - PersonType2) &&
(NumOfEachAtStart - PersonType1 > 0))
return true;
  
return false;
}

}
#endregion
}