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.
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.
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: