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

1. Objectives

? To gain more experience on using pointers and linkedlists in C programs.

? To learn how to solve problems using state space searchand A* search algorithm.

? To learn how to accelerate processing using multiplethreads.

? To learn how to coordinate the progress of multiplethreads.

2. Background

A* search and 15-puzzle problem have been introduced in theclass. For more information, please read the wiki page of 15-puzzleproblem at https://en.wikipedia.org/wiki/15_puzzle, and the wikipage of A* search athttps://en.wikipedia.org/wiki/A*_search_algorithm.

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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

0

Your program can solve the problem using a single thread orusing 4 threads, depending on the first argument (argv[1]). Theprogram uses a single thread if argv[1] is "-s", or 4 threads ifargv[1] is "-m". The initial layout of the tiles is also providedin the command line as arguments by listing tile indexes in arow-major order (refer to this pagehttps://en.wikipedia.org/wiki/Row- _and_column-major_order if youneed to understand what is row-major order).

For example, the command

./your_program-s 2 3 0 4 1 6 7 8 5 9101213141115

is to use one thread to solve the 15-puzzle problem, inwhich the tiles are initially placed as follows, and are to bemoved to their goal locations shown above:

2	3	0	4
1	6	7	8
5	9	10	12
13	14	11	15

The command

./your_program-m 2 3 0 4 1 6 7 8 5 9101213141115

is to solve the above problem using 4 threads.

The execution of the program will print out the statetransitions from the initial state to the goal state as a solution.For the above 15-puzzle problem, the following states will beprinted out on the screen. Note that, to save space, this documentuses two columns to show the output, with the column on the leftfollowed by the column on the right and the line separating the twocolumns. Your program only needs to print the states in one column,and does not need to show the line.

Path (lengh=9):

2304 1678 5 9 10 12

13 14 11 15

2034 1678 5 9 10 12

13 14 11 15

0234 1678 5 9 10 12

13 14 11 15

1234 0678 5 9 10 12

13 14 11 15

5678

 0  9 10 1213 14 11 15

1234 5678 9 0 10 12

13 14 11 15

1234 5678 9 10 0 12

13 14 11 15

1234 5678 9 10 11 12

1314 015

1234 5678 9 10 11 12

131415 0

1234

./GenGemPuzzle 100

##Here is GenGem Puzzle

#include #include #include #include #define N 4#define NxN (N*N)#define TRUE 1#define FALSE 0struct node {        int tiles[N][N];        int f, g, h;        short zero_row, zero_column;   /* location (row and colum) of blank tile 0 */        struct node *next;        struct node *parent;          /* used to trace back the solution */};int goal_rows[NxN];int goal_columns[NxN];void swap(int row1,int column1,int row2,int column2, struct node * pnode){        int tile = pnode->tiles[row1][column1];        pnode->tiles[row1][column1]=pnode->tiles[row2][column2];        pnode->tiles[row2][column2]=tile;}/* 0 goes down by a row */void move_down(struct node * pnode){        swap(pnode->zero_row, pnode->zero_column, pnode->zero_row+1, pnode->zero_column, pnode);         pnode->zero_row++;}/* 0 goes right by a column */void move_right(struct node * pnode){        swap(pnode->zero_row, pnode->zero_column, pnode->zero_row, pnode->zero_column+1, pnode);         pnode->zero_column++;}/* 0 goes up by a row */void move_up(struct node * pnode){        swap(pnode->zero_row, pnode->zero_column, pnode->zero_row-1, pnode->zero_column, pnode);         pnode->zero_row--;}/* 0 goes left by a column */void move_left(struct node * pnode){        swap(pnode->zero_row, pnode->zero_column, pnode->zero_row, pnode->zero_column-1, pnode);         pnode->zero_column--;}void print_a_node(struct node *pnode, int format) {        int i,j;        for (i=0;itiles[i][j]);                if(format==0)                        printf("");        }        printf("");}int main(int argc,char **argv) {        int i,j,k,index,count;        struct node *pnode;        if(argc!=2 || sscanf(argv[1], "%d", &count)!=1) {                printf("%s #steps", argv[0]);                exit(1);        }        pnode=(struct node *) malloc(sizeof(struct node));        goal_rows[0]=3;        goal_columns[0]=3;        for(index=1; indextiles[j][k]=index;        }        pnode->tiles[N-1][N-1]=0;          /* empty tile=0 */        pnode->zero_row = N-1;        pnode->zero_column = N-1;        pnode->f=0;        pnode->g=0;        pnode->h=0;        pnode->next=NULL;        printf("goal state"); print_a_node(pnode, 0);        srand(time(NULL));        i=0;        do{                j = rand();                k = j % 4;                if( k == 0 && pnode->zero_row>0){                        move_up(pnode);                        i++;                }                if( k == 1 && pnode->zero_rowzero_column>0){                        move_left(pnode);                        i++;                }                if( k == 3 && pnode->zero_column
You may use the attached program GenGemPuzzle.c togenerate initial states. The program takes an integer as itsargument (example shown below), and moves tiles away from theirgoal locations. The argument is the number of moves. Thus, usually,the larger the argument is, the more difficult
PLEASE USE THREADS TO SOLVE IT! 

Answer rating: 100% (QA)

C program that solves the 15puzzle problem using the A search algorithm with m... View the full answer