Implement a C program to solve the 15-puzzle problem using the A* search algorithm.

In the assignment, solving a 15-puzzle problem needs to move the tiles to their goal locations, which are as shown below. The numbers 1~15 are indexes of the tiles, and 0 means blank tile. This state is the goal state.

Your program can solve the problem using a single thread or using 4 threads, depending on the first argument (argv[1]). The program uses a single thread if argv[1] is "-s", or 4 threads if argv[1] is "-m". The initial layout of the tiles is also provided in the command line as arguments by listing tile indexes in a row-major order.

For example, the command ./your_program -s 2 3 0 4 1 6 7 8 5 9 10 12 13 14 11 15 is to use one thread to solve the 15-puzzle problem, in which the tiles are initially placed as follows, and are to be moved to their goal locations

The command ./your_program -m 2 3 0 4 1 6 7 8 5 9 10 12 13 14 11 15 is to solve the above problem using 4 threads.

Program needs to print out a sequence of states showing the movement the tiles, or text "no solution" if a solution cannot be found.

#include<stdio.h>

#include<conio.h>

int m=0,n=4;

int cal(int temp[10][10],int t[10][10])

{

               int i,j,m=0;

               for(i=0;i < n;i++)

                               for(j=0;j < n;j++)

                               {

                                               if(temp[i][j]!=t[i][j])

                                               m++;

                               }

               return m;

}

int check(int a[10][10],int t[10][10])

{

               int i,j,f=1;

               for(i=0;i < n;i++)

                               for(j=0;j < n;j++)

                                               if(a[i][j]!=t[i][j])

                                                               f=0;

               return f;

}

void main()

{

               int p,i,j,n=4,a[10][10],t[10][10],temp[10][10],r[10][10];

               int m=0,x=0,y=0,d=1000,dmin=0,l=0;

               clrscr();

               printf("\nEnter the matrix to be solved,space with zero :\n");

               for(i=0;i < n;i++)

                               for(j=0;j < n;j++)

                                               scanf("%d",&a[i][j]);

               printf("\nEnter the target matrix,space with zero :\n");

               for(i=0;i < n;i++)

                               for(j=0;j < n;j++)

                                               scanf("%d",&t[i][j]);

               printf("\nEntered Matrix is :\n");

               for(i=0;i < n;i++)

               {

                               for(j=0;j < n;j++)

                                               printf("%d\t",a[i][j]);

                               printf("\n");

               }

               printf("\nTarget Matrix is :\n");

               for(i=0;i < n;i++)

               {

                               for(j=0;j < n;j++)

                                               printf("%d\t",t[i][j]);

                               printf("\n");

               }

               while(!(check(a,t)))

               {

                               l++;

                               d=1000;

                               for(i=0;i < n;i++)

                                               for(j=0;j < n;j++)

                                               {

                                                               if(a[i][j]==0)

                                                               {

                                                                               x=i;

                                                                               y=j;

                                                               }

                                               }

                               //To move upwards

                               for(i=0;i < n;i++)

                                               for(j=0;j < n;j++)

                                                               temp[i][j]=a[i][j];

                               if(x!=0)

                               {

                                               p=temp[x][y];

                                               temp[x][y]=temp[x-1][y];

                                               temp[x-1][y]=p;

                               }

                               m=cal(temp,t);

                               dmin=l+m;

                               if(dmin < d)

                               {

                                               d=dmin;

                                               for(i=0;i < n;i++)

                                                               for(j=0;j < n;j++)

                                                                               r[i][j]=temp[i][j];

                               }

                               //To move downwards

                               for(i=0;i < n;i++)

                                               for(j=0;j < n;j++)

                                                               temp[i][j]=a[i][j];

                               if(x!=n-1)

                               {

                                               p=temp[x][y];

                                               temp[x][y]=temp[x+1][y];

                                               temp[x+1][y]=p;

                               }

                               m=cal(temp,t);

                               dmin=l+m;

                               if(dmin < d)

                               {

                                               d=dmin;

                                               for(i=0;i < n;i++)

                                                               for(j=0;j < n;j++)

                                                                               r[i][j]=temp[i][j];

                               }

                               //To move right side

                               for(i=0;i < n;i++)

                                               for(j=0;j < n;j++)

                                                               temp[i][j]=a[i][j];

                               if(y!=n-1)

                               {

                                               p=temp[x][y];

                                               temp[x][y]=temp[x][y+1];

                                               temp[x][y+1]=p;

                               }

                               m=cal(temp,t);

                               dmin=l+m;

                               if(dmin < d)

                               {

                                               d=dmin;

                                               for(i=0;i < n;i++)

                                                               for(j=0;j < n;j++)

                                                                               r[i][j]=temp[i][j];

                               }

                               //To move left

                               for(i=0;i < n;i++)

                                               for(j=0;j < n;j++)

                                                               temp[i][j]=a[i][j];

                               if(y!=0)

                               {

                                               p=temp[x][y];

                                               temp[x][y]=temp[x][y-1];

                                               temp[x][y-1]=p;

                               }

                               m=cal(temp,t);

                               dmin=l+m;

                               if(dmin < d)

                               {

                                               d=dmin;

                                               for(i=0;i < n;i++)

                                                               for(j=0;j < n;j++)

                                                                               r[i][j]=temp[i][j];

                               }

                               printf("\nCalculated Intermediate Matrix Value :\n");

                               for(i=0;i < n;i++)

                               {

                                               for(j=0;j < n;j++)

                                               printf("%d\t",r[i][j]);

                                               printf("\n");

                               }

                               for(i=0;i < n;i++)

                                               for(j=0;j < n;j++)

                                               {

                                               a[i][j]=r[i][j];

                                               temp[i][j]=0;

                                               }

                               printf("Minimum cost : %d\n",d);

               }

               getch();

}

Explanation:

no backup memory