/************************************************************************/
/* */
/* Solving 8-puzzle Problem by A* algorithms */
/* */
/* */
/************************************************************************/
#include "solvePuzzleAStarSearch.h"
//////////////////////////////////////////////////////////////////////////
/// CHECK WHETHER OR NOT THE TWO NODES ARE OF THE SAME
///
bool isEqual( StateList *st1, StateList *st2)
{
int i,j;
for (i=0;i<3;i++)
for (j=0;j<3;j++)
if ( st1->a[i][j] != st2->a[i][j]) return false;
return true;
}
//////////////////////////////////////////////////////////////////////////
/// CHENCK WHETHER OR NOT THE NEW NODE IS EXPANDED REPEATELY
///
bool isLastState(StateList *st1,StateList *lt)
{
if(lt==NULL) return false;
if(lt->last==NULL) return false;
return isEqual(st1,lt->last);
}
//////////////////////////////////////////////////////////////////////////
/// CHECK WHETHER OR NOT THE NODE IS IN THE LIST
///
StateList *inList(StateList *state, StateList *list)
{
StateList *pList = list;
while (pList && ! isEqual(state,pList))
{
pList = pList->next;
if (pList == NULL)
break;
}
return pList;
}
//////////////////////////////////////////////////////////////////////////
/// DELETE A NODE FROM THE LINK LIST
///
StateList *del(StateList *state, StateList *list)
{
StateList *pList = list;
StateList *pLast = NULL;
StateList *pTemp = NULL;
while (pList && ! isEqual(state,pList))
{
pLast = pList;
pList = pList->next;
}
if ((NULL != pLast) && (NULL != pList))
{
pLast->next = pList->next;
pTemp = pLast;
}
else if (pLast) pTemp= NULL;
else if (pList) {pTemp = pList->next; delete(pList);}
else pTemp = NULL;
return pTemp;
}
//////////////////////////////////////////////////////////////////////////
/// INSERT THE NODE INTO THE OPEN TABLE
///
StateList *intoOpen(StateList *state, StateList *open)
{
/*StateList *ptemp = open;
StateList *plast = NULL;
StateList *pNewHead = open;
if (open == NULL)
{
state->next = NULL;
return state;
}
while (NULL != ptemp)
{
if (ptemp->f > state->f)
{
state->next = ptemp;
if (plast != NULL)
plast->next = state;
else
pNewHead = state;
}
else
{
plast = ptemp;
ptemp = ptemp->next;
}
}
if (ptemp == NULL && plast != NULL)
{
plast->next = state;
state->next = NULL;
}
return pNewHead;*/
if(open==NULL)
{
state->next=NULL;
return state;
}
else if (open->f > state->f)
{
state->next = open;
return state;
}
else
{
open->next = intoOpen(state,open->next); // recursively
return open;
}
}
//////////////////////////////////////////////////////////////////////////
/// INSERT THE NODE INTO THE CLOSED TABLE
///
StateList *intoClosed(StateList *state , StateList *closed)
{
state->next = closed;
return state;
}
//////////////////////////////////////////////////////////////////////////
/// CALCULATE THE VALUE OF H FUNCTION
///
double getHValue(StateList *state)
{
int i,j,s,t;
double p=0,q=0;
for (i=0; i < 3; i++)
{
for (j=0; j < 3; j++)
{
if (state->a[i][j] != desState.a[i][j])
q++;
bool flag = false;
for (s=0; s < 3; s++)
{
for (t=0; t < 3; t++)
{
if (desState.a[s][t] == state->a[i][j])
{
flag = true;
break;
}
}
if (flag)
break;
}
if (flag)
p = p + abs(s-i) + abs(t-j);
}
}
if (1==inn) return q;
else if (2==inn) return p;
else exit(0);
return 0;
}
//////////////////////////////////////////////////////////////////////////
/// EXAMINE THE STATUS AFTER MOVING A DIGIT
///
StateList *move(StateList *state , int i, int j )
{
int tmpRow,tmpCol;
StateList *tmp=NULL;
tmp = new StateList;
for (int k=0;k<3;k++)
for (int l=0;l<3;l++)
tmp->a[k][l] = state->a[k][l];
tmp->or=state->or;
tmp->ol=state->ol;
tmpRow=tmp->or;
tmpCol=tmp->ol;
tmp->a[tmpRow][tmpCol]=tmp->a[i][j]; // Move a(i,j) to the blank grid
tmp->a[i][j]=0;
tmp->or=i; // new position of new blank grid
tmp->ol=j;
tmp->last=NULL;
tmp->next=NULL;
tmp->f=0;
tmp->g=0;
genCount ++;
return tmp;
}
//////////////////////////////////////////////////////////////////////////
/// INSERT ALL THE NODES EXPANDED BY THE CURRENT NODE INTO THE LINK LIST
///
StateList *expand(StateList *state)
{
int i1,j1;
int i2,j2;
StateList *expandedState=NULL;
StateList *newState=NULL; // new state generated
for (i1=-1;i1<2;i1++)
for (j1=-1;j1<2;j1++)
{
if (i1==0 && j1==0) continue;
if (i1!=0 && j1!=0) continue;
i2=state->or+i1;
j2=state->ol+j1;
if (i2<0 || j2<0 || i2>2 || j2>2) continue;
newState=move(state,i2,j2); // call move() to generate new node
if (isLastState(newState,state))
{
delete(newState);
continue;
}
newState->last=state;
newState->g=state->g+1;
newState->f = newState->g + getHValue(newState); // f=g+h
newState->next=expandedState;
expandedState=newState;
}
expandCount ++;
return expandedState;
}
//////////////////////////////////////////////////////////////////////////
/// THE ESSENTIAL PROCEDURE OF THE A* ALGORITHMS
///
StateList *A(StateList *firstState)
{
StateList *expandedState=NULL;
StateList *first=NULL;
StateList *temp=NULL;
StateList *state=NULL;
open=firstState; // put initial state into the Open Table
closed=NULL;
while(open!=NULL)
{
first = open; // the first element of the Open Table
if (isEqual(first,&desState)) // If target, win.
return first; // Otherwise put first into the Closed Table
open = open->next;
closed = intoClosed(first, closed);
expandedState = expand(first); // Expand the FIRST node to get all its sub-nodes
while (expandedState!=NULL)
{
temp = expandedState;
expandedState = expandedState->next;
if (state = inList(temp, open))
{
if (temp->f < state->f)
{
open = intoOpen(temp, del(state, open));
delete(state);
}
else delete(temp); //Discard the temp
}
else if (state = inList(temp, closed))
{
if (temp->f < state->f)
{
closed = del(state, closed);
open = intoOpen(temp, open); // reinsert to the Open Table
expandCount --;
