Population

Missionary

A.First Edition

This is my first edition of my Missionary class inherited from DFSArray class, so you can also regard it as

an application of DFS class.

B.The problem

This is a rather classic problem which we all solved during our primary school or middle school and quite

frequently it is given as an example in many AI course.

There are 3 missionaries and 3 barbarians in one side of river, there is only one boat which can hold maximum

two persons. That is either MM, BB, MB, M, B. (If you regard barbarian also as a person...) There is one rule

that whenever barbarians are over-numbered with missionaries then missionaries will be eaten by barbarians. So,

try to arrange a way to let 3 missionaries to cross river with that boat.

C.The idea of program

Basically you should realize that there are actually 10 possible choices for shipping at every occation.

MM_LR, BB_LR, MB_LR, M_LR, B_LR, MM_RL, BB_RL, MB_RL, M_RL, B_RL: LR stands for from LEFT TO RIGHT, RL is opposite.

And MM stands for two missionaries, BB for two barbarians, M of course stands for one missionary, B stands for

one barbarian, MB stands for one missionary and one barbarian.

So, we actually figure out all possible choices. Then the job is only how to verify the options which is quite

a bit complicated. I designed a structure to hold the info for the ten choices. And in the class Missionary, there

is a private member Position which records the state of game. It is the problem that when and how should we update

this state!

As you know, I already compile the DFS class into object file (.obj file) and from that I use the "lib" command to

make it a .lib file and put it into the "lib" directory under "vc98". And the "DFSArray.h" file was placed in

directory "include". On the project setting menu, I insert the name of "DFSArray.lib". So, this implies that my

DFSArray class is actually not reachable for source code! I cannot change anything from the base class!

This really creates some trouble if your base class is not designed properly. For example, the Position array

cannot be updated when verifying data as in function "validateOption(int sonData)", you have no access to your

son node. Then you can only do the synchronization action when you add son nodes. This is rather complicated!

D.The major functions

1. bool Missionary::evaluate()

This function tests the son node, but you need to synchronize Position with "data", otherwise, you will only check

the parent Position as when new node is created, Position are copied from parent.

2. bool Missionary::validateOption(int sonData)

There is a lot of issues needed to be taken care with! First, check if boat is available for the option which is

simple. Second, there should be enough person to be shipped to other side and barbarians can never outnumber

missionaries at either sides of river. Third, check if direct repetition or indirect repetition is made. Direct

means you ship something back immediately after you ship it here. But indirect is a little tricky! At beginning

my program is cunning enough to produce a lot of indirect repetition---after several rounds, it become the original

starting state. So, I add an extra condition-checking function to see if original starting state is reached.

E.Further improvement

1. You tell me!

DFSArray.h  (placed in "include" directory under vc98)

#ifndef DFSARRAY_H
#define DFSARRAY_H
#include <iostream>

using namespace std;

const int MaxSonCount=8;

const int MaxLevel =20;

const int MaxOptions = 10;

const int MaxNodeCount = 1000;

class DFS
{
private:
	void initialize(DFS* now);
	static DFS* nodeList[MaxNodeCount];
	static bool findAll;
	static int optionArray[MaxOptions];
	static int optionCount;
	static char** nameString;
	static int solutionCount;
	static int maxLevel;
	static int domino;
	void addSon(int sonData);
	bool touchDown();
	void setMaxLevel(int max) { maxLevel = max;}
	DFS* upDate();
	bool hasBrother();
	DFS* nextBrother();
	bool generate();
	DFS* findNext();
	DFS* getNode(int theIndex){return nodeList[theIndex];}
	void putNode(int theIndex) { nodeList[theIndex] = this;}
	DFS* getParent(){return getNode(parent);}
	bool hasParent(){return parent!=-1;}
protected:
	int parent;
	int sonCount;
	int sonIndex;
	int son;
	int depth;
	int index;//index in nodeList
	int data;
	void backTrack();
	static int trackRecord[MaxLevel];
	virtual DFS* createSon();
	virtual bool validateOption(int sonData);	
	virtual void onLeave();
	virtual bool evaluate();
	virtual void collectResult();
public:
	int getSolutionCount(){ return solutionCount;}
	void setOptions(int* array, int size);
	void setNameStr(char** str){nameString = str;}
	void beginCount(int max, bool findall=false);
};

#endif

DFSArray.lib is placed in "lib" directory under "vc98" directory!

missionary.cpp

#include <DFSArray.h>

using namespace std;

enum RiverSide
{LEFT, RIGHT};

enum People
{MISSIONARY, BARBARIAN};

struct Action
{
	int people[2];
	RiverSide riverSide;
};

Action actionArray[10] = {{{2,0},LEFT}, {{0,2}, LEFT}, {{1,1},LEFT},{{1,0},LEFT},
{{0,1}, LEFT}, {{2,0},RIGHT}, {{0,2}, RIGHT}, {{1,1,}, RIGHT}, {{1,0}, RIGHT},{{0,1},RIGHT}};

//2M, 2B, 1M1B, 1M, 1B and LR means from left to right, RL is opposite
enum OptionType
{MM_LR, BB_LR, MB_LR, M_LR, B_LR, MM_RL, BB_RL, MB_RL, M_RL, B_RL}; 

//3 missionary are at left side of river
//3 barbarian are also at left side

