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.

Question

07-03-2020
Computers and Technology

contestada

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.

Respuesta :

Otras preguntas

Cynthia was asked to subtract 0.223 from 0.54. Which of the following is the best estimate that Cynthia can make to check her answer? A. 0.4 − 0.2 B. 0.5 − 0.

what's the value of x?

Why does the rate of the reaction decrease over time? Why does the rate of the reaction decrease over time? Exothermic reactions lose heat which cools the react

Giovanni da Palestrina was a composer in the A. Romantic period. B. 20th Century. C. Renaissance period.

pls help!!!!!!!?!?!?!

Does (7, 8) make the equation y = x + 5 true?

Create a 1 month Personal Fitness Plan. It should include cardiovascular, endurance activities, muscle strength training, and stretching warm ups and cool downs

What is the meaning of the word sagacious in the following sentence? Mrs. Tomlinson, the sagacious teacher who convinced me to go to college, was the most insig

What is the value of a + C? Explain or show your reason

How many solutions does the system have? 5y = 15x - 40 y = 3x -8 A. Infinitely many solutions B. No solutions C. Exactly one solution

abdullahfarooqi abdullahfarooqi · Answer 1 · 2020-03-11T05:36:18+01:00

Answer:

#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: