8 Puzzle Code - Tree.h

Tree node processing methods code:

#include "TreeNode.h"
#include "LinkQueue.h"
#include "LinkStack.h"
#define SIZE 9
#define TILESTEPS 1
#define DISTANCE 2
#define MANHATTAN 3
#define ASTAR 4

class PuzzleTree{
public:
TreeNode* root;

PuzzleTree(){ root=NULL; }
~PuzzleTree(){
DeleteTree(root);
}

void SetTreeRoot(TreeNode* rootnode){
root=rootnode;
}

//Adding in version 2
//The generated state is no duplicated with previous state.
void GenerateNewStateNodeNoDup(TreeNode* currnode){
int spcpos;
char *currstate;
char temp[SIZE];
currstate=currnode->state;
spcpos=getSpacePos(currstate);
if( (spcpos-3)>=0 ){
newState(temp, currstate, spcpos, spcpos-3);
if(currnode->parent==NULL)
{addChild(currnode, temp);}
else{
if(!isEverSameState(temp, currnode)){ addChild(currnode,temp);}
}
}

if( (spcpos-1)>=0 && (spcpos-1)!=2 && (spcpos-1)!=5){
newState(temp, currstate, spcpos, spcpos-1);
if(currnode->parent==NULL)
{ addChild(currnode, temp);}
else{
if(!isEverSameState(temp, currnode)){ addChild(currnode,temp);}
}
}

if( (spcpos+3)<SIZE ){
newState(temp, currstate, spcpos, spcpos+3);
if(currnode->parent==NULL){ addChild(currnode, temp);}
else{
if(!isEverSameState(temp, currnode)){ addChild(currnode,temp);}
}
}

if( (spcpos+1)<SIZE && (spcpos+1)!=3 && (spcpos+1)!=6){
newState(temp, currstate, spcpos, spcpos+1);
if(currnode->parent==NULL){ addChild(currnode, temp);}
else{
if(!isEverSameState(temp, currnode)){addChild(currnode,temp); }
}
}
}//End of Generate New State with no previous duplication.


void GenerateNewStateNode(TreeNode* currnode){
int spcpos;
char *currstate;
char temp[SIZE];
currstate=currnode->state;
spcpos=getSpacePos(currstate);
if( (spcpos-3)>=0 ){
newState(temp, currstate, spcpos, spcpos-3);
if(currnode->parent==NULL){addChild(currnode, temp);}
else{
if(!isSameState(temp, currnode->parent->state)){addChild(currnode,temp);}
}
}

if( (spcpos-1)>=0 && (spcpos-1)!=2 && (spcpos-1)!=5){
newState(temp, currstate, spcpos, spcpos-1);
if(currnode->parent==NULL){addChild(currnode, temp);}
else{
if(!isSameState(temp, currnode->parent->state)){addChild(currnode,temp);}
}
}

if( (spcpos+3)<SIZE ){
newState(temp, currstate, spcpos, spcpos+3);
if(currnode->parent==NULL){ addChild(currnode, temp);}
else{
if(!isSameState(temp, currnode->parent->state)){ addChild(currnode,temp);}
}
}

if( (spcpos+1)<SIZE && (spcpos+1)!=3 && (spcpos+1)!=6){
newState(temp, currstate, spcpos, spcpos+1);
if(currnode->parent==NULL){ addChild(currnode, temp);}
else{
if(!isSameState(temp, currnode->parent->state)){addChild(currnode,temp);}
}
}
}//End Generate New State procedure.

void BackTrackTree(TreeNode* thisnode, LinkStack* s){
TreeNode* curr;
curr=thisnode;
while(curr!=NULL){
s->push(curr);
curr=curr->parent;
}
}

void ExposeNextState(TreeNode* currnode, LinkQueue* q){
if(currnode->child1!=NULL) q->add(currnode->child1);
if(currnode->child2!=NULL) q->add(currnode->child2);
if(currnode->child3!=NULL) q->add(currnode->child3);
if(currnode->child4!=NULL) q->add(currnode->child4);
}

//Add in version 3.
//Calculate tree node heuristic value and add to q with sorted manner.
//Sort manner will perform multi level expanding tree according to
//good heuristic value node be expanded first.
void ExposeNextStateHeuristic(TreeNode* currnode, LinkQueue* q, int htype){
if(currnode->child1!=NULL) {
GetHeuristicValue(currnode->child1,htype);
q->addHeuristic(currnode->child1, htype);
}

if(currnode->child2!=NULL) {
GetHeuristicValue(currnode->child2,htype);
q->addHeuristic(currnode->child2, htype);
}

if(currnode->child3!=NULL) {
GetHeuristicValue(currnode->child3,htype);
q->addHeuristic(currnode->child3, htype);
}

if(currnode->child4!=NULL) {
GetHeuristicValue(currnode->child4,htype);
q->addHeuristic(currnode->child4, htype);
}
}

void reset(){
if(root==NULL) return;
DeleteTree(root);
root=NULL;
}

void DeleteTree(TreeNode* root){
if(root==NULL) return;
DeleteTree(root->child1);
DeleteTree(root->child2);
DeleteTree(root->child3);
DeleteTree(root->child4);
delete root;
}

UINT GetCharValue(char c){
UINT ch;
ch=0;
switch(c){
case '1': ch=1; break;
case '2': ch=2; break;
case '3': ch=3; break;
case '4': ch=4; break;
case '5': ch=5; break;
case '6': ch=6; break;
case '7': ch=7; break;
case '8': ch=8; break;
case '#': ch=9; break
}

return ch;
}

//Other usage function.
void GetHeuristicValue(TreeNode* anode, int type){
UINT hvalue;
int v;

switch(type){
case TILESTEPS:
hvalue=0;
for(v=0; v<SIZE; v++){
if(anode->state[v]=='#') continue;
hvalue+=abs(v-GetCharValue(anode->state[v])+1);
}

anode->h=hvalue;
break;

case DISTANCE: //Number of tile that are not put in correct position.
//Not including the space.

hvalue=0;
for(v=0; v<SIZE; v++){
if(anode->state[v]!='#'){
if( (v+1)!=(int)GetCharValue(anode->state[v]) )
hvalue++;
}
}

anode->h=hvalue;
break;

case MANHATTAN:
hvalue=GetManhattanDistance(anode->state);
anode->h=hvalue;
break;

case ASTAR: //Calculating A* algorithm.
anode->gn=anode->parent->gn+1; //cause cost for epanding node is 1.
anode->hn=GetManhattanDistance(anode->state);
hvalue= anode->gn + anode->hn;
anode->fn=hvalue;
break;

}//End solution switch.
}

void addChild(TreeNode* thisnode, char *state){
TreeNode* newnode = new TreeNode();
newnode->parent=thisnode;
newnode->setState(state);

if(thisnode->child1==NULL) {
thisnode->child1=newnode;
return;
}

if(thisnode->child2==NULL) {
thisnode->child2=newnode;
return;
}

if(thisnode->child3==NULL) {
thisnode->child3=newnode;
return;
}

if(thisnode->child4==NULL) {
thisnode->child4=newnode;
return;
}
}



void newState(char *n, char *p, int oldp, int newp){
char hold;
for(int v=0; v<SIZE; v++) *(n+v)=*(p+v);
hold=*(n+newp);
*(n+newp)=*(p+oldp);
*(n+oldp)=hold;
}



BOOL isEverSameState(char *s, TreeNode* thisnode){
BOOL flag;
TreeNode* curr;
flag=false;
curr=thisnode->parent;
while(curr!=NULL){
if(isSameState(s, curr->state)){
flag=true;
break;
}

curr=curr->parent;
}

return flag;
}

BOOL isSameState(char *s1, char *s2){
BOOL flag;
flag=true;
for(int v=0; v<SIZE; v++){
if(*(s1+v)!=*(s2+v)){
flag=false;
break;
}
}
return flag;
}

int getSpacePos(char *s){
int p;
for(int v=0; v<SIZE; v++){
if(*(s+v)=='#'){
p=v;
break;
}
}
return p;
}

int GetManhattanDistance(char *s){

int c, r, ap, ar, ac; //current col, current row, actual position.
//actual col, actual row.

int m; //manhattan distance value.
m=0;
for(int v=0; v<SIZE; v++){
if(*(s+v)=='#') continue; //skip space.
r=v/3;
c=v%3;
ap=GetCharValue(*(s+v))-1;
ar=ap/3;
ac=ap%3;
m=m+(abs(r-ar)+abs(c-ac));
}

return m;
}

};