8 Puzzle Code - Queue.cpp

#include "stdafx.h"
#include "queue.h"

Queue::Queue(){
head=NULL;
tail=NULL;
}

BOOL Queue::isEmpty(){

return (head==NULL && tail==NULL);

}



void Queue::add(char* p, char* pp){

StateNode* newnode = new StateNode();
newnode->setPuzzle(p);
newnode->setParentState(pp);

if(isEmpty()){
head=newnode;
tail=head;
}
else{
tail->next=newnode;
tail=newnode;
}
}

StateNode* Queue::get(){
StateNode* temp;
temp=head;
head=head->next;
if(head==NULL) tail=NULL;
return temp;
}

void Queue::deleteNode(StateNode* n){
StateNode* curr=head;
while(curr!=NULL){
head=head->next;
delete curr;
curr=head;
}
}

Queue::~Queue(){
TRACE(_T("Delete Q...\n"));
deleteNode(head);
}

8 Puzzle Code - StateNode.h

#define SIZE 9
class StateNode{
public:
char puzzle[SIZE];
char parentstate[SIZE];

StateNode* next;

StateNode(){
next=NULL;
}

void setPuzzle(char* p){
for(int v=0; v<SIZE; v++) puzzle[v]=*(p+v);
}

void setParentState(char *pp){
for(int v=0; v<SIZE; v++) parentstate[v]=*(pp+v);
}
};

8 Puzzle Code - Queue.h

Share code: 8 Puzzle Code - Queue.h

#include "statenode.h"

class Queue{
public:
StateNode* head;
StateNode* tail;

Queue();
~Queue();
void deleteNode(StateNode*);
void add(char* , char*);
BOOL isEmpty();
StateNode* get();
};

8 Puzzle Code - ReadMe.txt

//This program try to solve the 8-PUZZLE problem.

//Program version: Version 1
//Create date: 26 JUN 2002
//Description: Background process the solution.
1) Initial the problem first stage.
2) Expand the problem tree space from problem state to
new state.
3) This version got some bugs in expanding to new state.
4) Using Queue data structure and State Node to implement problem
tree problem space and performing breath first search algo.
5) Did not implement step by step solutions display.
6) Solution to puzzle problem is performed background.
7) Some bugs, new state didnt be generated correctly.

//Program version: Version 2
//Create date: 28 JUN 2002
//Description: 1) Enhance version 1.
2) Implement puzzle problem tree using tree data structure.
3) Create multi expanding tree using Tree and TreeNode data
structure. Implementing maximum four child per node.
4) Implementing breath first search on tree using Queue data
structure.
5) Implementing step by step solution display. Using stack to
collect the state from the bottom of tree until the root
of problem tree.
6) Limitation:
** Did not implement heuristic search technique.
** Problem is, the n number of expanded node is
3 to the power of steps for solution to a certain
question.
** Need a lot of time and memory space to solve certain
puzzle problem.

//Update 3 July 2002
1) Implement Heuristic search. Mahathan distance heuristic search.
Be able to solve certain difficult puzzle in short time.
Better than blind breath first search.

//Update 8 July 2002
1) Add a pair of previous and next button for user to step through the
solution computer get.


//Update 11 July 2002
1) Correct wrong implementation of Manhattan Distance Algorithm.
2) Implement correct Manhattan Distance Algorithm.
3) Fix some exception memory bugs.

8 Puzzle Code - LinkStack.h

#include "TreeNode.h"

#ifndef _LINKSTACK_H
#define _LINKSTACK_H

class LinkNode{
public:
TreeNode* treenode;
LinkNode* next;
LinkNode(TreeNode* thenode){
treenode=thenode;
next=NULL;
}
};

class LinkStack{
public:
LinkNode* head;
LinkStack(){ head=NULL; }

~LinkStack(){
deletenode(head);
}

void deletenode(LinkNode *n){
if(n==NULL) return;
deletenode(n->next);
delete n;
}

BOOL isEmpty() { return (head==NULL); }

void push(TreeNode* thenode){
LinkNode* newnode = new LinkNode(thenode);
if(isEmpty()){
head=newnode;
}
else{
newnode->next=head;
head=newnode;
}
}

UINT NumOfNodes(){
LinkNode* curr;
curr=head;
UINT temp;
temp=0;
while(curr!=NULL){
temp++;
curr=curr->next;
}

return temp;
}

LinkNode* getNode(int nodeno){
int i;
LinkNode* curr;
curr=head;
i=0;
while(i<nodeno){
curr=curr->next;
i++;
}

return curr;
}

LinkNode* pop(){
LinkNode* temp;
temp=head;
head=head->next;
return temp;
}

void reset(){
if(head==NULL) return;
deletenode(head);
head=NULL;
}
};

#endif

8 Puzzle Code - LinkQueue.h

#include "TreeNode.h"

#ifndef _LINKQUEUE_H
#define _LINKQUEUE_H

#define TILESTEPS 1
#define DISTANCE 2
#define MANHATTAN 3
#define ASTAR 4

class QueueNode{
public:
TreeNode* treenode;
QueueNode* next;
QueueNode(TreeNode* thenode){
treenode=thenode;
next=NULL;
}
};

class LinkQueue{
public:
QueueNode* head;
QueueNode* tail;

LinkQueue(){
head=NULL;
tail=NULL;
}

BOOL isEmpty(){ return (head==NULL && tail==NULL); }

void add(TreeNode* thenode){
QueueNode* newnode = new QueueNode(thenode);
if(isEmpty()){
head=newnode;
tail=head;
}
else{
tail->next=newnode;
tail=newnode;
}
}

//Add in version 3.
//Adding Q with sort manner according to node heuristic value.
void addHeuristic(TreeNode* thenode, int type){
UINT currh, newh;
QueueNode* newnode=new QueueNode(thenode);

if(isEmpty()){
head=newnode;
tail=head;
}
else{
QueueNode* prevnode;
QueueNode* currnode;
BOOL addedflag;

addedflag=false;
currnode=head;
prevnode=NULL;

while(currnode!=NULL){
switch(type){
case TILESTEPS:
case DISTANCE:
case MANHATTAN:
currh=currnode->treenode->h;
newh=newnode->treenode->h;
break;

case ASTAR:
currh=currnode->treenode->fn;
newh=newnode->treenode->fn;
break;
}

if( currh>newh ){
if(prevnode==NULL){
head=newnode;
head->next=currnode;
}
else{
newnode->next=currnode;
prevnode->next=newnode;
}

addedflag=true;
break;
}

prevnode=currnode;
currnode=currnode->next;
}

if(!addedflag){
tail->next=newnode;
tail=newnode;
}
}
}

QueueNode* get(){
QueueNode* temp;
temp=head;
head=head->next;
if(head==NULL) tail=NULL;
return temp;
}

void deleteNode(){
QueueNode* curr;
curr=head;
while(curr!=NULL){
head=head->next;
delete curr;
curr=head;
}
}

void reset(){
deleteNode();
head=NULL;
tail=NULL;
}

~LinkQueue(){
deleteNode();
}
};
#endif

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;
}

};