int optionArray[10] = {MM_LR, BB_LR, MB_LR, M_LR, B_LR, MM_RL, BB_RL, MB_RL, M_RL, B_RL}; 

char* optionString[10] = {"MM_LR", "BB_LR", "MB_LR", "M_LR", "B_LR", "MM_RL", 
	"BB_RL", "MB_RL", "M_RL", "B_RL"};

bool isRoot = true;

class Missionary: public DFS
{
private:
	int Position[2][2];
	RiverSide boat;
	bool isLooping(int sonData);
	bool checkData(int sonData);
	bool initialized;
protected:
	bool validateOption(int sonData);
	DFS* createSon();
	bool evaluate();
public:
	Missionary();
};


int main()
{
	Missionary M;
	M.setNameStr(optionString);
	M.setOptions(optionArray, 10);
	M.beginCount(20, true);
	
	return 0;
}

Missionary::Missionary()
{
	if (isRoot)
	{
		Position[MISSIONARY][LEFT] = 3;
		Position[MISSIONARY][RIGHT]=0;
		Position[BARBARIAN][LEFT] = 3;
		Position[BARBARIAN][RIGHT]=0;
		isRoot = false;
		boat = LEFT;
	}
	initialized =false;
}

bool Missionary::evaluate()
{
	if (!initialized&&parent!=-1)//this is the first son
	{
		RiverSide river = actionArray[data].riverSide;
		RiverSide opposite = (river==LEFT?RIGHT:LEFT);
		//initialize Position so that it reflects the move
		//this is ackward as I cannot access son Ptr anymore
		Position[MISSIONARY][river]-= actionArray[data].people[MISSIONARY];
		Position[MISSIONARY][opposite] += actionArray[data].people[MISSIONARY];
		Position[BARBARIAN][river]-= actionArray[data].people[BARBARIAN];
		Position[BARBARIAN][opposite] += actionArray[data].people[BARBARIAN];
		boat = (boat==LEFT?RIGHT:LEFT);
		initialized = true;
	}
	return Position[MISSIONARY][RIGHT]==3;
}

bool Missionary::isLooping(int sonData)
{
	backTrack();
	return (trackRecord[depth-1] - sonData==5)||(sonData - trackRecord[depth-1] ==5);
}


bool Missionary::checkData(int sonData)
{
	RiverSide river = actionArray[sonData].riverSide;
	RiverSide opposite = (river==LEFT?RIGHT:LEFT);
	
	if (river==RIGHT
		&&Position[MISSIONARY][river] - actionArray[sonData].people[MISSIONARY]==0
		&&Position[BARBARIAN][river] - actionArray[sonData].people[BARBARIAN]==0)
		return false;

	return ((Position[MISSIONARY][river] - actionArray[sonData].people[MISSIONARY]>=
		Position[BARBARIAN][river] - actionArray[sonData].people[BARBARIAN])
		||(Position[MISSIONARY][river] - actionArray[sonData].people[MISSIONARY]==0))
		
		&&
		((Position[MISSIONARY][opposite]+ actionArray[sonData].people[MISSIONARY]>=
		Position[BARBARIAN][opposite]+actionArray[sonData].people[BARBARIAN])
		||(Position[MISSIONARY][opposite]+ actionArray[sonData].people[MISSIONARY]==0));
}

bool Missionary::validateOption(int sonData)
{
	
	if (!initialized&&parent!=-1)//this is the first son
	{
		RiverSide river = actionArray[data].riverSide;
		RiverSide opposite = (river==LEFT?RIGHT:LEFT);
		//initialize Position so that it reflects the move
		//this is ackward as I cannot access son Ptr anymore
		Position[MISSIONARY][river]-= actionArray[data].people[MISSIONARY];
		Position[MISSIONARY][opposite] += actionArray[data].people[MISSIONARY];
		Position[BARBARIAN][river]-= actionArray[data].people[BARBARIAN];
		Position[BARBARIAN][opposite] += actionArray[data].people[BARBARIAN];
		boat = (boat==LEFT?RIGHT:LEFT);
		initialized = true;
	}


	if (boat!=actionArray[sonData].riverSide)
	{
		return false;
	}
	else
	{
		if (Position[MISSIONARY][boat]<actionArray[sonData].people[MISSIONARY]||
			Position[BARBARIAN][boat]<actionArray[sonData].people[BARBARIAN])
		{
			return false;
		}
		if (!isLooping(sonData))
		{
			if (checkData(sonData))
			{
				return true;
			}
		}
	}
	return false;
}


DFS* Missionary::createSon()
{
	DFS* ptr= new Missionary;
	for (int i=0; i<2; i++)
	{
		for (int j=0; j<2; j++)
		{
			((Missionary*)(ptr))->Position[i][j] = Position[i][j];
		}
		((Missionary*)(ptr))->boat = boat;
	}
	return ptr;
}

Running result of program:

The route is:BB_LR, B_RL, BB_LR, B_RL, MM_LR, MB_RL, MM_LR, It is number:0
The route is:MB_LR, M_RL, BB_LR, B_RL, MM_LR, MB_RL, MM_LR, It is number:1
Press any key to continue

Do you understand the result? It means 2B go, 1B back, 2B go, 1B back, 2M go, 1M1B back, 2M go-->succeed!