I recently had to do a project for my AI class that could solve an 8 puzzle using an A* search in C++. I have to admit that I wish I could have spent more time cleaning up my code. What’s good is my linked list structure. What’s a little sloppy are my computational methods. Regardless, I thought that this code could still be useful for people who are new or rusty on how to use classes and setting up a search tree.
This is an empty console project, with one source file (main.cpp), one input file (in.txt), and one output file (out.txt). This code has been tested, compiled, and executed under Visual Studio 2008 Professional Edition.
My Algorithm
I created a tree class that could handle linked lists. Every linked node could have up to 4 children. I would simply build the tree structure out. Using the first heuristic, I would build the tree according to which node had the lowest distance from the root node. This is pretty much creating a tree by a breadth depth search. My second heuristic added in a cost for how similar the current node’s state was to the goal state. This allowed the tree to be built smartly and not continue to expand down bad branches.
I also added a constraint that wouldn’t allow a node to be created if it was trying to make a bad move. A bad move is when the puzzle is backtracking. Backtracking is a sure sign that that branch is not an optimal solution.
My Results
I ran my program using two different heuristics. One was many times more efficient than the other. My first heuristic was simply just using the distance from the root node. It took 6.63 minutes to complete.
/**************OUTPUT******************/ Success! n = 12 time: 663801 msecs Press any key to continue . . . /**************************************/
My second heuristic was adding a cost to the distance for how many numbers in the current state were in the same position as the numbers in the goal state. The output was significantly faster. It computed the the same path in under 1 second.
/**************OUTPUT******************/ Success! n = 12 time: 858 msecs Press any key to continue . . . /**************************************/
Using this Code
If you are working on a similar assignment, feel free to use this code and expand on it. I would really appreciate it if someone could polish the code for me and send me an updated copy. It could use a better class structure, better name conventions, prettier computational methods, and some relevant comments. I simply didn’t have time. Feel free to leave a comment if you have any questions trying to get this to work on your computer. I hope this helps!
#include
#include “printer.h”
#include “loader.h”
#include “vector.h”
struct MyTree_node
{
struct MyTree_node *link1;
struct MyTree_node *link2;
struct MyTree_node *link3;
struct MyTree_node *link4;
struct MyTree_node *parent;
char state[10];
int cost;
int blackItemIndex;
int distance;
};
typedef struct MyTree_node tree_node;
void match(Block shuff[],Block orginal[]);
void nullState(char s[]);
char initialState[10];
char finalState[10];
tree_node* root = NULL;
int heuristic;
int success;
int inxBlackItemIndex;
vector stack;
void build()
{
makeRoot(initialState);
success = 0;
tree_node *curr = (tree_node *)calloc(1,sizeof(tree_node));
heuristic = 1;
int count = 0;
while (stack.size > 0)
{
curr = (tree_node *)front(&stack);
eraseBegin(&stack);
insert(curr);
if (curr->distance > count) {
count = curr->distance;
printf(“\nn = %d\n”,count);
}
}
}
void makeRoot(char state[])
{
tree_node *t1 = (tree_node *)calloc(1,sizeof(tree_node));
int inx;
for (inx = 0; inxstate[inx] = state[inx];
}
t1->state[inx] = ”;
t1->cost = h1(t1);
t1->distance = 1;
t1->link1 = NULL;
t1->link2= NULL;
t1->link3 = NULL;
t1->link4 = NULL;
t1->parent = NULL;
for (inx = 0; inxblackItemIndex = inx; break;
}
}
if(isEmpty(&stack))
{
root = t1;
vectorAddItem(&stack,t1);
}
}
int h1(tree_node* t)
{
int cost = 0;
int i;
for (i=0; istate[i] == ‘/’)
{
if (’2′ != finalState[i])
{
cost++;
}
}
else if (t->state[i] != finalState[i])
{
cost++;
}
}
return cost;
}
void makeMove(tree_node* curr, tree_node* t, char direction)
{
int temp, index;
int badMove = 0;
int i;
for (i=0; istate[i] == ‘/’)
{
index = i;
}
t->state[i] = curr->state[i];
}
t->blackItemIndex = index;
if (curr->distance > 2)
{
if (index == curr->parent->blackItemIndex)
{
badMove = 1;
}
}
switch (direction)
{
case ‘u’ :
if ((index > 2) && (badMove != 1)) {
temp = t->state[index];
t->state[index] = t->state[index-3];
t->state[index-3] = temp;
}
else
nullState(t->state);
break;
case ‘r’ :
if ((index%3 != 2) && (badMove != 1)) {
temp = t->state[index];
t->state[index] = t->state[index+1];
t->state[index+1] = temp;
}
else
nullState(t->state);
break;
case ‘d’ :
if ((index state[index];
t->state[index] = t->state[index+3];
t->state[index+3] = temp;
}
else
nullState(t->state);
break;
case ‘l’ :
if ((index%3 != 0) && (badMove != 1)) {
temp = t->state[index];
t->state[index] = t->state[index-1];
t->state[index-1] = temp;
}
else
nullState(t->state);
break;
}
}
void insert(tree_node* curr)
{
tree_node *t1 = (tree_node *)calloc(1,sizeof(tree_node));
makeMove(curr, t1, ‘u’);
t1->distance = curr->distance + 1;
t1->cost = h1(t1) + t1->distance;
t1->link1 = NULL; t1->link2 = NULL; t1->link3 = NULL; t1->link4 = NULL;
t1->parent = curr;
tree_node *t2 = (tree_node *)calloc(1,sizeof(tree_node));
makeMove(curr, t2, ‘r’);
t2->distance = curr->distance + 1;
t2->cost = h1(t2) + t2->distance;
t2->link1 = NULL; t2->link2 = NULL; t2->link3 = NULL; t2->link4 = NULL;
t2->parent = curr;
tree_node *t3 = (tree_node *)calloc(1,sizeof(tree_node));
makeMove(curr, t3, ‘d’);
t3->distance = curr->distance + 1;
t3->cost = h1(t3) + t3->distance;
t3->link1 = NULL; t3->link2 = NULL; t3->link3 = NULL; t3->link4 = NULL;
t3->parent = curr;
tree_node *t4 = (tree_node *)calloc(1,sizeof(tree_node));
makeMove(curr, t4, ‘l’);
t4->distance = curr->distance + 1;
t4->cost = h1(t4) + t4->distance;
t4->link1 = NULL; t4->link2 = NULL; t4->link3 = NULL; t4->link4 = NULL;
t4->parent = curr;
if ((curr->link1 == NULL) && (!isNullState(t1->state)))
{
curr->link1 = t1;
if (!success) vectorAddItem(&stack,curr->link1);
}
else
free(t1);
if ((curr->link2 == NULL) && (!isNullState(t2->state)))
{
curr->link2 = t2;
if (!success) vectorAddItem(&stack,curr->link2);
}
else
free(t2);
if ((curr->link3 == NULL) && (!isNullState(t3->state)))
{
curr->link3 = t3;
if (!success) vectorAddItem(&stack,curr->link3);
}
else
free(t3);
if ((curr->link4 == NULL) && (!isNullState(t4->state)))
{
curr->link4 = t4;
if (!success) vectorAddItem(&stack,curr->link4);
}
else
free(t4);
sort();
checkSuccess(curr);
}
void checkSuccess(tree_node* curr)
{
int pass1 = 1;
int pass2 = 1;
int pass3 = 1;
int pass4 = 1;
int i;
for (i=0; ilink1 != NULL)
{
if (curr->link1->state[i] != finalState[i])
pass1 = 0;
}
else
pass1 = 0;
if (curr->link2 != NULL)
{
if (curr->link2->state[i] != finalState[i])
pass2 = 0;
}
else
pass2 = 0;
if (curr->link3 != NULL)
{
if (curr->link3->state[i] != finalState[i])
pass3 = 0;
}
else
pass3 = 0;
if (curr->link4 != NULL)
{
if (curr->link4->state[i] != finalState[i])
pass4 = 0;
}
else
pass4 = 0;
}
if (pass1) {
success = 1;
printf(“Success\n”);
dispState(curr->link1->state);
}
else if (pass2) {
success = 1;
printf(“Success\n”);
dispState(curr->link2->state);
}
else if (pass3) {
success = 1;
printf(“Success\n”);
dispState(curr->link3->state);
}
else if (pass4) {
success = 1;
printf(“Success\n”);
dispState(curr->link4->state);
}
}
void sort()
{
tree_node *temp = (tree_node *)calloc(1,sizeof(tree_node));
int i,j;
for (i=0; i<stack.size-1; i++)
{
for (j=0; jcost > ((tree_node *)getItem(&stack,j+1))->cost)
{
temp = stack.buffer[j];
stack.buffer[j] = stack.buffer[j+1];
stack.buffer[j+1] = temp;
}
}
}
}
int main()
{
char *pathOrginalPicture = “pgmFile/original.pgm”;
char *pathShuffledPicture = “pgmFile/mixedpgm.pgm”;
Block mixedPicBlock[9],originalPicBlock[9];
loadBlock(pathOrginalPicture,pathShuffledPicture,originalPicBlock,mixedPicBlock);
match(mixedPicBlock,originalPicBlock);
dispState(initialState);
dispState(finalState);
printf(“\n——\n”);
initvector(&stack);
build();
return 1;
}
/*
* *************************************
* *************************************
* *************************************
* *************************************
* *************************************
* *************************************
* *************************************
*/
void nullState(char s[])
{
int inx;
for(inx=0; inx<9; inx++)
s[inx] = NULL;
}
int isNullState(char s[])
{
if(s[0] == NULL) return 1;
else return 0;
}
void match(Block shuff[],Block orginal[])
{
int hinx,winx,counter;
for(hinx=0; hinx<9; hinx++)
{
finalState[hinx] = hinx + '0';
}
finalState[hinx] = '';
for(hinx=0; hinx<9; hinx++)
{
counter=0;
for(winx=0; winx<9; winx++)
{
if(isSameBlock(shuff[hinx],orginal[winx])) initialState[hinx] = finalState[winx];
else counter++;
}
if(counter == 9)
{
initialState[hinx] = '/';
inxBlackItemIndex = hinx;
}
}
initialState[hinx] = '';
}
Comment by murat — December 13, 2010 @ 7:59 pm
thanx bro.
Comment by kuldeep — July 18, 2011 @ 11:27 pm
thanx.very nice.
Comment by HamiD — November 26, 2011 @ 12:30 am
hi, when ur saying each node can have up to 4 children the “n” limit is 16 on the search? if i set an initial and final states that needs for example 22 nodes to find the answer this code wont work?
where do u defin the 4 children limit?
Comment by Fernando — March 29, 2012 @ 1:25 pm
Hey,
I’ve taken a look at your main.cpp, under what filename is the above source code supposed to be?
Comment by Anonymous — April 14, 2012 @ 11:20 pm