astar.c

implementation od A* algorithm for tiling problem in C

//A* ALGORITHM
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
struct node{
int a[3][3];
int sd; //source distance
int hd; //heuristic disatnce
int tot;
struct node *next;
};
struct node * up(struct node *	n);
struct node * down(struct node * n);
struct node * left(struct node * n);
struct node * right(struct node * n);
void expand(struct node * n);
void insert(struct node * s);
struct node * f;  //pointer to first element of list containing states in order of their heuristic merit
int test(struct node *s);
int heuristic(struct node *n);
main()
{
//initialization
int i,j;
struct node s;
s.a[0][0]=2;
s.a[0][1]=8;
s.a[0][2]=3;
s.a[1][0]=1;
s.a[1][1]=6;
s.a[1][2]=4;
s.a[2][0]=7;
s.a[2][1]=0;
s.a[2][2]=5;
s.sd=0;
s.hd=heuristic(&s);
s.tot=s.sd+s.hd;
s.next=NULL;
f=&s;
while(f!=NULL)
	{
	int x;
	struct node *n;
	n=f;

	x=test(n);
	if(x==1)
		{
		printf("got the solution\n");
		for(i=0;i<3;i++)
		       {
		       for(j=0;j<3;j++)
			 printf("%d",n->a[i][j]);
		       printf("\n");
		       }
		printf("got the solution");
		getche();
		return 0;
		}
	else    {
		printf("trying and expanding this\n");
		for(i=0;i<3;i++)
		       {
		       for(j=0;j<3;j++)
			 printf("%d",n->a[i][j]);
		       printf("\n");
		       }
		
		expand(n);
		 f=f->next;
		 free(n);
		 }
	}
printf("algorithm failed");
return -1;
}

int test(struct node *n)
{
if((n->a[0][0])!=1)
	return 0;
if((n->a[0][1])!=2)
	return 0;
if((n->a[0][2])!=3)
	return 0;
if((n->a[1][0])!=8)
	return 0;
if((n->a[1][1])!=0)
	return 0;
if((n->a[1][2])!=4)
	return 0;
if((n->a[2][0])!=7)
	return 0;
if((n->a[2][1])!=6)
	return 0;
if((n->a[2][2])!=5)
	return 0;
else
	return 1;
}

void expand(struct node * n)
{

struct node *x;
if((x=up(n))!=NULL)
{
insert(x);
}
if((x=down(n))!=NULL)
{
insert(x);
}
if((x=left(n))!=NULL)
{
insert(x);
}
if((x=right(n))!=NULL)
{
insert(x);
}

return ;
}

struct node * up(struct node * n)
{

struct node * r;
int i,j,y,x=0;
int t1;
for(i=0;i<3;i++)
	{

	for(j=0;j<3;j++)
		{
		if((n->a[i][j])==0)
			{
			x=i;
			y=j;
			}
		}


	}
if(x==0)
	return NULL;
else
{
r=(struct node *) malloc(sizeof(struct node));
if(r==NULL)
	{
	printf("failure to get memory, press any button to quit") ;
	getche();
	exit(-1);
	}
else
	{
	
	for(i=0;i<3;i++)
	{

	for(j=0;j<3;j++)
		{
		r->a[i][j]=n->a[i][j];
		}


	}
	t1=(r->a[x-1][y]);
	(r->a[x-1][y])=0;
	(r->a[x][y])=t1;
	(r->sd)=(n->sd)+1;
	(r->hd)=heuristic(r);
	(r->tot)=(r->sd)+(r->hd);
	}
}
return r;
}

struct node * down(struct node * n)
{

struct node * r;
int i,j,y,x=0;
int t1;
for(i=0;i<3;i++)
	{

	for(j=0;j<3;j++)
		{
		if((n->a[i][j])==0)
			{
			x=i;
			y=j;

			}
		}


	}
if(x==2)
	return NULL;
else
{
r=(struct node * ) malloc(sizeof(struct node));
if(r==NULL)
	{
	printf("failure to get memory, press any button to quit")  ;
	getche();
	exit(-1);
	}
else
	{
	
	for(i=0;i<3;i++)
	{

	for(j=0;j<3;j++)
		{
		r->a[i][j]=n->a[i][j];
		}


	}


	t1=(n->a[x+1][y]);
	(r->a[x+1][y])=0;
	(r->a[x][y])=t1;
	(r->sd)=(n->sd)+1;
	(r->hd)=heuristic(r);
	(r->tot)=(r->sd)+(r->hd);
	}
}
return r;
}


struct node * left(struct node * n)
{

struct node * r;
int i,j,y,x=0;
int t1;
for(i=0;i<3;i++)
	{

	for(j=0;j<3;j++)
		{
		if((n->a[i][j])==0)
			{
			x=i;
			y=j;

			}
		}


	}
if(y==0)
	return NULL;
else
{
r=(struct node *) malloc(sizeof(struct node));
if(r==NULL)
	{
	printf("failure to get memory, press any button to quit")  ;
	getche();
	exit(-1);
	}
else
	{
	for(i=0;i<3;i++)
	{

	for(j=0;j<3;j++)
		{
		r->a[i][j]=n->a[i][j];
		}


	}
	
	
	t1=(r->a[x][y-1]);
	(r->a[x][y-1])=0;
	(r->a[x][y])=t1;
	(r->sd)=(n->sd)+1;
	(r->hd)=heuristic(r);
	(r->tot)=(r->sd)+(r->hd);
	}
}
return r;
}

struct node * right(struct node * n)
{

struct node * r;
int i,j,y,x=0;
int t1;
for(i=0;i<3;i++)
	{

	for(j=0;j<3;j++)
		{
		if((n->a[i][j])==0)
			{
			x=i;
			y=j;

			}
		}


	}
if(y==2)
	return NULL;
else
{
r=(struct node * ) malloc(sizeof(struct node));
if(r==NULL)
	{
	printf("failure to get memory, press any button to quit")  ;
	getche();
	exit(-1);
	}
else
	{
	for(i=0;i<3;i++)
	{

	for(j=0;j<3;j++)
		{
		r->a[i][j]=n->a[i][j];
		}


	}

	t1=(r->a[x][y+1]);
	(r->a[x][y+1])=0;
	(r->a[x][y])=t1;
	(r->sd)=(n->sd)+1;
	(r->hd)=heuristic(r);
	(r->tot)=(r->sd)+(r->hd);
	}
}
return r;
}

void insert(struct node * s)
{
struct node * curr=f;
struct node * t;
while(((curr->next)!=NULL)&&(((curr->next)->tot)<(s->tot)))
	curr=curr->next;
t=curr->next;
curr->next=s;
s->next=t;
return;
}

int heuristic(struct node * n)
{
int x=0;
if((n->a[0][0])!=1)
	x++;
if((n->a[0][1])!=2)
	x++;
if((n->a[0][2])!=3)
	x++;
if((n->a[1][0])!=8)
	x++;
if((n->a[1][1])!=0)
	x++;
if((n->a[1][2])!=4)
	x++;
if((n->a[2][0])!=7)
	x++;
if((n->a[2][1])!=6)
	x++;
if((n->a[2][2])!=5)
	x++;
return x;
}