DFSArray---New Knight

A. Third Edition

This is my third edition of my DFS class implemented with an array (The second edition never appear on web as it

is only a minor different from first edition.  Or you can call it second version of Knights-tour problem which I

wrote long before with a series of functions.

B.The problem

There is a big change in this edition that I changed the dynamic allocating nodes to be a kind of pre-created 

nodes. It is meaningless to "new" and "delete" those nodes since the nodes remains there, only that the data

inside nodes changes. So, why don't we just change the data instead of creating and deleting nodes?

However, most part of code of previous version remains unchanged. I only initialize all pointers in the pointer

array to point to a real derived class objects. And won't delete them until end of program. When son node is created

only data in the node was initialized, but not the object was created as it is created already first time.

D.The major functions

1. void DFS::addSon(int sonData)

This function now only points to the son node without "new" a son node object.

2. virtual void onBeginSearch();

This virtual function gives user opportunity to initialize data just before searching starts.

3. virtual void onAfterAdded();

This function gives user opportunity to synchronize data between parent and son just after son node is created.

4. virtual DFS* createSon() = 0;

Now this function is only called in base class to create all nodes in the first time to guarentee it is creating

son node.

5. 

E.Further improvement

1. There is trade off for OOP as it slows down program execution by too many object operations. 

2. Should add weight concept in next eddiition just as before.

//file DFSArray.h

#ifndef DFSARRAY_H
#define DFSARRAY_H
#include <iostream>

using namespace std;

const int MaxSonCount=8;

const int MaxLevel = 120;

const int MaxOptions = 16;

const int MaxNodeCount = 300;

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

#endif

//file DFSArray.cpp

#include <iostream>
#include "DFSArray.h"

using namespace std;

int DFS::domino = 0;
bool DFS::findAll = false;
bool DFS::initialized = false;
int DFS::maxLevel = 0;
int DFS::optionArray[MaxOptions] = {0};
char** DFS::nameString=NULL;
int DFS::solutionCount = 0;
int DFS::optionCount = 0;
DFS* DFS::nodeList[MaxNodeCount] = {NULL};
int DFS::trackRecord[MaxLevel]= {0};


bool DFS::touchDown()
{
	return depth==maxLevel;
}

void DFS::onBeginSearch()
{
	//programmer may need do some initializing job here!
}

void DFS::onAfterAdded()
{
	//programmer may need do something for his own purpose
}

void DFS::onLeave()
{
	DFS* ptr =this;
	if (ptr->hasParent())
	{
		DFS* father = ptr->getParent();
		/*
		for (int i= father->son; i<father->sonCount; i++)
		{
			delete nodeList[i];
			nodeList[i] = NULL;
		}
		*/
		domino -= father->sonCount;
		father->sonCount = 0;
		father->son = -1;	
	}	
}

void DFS::backTrack()
{
	DFS* ptr = this;

	while (ptr->hasParent())
	{
		trackRecord[ptr->depth-1] = ptr->data;
		ptr = ptr->getParent();
	}
}


//a stack
void DFS::collectResult()
{
	backTrack();
	cout<<"The route is:\n";
	for (int i=0; i<depth; i++)
	{
		cout<<nameString[trackRecord[i]]<<", ";
	}
	cout<<"\nIt is number:"<<solutionCount++;
	cout<<endl;
}

void DFS::setOptions(int *array, int size)
{
	optionCount = size;
	for (int i=0; i<size; i++)
	{
		optionArray[i] = *(array+i);
	}
}

DFS::~DFS()
{
	if (initialized)
	{
		for (int i=1; i<MaxNodeCount; i++)//the i=0 is root which is not dynamic allocated!
		{
			delete nodeList[i];
		}
		domino =0;
		initialized=false;
	}
}


void DFS::onGenerate()
{
	//programmer may need to initialize at this stage
}


bool DFS::beginCount(int max, bool findall)
{
	DFS* ptr = this;
	setMaxLevel(max);
	findAll = findall; //setup if want all result
	initialize(this);
	onBeginSearch();//this is done from root!

	while (ptr!=NULL)
	{
		//programmer may need to initialize at this stage
		ptr->onGenerate();
		if (ptr->generate())
		{
			ptr = ptr->upDate();//move to first son			
			if (ptr->evaluate())
			{
				ptr->collectResult();
				if (!findAll)
				{
					break;
				}
				else
				{
					ptr = ptr->findNext();
									
				}
			}
			else
			{
				if (ptr->touchDown())//for a new son
				{
					ptr=ptr->findNext();
										
				}
			}
		}
		else
		{
			ptr = ptr->findNext();//for a new son
			
		}
	}
	if (solutionCount==0)
	{
		cout<<"no solution!";
		return false;
	}
	else
	{
		cout<<"Total solution is "<<solutionCount<<endl;
		return true;
	}
		
}
	
DFS* DFS::findNext()
{
	DFS* ptr = this;
	DFS* dummy;
	while (ptr!=NULL)
	{
		if (ptr->hasBrother())
		{
			ptr = getNode(ptr->index+1);//next brother
			
			return ptr;			
		}
		else
		{
			if (ptr->hasParent())
			{
				dummy = ptr;
				ptr = ptr->getParent(); //if 
				dummy->onLeave(); //only clear when go up one level
			}
			else
			{
				break;
			}
		}
	}
	return NULL;
}

bool DFS::generate()
{
	bool result = false;
	if (touchDown())
	{
		return false;
	}
	//this is preorder and I don't bother to 
	//give choices for midorder or postorder
	for (int i=0; i< optionCount; i++)
	{
		if (validateOption(optionArray[i]))
		{
			addSon(optionArray[i]);
			result = true;		
		}
	}
	return result;
}


DFS* DFS::upDate()
{
	//return first son	
	return getNode(son);
}

/* a pure virtual
//must be override by user when inherited
DFS* DFS::createSon()
{
	DFS* ptr = new DFS;
	return ptr;
}
*/


void DFS::addSon(int sonData)
{	
	if (sonCount+1<MaxSonCount)
	{
		if (domino==MaxNodeCount)
		{
			cout<<"Exceeds limit of node list"<<endl;
			return;
		}
		//DFS* ptr = createSon();
		DFS* ptr = nodeList[domino];
		ptr->index = domino;//
		//ptr->putNode(domino);		

		if (sonCount==0)//if it is the first son
		{
			son = domino;//first son 
		}
		domino++;
		ptr->data = sonData;
		ptr->sonCount = 0;
		ptr->son = -1;//temporarily
		ptr->parent = index;
		ptr->depth = depth+1;
		ptr->sonIndex = sonCount;
		sonCount++;
		ptr->onAfterAdded();
	}
	else
	{
		cout<<"Exceed max of sons!";
	}
}

void DFS::initialize(DFS* now)
{
	now->index =0;	
	now->depth = 0;
	now->sonCount = 0;
	now->sonIndex = -1;
	now->parent = -1;
	now->data = 0;
	now->son = -1;
	now->putNode(0); //put in list

	if (!initialized)
	{
		for (int i=1; i<MaxNodeCount; i++)
		{
			nodeList[i] = createSon();
		}
		initialized = true;
	}
	domino++;
}

bool DFS::hasBrother()
{
	if (hasParent())
	{
		if (getParent()->sonCount > sonIndex+1)//has little brother
		{
			return true;
		}
	}
	return false;
}

//file Knights.cpp

#include <iostream>
#include "DFSArray.h"
using namespace std;

const int BoardSize = 6;


enum MoveType
{RightUp, UpRight, UpLeft, LeftUp, LeftDown, DownLeft, DownRight, RightDown};

int moveChoice[8] = 
	{RightUp, UpRight, UpLeft, LeftUp, LeftDown, DownLeft, DownRight, RightDown};

char* moveStr[8] = 
{"RightUp", "UpRight", "UpLeft", "LeftUp", "LeftDown", "DownLeft", "DownRight", "RightDown"};


struct Pos
{
	int x;
	int y;
};

Pos startPos = {0,0};


class Knights: public DFS
{
	bool board[BoardSize][BoardSize];
	Pos pos;
	Pos testMove(MoveType theMove, Pos thePos);
	void move(MoveType theMove);
protected:
	void onAfterAdded();
	void onBeginSearch();
	DFS* createSon();
	bool validateOption(int sonData);
	bool evaluate();
	void collectResult();
public:
};

int main()
{
	Knights K;
	K.setOptions(moveChoice, 8);
	K.setNameStr(moveStr);
	for (int r=0; r<BoardSize/2; r++)
	{
		for (int c =0; c<r+1; c++)
		{
			startPos.x = r;
			startPos.y = c;
			cout<<"startPos("<<r<<','<<c<<") is:";
			if (K.beginCount(BoardSize*BoardSize, true))
			{
				return 0;
			}
			cout<<endl<<endl;

		}
	}
	return 0;
}


void Knights::onAfterAdded()
{
	DFS* ptr = getParent();
	for (int r=0; r<BoardSize; r++)
	{
		for (int c=0; c<BoardSize; c++)
		{
			board[r][c] = ((Knights*)(ptr))->board[r][c];
		}
	}
	pos = ((Knights*)(ptr))->pos;
	if (depth!=0)
	{
		move((MoveType)(data));
	}
}

void Knights::collectResult()
{
	int temp[BoardSize][BoardSize]={0};
	Pos curPos = startPos;

	DFS::collectResult();//do what should be done first
	for (int i=0; i<BoardSize*BoardSize; i++)
	{
		temp[curPos.x][curPos.y] = i+1;
		curPos = testMove((MoveType)(trackRecord[i]), curPos);
	}
	cout<<endl;
	for (int r=0; r<BoardSize; r++)
	{
		for (int c=0; c<BoardSize; c++)
		{
			cout<<temp[r][c]<<'\t';
		}
		cout<<endl;
	}
}

bool Knights::evaluate()
{
	return depth==BoardSize*BoardSize;
}

bool Knights::validateOption(int sonData)
{
	Pos temp = testMove((MoveType)(sonData), pos);
	if (temp.x<0||temp.x>BoardSize-1||temp.y<0||temp.y>BoardSize-1)
	{
		return false;
	}
	if (board[temp.x][temp.y])
	{
		return false;
	}
	return true;
}

void Knights::onBeginSearch()
{
	for (int r=0; r<BoardSize; r++)
	{
		for (int c=0; c<BoardSize; c++)
		{
			board[r][c] = false;
		}
	}
	board[startPos.x][startPos.y] = true;
	pos = startPos;

}

//copy data from parent
DFS* Knights::createSon()
{
	DFS* ptr = new Knights;
	if (ptr==NULL)
	{
		cout<<"unable to create new node!\n";
	}

	return ptr;
}




Pos Knights::testMove(MoveType theMove, Pos thePos)
{
	Pos temp = thePos;
	switch (theMove)
	{
	case RightUp:
		temp.x += 2;
		temp.y -= 1;
		break;
	case UpRight:
		temp.x += 1;
		temp.y -= 2;
		break;
	case UpLeft:
		temp.x -= 1;
		temp.y -= 2;
		break;
	case LeftUp:
		temp.x -= 2;
		temp.y -= 1;
		break;
	case LeftDown:
		temp.x -= 2;
		temp.y += 1;
		break;
	case DownLeft:
		temp.x -= 1;
		temp.y += 2;
		break;
	case DownRight:
		temp.x += 1;
		temp.y += 2;
		break;
	case RightDown:
		temp.x += 2;
		temp.y += 1;
		break;
	}
	return temp;
}


void Knights::move(MoveType theMove)
{
	pos = testMove(theMove, pos);
	board[pos.x][pos.y] = true;
}

Running result of program: