Question

Major Homework #2
Implement a C program major_hw2.c to solve the 15-puzzle problem using the A* search
algorithm. Please include pictures that the code runs and shows the different states as it reaches goal state please.
1. Objectives
• To gain more experience on using pointers and linked lists in C programs.
• To learn how to solve problems using state space search and A* search algorithm.
2. Background
A* search and 15-puzzle problem have been introduced in the class. For more information, please
read the wiki page of 15-puzzle problem at https://en.wikipedia.org/wiki/15_puzzle, and the wiki
page of A* search at https://en.wikipedia.org/wiki/A*_search_algorithm.
Solving a 15-puzzle problem needs to keep swapping the locations of the blank tile and a tile
adjacent to it (i.e., above/below it or to the left/right of the blank title), such that in the end all the
tiles are moved from their initial locations to their goal locations.
In the assignment, the blank title is labeled with number 0, and other titles are labeled with nonzero numbers from 1~15. The goal locations are as shown below, and the initial locations are
provided through program arguments by listing tile indexes in a row-major order. Refer to page
https://en.wikipedia.org/wiki/Row-_and_column-major_order, if you need to understand what
row-major order is.
For example, the command
./major_hw2 2 3 0 4 1 6 7 8 5 9 10 12 13 14 11 15
is to solve a 15-puzzle problem, in which the tiles are initially placed as follows, and are to be
moved to their goal locations shown above:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 0

The execution of the program will print out the state transitions from the initial state to the goal
state as a solution. For the above 15-puzzle problem, the following states will be printed out on
the screen. Note that, to save space, this document uses two columns to show the output, with the
column on the left followed by the column on the right and the line separating the two columns.
Your program only needs to print the states in one column, and does not need to show the line.
Path (lengh=9):
2 3 0 4
1 6 7 8
5 9 10 12
13 14 11 15
2 0 3 4
1 6 7 8
5 9 10 12
13 14 11 15
0 2 3 4
1 6 7 8
5 9 10 12
13 14 11 15
1 2 3 4
0 6 7 8
5 9 10 12
13 14 11 15
1 2 3 4
5 6 7 8
0 9 10 12
13 14 11 15
1 2 3 4
5 6 7 8
9 0 10 12
13 14 11 15
1 2 3 4
5 6 7 8
9 10 0 12
13 14 11 15
1 2 3 4
5 6 7 8
9 10 11 12
13 14 0 15
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 0
You may use the attached program GenGemPuzzle.c to generate initial states. The program starts
from the goal state (i.e., all the tiles are at their goal locations) and moves tiles randomly. It takes
an integer as its argument (example shown below), which is the number of moves it makes before
it finishes.
./GenGemPuzzle 20
2 3 0 4
1 6 7 8
5 9 10 12
13 14 11 15

Usually, with a larger the argument, the program can generate an initial state that is more different
is from the goal state; thus, when solving the problem, more moves are needed to move the tiles
to their goal locations, and your program needs more time to finish.
3. Other Requirements and Instructions
• Name the program major_hw2.c. Do not include any information that can link the program
to yourself (e.g., your first name, last name, UCID, or NJIT ID). Submit your program to
the CLASS system. A submission that fails to follow this rule will be charged 20 points.
• The command line to run the program should have 16 unique integers between 0 and 15
(including 0 and 15) as tile indexes. The tile indexes are separated by spaces.
./major_hw2 index0 index1 … index15
• Your program needs to print out a sequence of states showing the movement the tiles, or
text "no solution" if a solution cannot be found.
• If your program cannot print the state transitions in correct order (i.e., from the initial state
to the goal state), it can still get partial credits if it can print the state transitions in reverse
order (i.e., from the goal state to the initial state). But your program needs to print out an
message as a note:
NOTE: the station transitions are in reverse order.

• You can improve the skeleton program attached with the assignment.
• The program will use intensively pointers and linked lists. Though you may print messages
to stderr to help you trace its execution, gdb will be more helpful in debugging. For the
usage of gdb, refer to this tutorial: http://beej.us/guide/bggdb/.
Grading:
Test 1. The program does not include the information that can identify the student; and if the
program can execute after compilation, the information printed out by the execution does not
include the information that can identify the student. --- 20 points.
Examine the program and check the execution outputs in tests 2~4. The program receives
• 0 point if such information is found
• 20 points if such information is not found.
Test 2. The program can solve the problem if the initial state matches the goal state. It must run
with the following command and print out the goal state as the solution within 1 minute. --- 20
points
./major_hw2 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0
Run the program with the arguments above and check the execution outputs. The program receives

• 0 point if the program cannot run
• 0 point if the program crashes or only prints out error messages without solution
• 10 points if the program finishes normally but it fails to print out a correct solution
within 1 minute
• 20 points if the program prints out the correct solution within 1 minute
3. Your program can solve a simple 15-puzzle problem. The initial state will be generated by the
class grader using command GenGemPuzzle 4. Your program must finish within 1 minute
without any errors and print out the states, including the initial states, intermediate states generated
by moving tiles, and the goal state: ---- 30 points
Run GenGemPuzzle 4 to generate an initial state, run the program with the arguments
corresponding to the initial state, and then check the execution outputs. The program receives
• 0 point if the program cannot run
• 0 point if fails to print out a correct solution within 1 minute
• 20 points if the program prints out the correct solution in reverse order within 1
minute
• 30 points if the program prints out the correct solution in correct order within 1
minute
4. Your program can solve a hard 15-puzzle problem. The initial state will be generated using
command GenGemPuzzle 40. Your program must finish within 20 minutes (long enough for
solving such a problem if your program is properly designed) and print out the states, including
the initial states, intermediate states generated by moving tiles, and the goal state: ---- 30 points
Run GenGemPuzzle 40 to generate an initial state, run the program with the arguments
corresponding to the initial state, and then check the execution outputs. The program receives
• 0 point if the program cannot run
• 0 point if fails to print out a correct solution within 20 minutes
• 20 points if the program prints out the correct solution in reverse order within 20
minutes
• 30 points if the program prints out the correct solution in correct order within 20
minutes

Skeleton Code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <pthread.h>

#define N 4
#define NxN (N*N)
#define TRUE 1
#define FALSE 0

struct 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];
struct node *start,*goal;
struct node *open = NULL, *closed = NULL;
struct node *succ_nodes[4];
pthread_barrier_t barrier_before_filtering, barrier_after_filtering;
int finish=0, multithread=0;

void print_a_node(struct node *pnode) {
        int i,j;
        for (i=0;i<N;i++) {
                for (j=0;j<N;j++) 
                        printf("%2d ", pnode->tiles[i][j]);
                printf("\n");
        }
        printf("\n");
}

struct node *initialize(int argc, char **argv){
        int i,j,k,index, tile;
        struct node *pnode;

        pnode=(struct node *) malloc(sizeof(struct node));
        index = 1;
        for (j=0;j<N;j++)
                for (k=0;k<N;k++) {
                        tile=atoi(argv[index++]);
                        pnode->tiles[j][k]=tile;
                        if(tile==0) {
                                pnode->zero_row=j;
                                pnode->zero_column=k;
                        }
                }
        pnode->f=0;
        pnode->g=0;
        pnode->h=0;
        pnode->next=NULL;
        pnode->parent=NULL;
        start=pnode;
        printf("initial state\n");
        print_a_node(start);

        pnode=(struct node *) malloc(sizeof(struct node));
        goal_rows[0]=3;
        goal_columns[0]=3;

        for(index=1; index<NxN; index++){
                j=(index-1)/N;
                k=(index-1)%N;
                goal_rows[index]=j;
                goal_columns[index]=k;
                pnode->tiles[j][k]=index;
        }
        pnode->tiles[N-1][N-1]=0;          /* empty tile=0 */
        pnode->f=0;
        pnode->g=0;
        pnode->h=0;
        pnode->next=NULL;
        goal=pnode; 
        printf("goal state\n");
        print_a_node(goal);

        return start;
}

/* merge unrepeated nodes into open list after filtering */
void merge_to_open() { 
}

/*swap two tiles in a node*/
void swap(int row1,int column1,int row2,int column2, struct node * pnode){
}

/*update the f,g,h function values for a node */
void update_fgh(struct node *pnode){
}

/* 0 goes down by a row */
void move_down(struct node * pnode){
}

/* 0 goes right by a column */
void move_right(struct node * pnode){
}

/* 0 goes up by a row */
void move_up(struct node * pnode){
}

/* 0 goes left by a column */
void move_left(struct node * pnode){
}

/* expand a node, get its children nodes, and organize the children nodes using
 * array succ_nodes.
 */
void expand(struct node *selected) {
}

int nodes_same(struct node *a,struct node *b) {
        int flg=FALSE;
        if (memcmp(a->tiles, b->tiles, sizeof(int)*NxN) == 0)
                flg=TRUE;
        return flg;
}

/* Filtering. Some nodes in succ_nodes may already be included in either open 
 * or closed list. Remove them. It is important to reduce execution time.
 * This function checks the (i)th node in succ_nodes array. You must call this
 & function in a loop to check all the nodes in succ_nodes.
 */ 
void filter(int i, struct node *pnode_list){ 
}

void *filter_threads(void *id){
        int *myid = (int *)id;
        printf("thread %d\n",*myid); 
        while(1){
        ... /* barrier sync */
        ... /* check the found flag, and exit when found is set */
                filter(*myid, open);
                filter(*myid, closed);
        ... /* barrier sync */
        }
}

int main(int argc,char **argv) {
        int iter,cnt;
        struct node *copen, *cp, *solution_path;
        pthread_t thread[N-1];
        int ret, i, pathlen=0, index[N-1];

        solution_path=NULL;
        ... /* set multithread flag based on argv[1] */
        start=initialize(argc-1,argv+1);        /* init initial and goal states */
        open=start; 
        if(multithread){
                ... /* initialize barriers */
                ... /* create threads */
        }

        iter=0; 
        while (open!=NULL) {    /* Termination cond with a solution is tested in expand. */
                copen=open;
                open=open->next;  /* get the first node from open to expand */
                if(nodes_same(copen,goal)){ /* goal is found */
                        if(multithread){
                                finish=1;
                                /* barrier sync to allow other threads to return 
                                 * from their barrier calls and exit*/
                                ...
                        }
                        do{ /* trace back and add the nodes on the path to a list */
                                copen->next=solution_path;
                                solution_path=copen;
                                copen=copen->parent;
                                pathlen++;
                        } while(copen!=NULL);
                        printf("Path (lengh=%d):\n", pathlen); 
                        copen=solution_path;
                        ... /* print out the nodes on the list */
                        break;
                }
                expand(copen);       /* Find new successors */
                if(multithread){
                        ... /* barrier sync */
                        filter(0,open);
                        filter(0,closed);
                        ... /* barrier sync */
                }
                else{
                        for(i=0;i<4;i++){
                                filter(i,open);
                                filter(i,closed);
                        }
                }
                merge_to_open(); /* New open list */
                copen->next=closed;
                closed=copen;           /* New closed */
                /* print out something so that you know your 
                 * program is still making progress 
                 */
                iter++;
                if(iter %1000 == 0)
                        printf("iter %d\n", iter);
        }

        if(multithread){
                ...  /* destroy barriers */
                ...  /* join threads */
        }
        return 0;
} /* end of main */

Answer 1

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <pthread.h>

#define N 4
#define NxN (N*N)
#define TRUE 1
#define FALSE 0

struct node {
        int tiles[N][N];
        int f, g, h;
        short zero_row, zero_column;
        struct node *next;
        struct node *parent;
};

int goal_rows[NxN];
int goal_columns[NxN];
struct node *start,*goal;
struct node *open = NULL, *closed = NULL;
struct node *succ_nodes[4];
pthread_barrier_t barrier_before_filtering, barrier_after_filtering;
int finish=0, multithread=0;

void print_a_node(struct node *pnode) {
        int i,j;
        for (i=0;i<N;i++) {
                for (j=0;j<N;j++) 
                        printf("%2d ", pnode->tiles[i][j]);
                printf("\n");
        }
        printf("\n");
}

struct node *initialize(int argc, char **argv){
        int i,j,k,index, tile;
        struct node *pnode;

        pnode=(struct node *) malloc(sizeof(struct node));
        index = 1;
        for (j=0;j<N;j++)
                for (k=0;k<N;k++) {
                        tile=atoi(argv[index++]);
                        pnode->tiles[j][k]=tile;
                        if(tile==0) {
                                pnode->zero_row=j;
                                pnode->zero_column=k;
                        }
                }
        pnode->f=0;
        pnode->g=0;
        pnode->h=0;
        pnode->next=NULL;
        pnode->parent=NULL;
        start=pnode;
        printf("initial state\n");
        print_a_node(start);

        pnode=(struct node *) malloc(sizeof(struct node));
        goal_rows[0]=3;
        goal_columns[0]=3;

        for(index=1; index<NxN; index++){
                j=(index-1)/N;
                k=(index-1)%N;
                goal_rows[index]=j;
                goal_columns[index]=k;
                pnode->tiles[j][k]=index;
        }
        pnode->tiles[N-1][N-1]=0;
        pnode->f=0;
        pnode->g=0;
        pnode->h=0;
        pnode->next=NULL;
        goal=pnode; 
        printf("goal state\n");
        print_a_node(goal);

        return start;
}

void merge_to_open() {
    //put succ_nodes into open based on open priority
    for(int i = 0; i < N; i++){
        if(succ_nodes[i] == NULL){
            continue;
        }
        //Create a new node to insert, as succ_nodes will soon be cleared for next iteration
        struct node *toInsert = (struct node *) malloc(sizeof(struct node));
        memcpy(toInsert->tiles, succ_nodes[i]->tiles, NxN*sizeof(int));
        toInsert->f = succ_nodes[i]->f;
        toInsert->g = succ_nodes[i]->g;
        toInsert->h = succ_nodes[i]->h;
        toInsert->zero_row = succ_nodes[i]->zero_row;
        toInsert->zero_column = succ_nodes[i]->zero_column;
        toInsert->parent = succ_nodes[i]->parent;

        if (open == NULL)
        {
            open = toInsert;
            continue;
        }

        struct node *temp = open;

        int hasInserted = FALSE;

        while(temp != NULL && temp->next != NULL){
            if(toInsert->f < temp->next->f){
                toInsert->next = temp->next;
                temp->next = toInsert;
                hasInserted = TRUE;
                break;
            }
        temp = temp->next;
        }

        //temp should be either the last node, or the node where toInsert should be inserted
        if(hasInserted == FALSE){
            temp->next = toInsert;
        }

    }

}

/*swap two tiles in a node*/
void swap(int row1,int column1,int row2,int column2, struct node * pnode){
    //swap WITHOUT A TEMP VARIABLE YEAH IM THAT COOL
    pnode->tiles[row1][column1] += pnode->tiles[row2][column2];
    pnode->tiles[row2][column2] = pnode->tiles[row1][column1] - pnode->tiles[row2][column2];
    pnode->tiles[row1][column1] -= pnode->tiles[row2][column2];
}

//used for h2
int manhattanDist(int entry, int row, int col){
    //ignore 0
    if(entry == 0){
        return 0;
    }
    //find entry in goal
    for(int i = 0; i < NxN; i++){
        for(int j = 0; j < NxN; j++){
            if(goal->tiles[i][j] == entry){
                //Goal destination is i, j
                return abs(row - i) + abs(col - j);
            }
        }
    }
}

//used to decide between h1 and h2
int max(int a, int b){
    if(a > b){
        return a;
    }else{
        return b;
    }
}

/*update the f,g,h function values for a node */
void update_fgh(struct node *pnode){
    //g is amount of steps from top
    if(pnode->parent != NULL){
        pnode->g = pnode->parent->g + 1;
    }else{
        pnode->g = 1;
    }

    //h is the max of h1 or h2
    int h1 = 0, h2 = 0;
    int i, j;
    int correct = 0;
    //h1 is number of misplaced tiles, h2 is how far the tile is from desired location
    for(i = 0; i < NxN; i++){
        for(j = 0; i < NxN; i++){
            correct++;
            if(pnode->tiles[j][i] != correct ){
                h1++;
            }
            h2 += manhattanDist(pnode->tiles[j][i], j, i);
        }
    }
    pnode->h = max(h1, h2);

    //f is g + h
    pnode->f = pnode->g + pnode->h;
}



/* 0 goes down by a row */
void move_down(struct node * pnode){
    if(pnode->zero_row+1 < N){
        swap(pnode->zero_row, pnode->zero_column, pnode->zero_row+1, pnode->zero_column, pnode);
        pnode->zero_row++;
    }else{
        pnode = NULL;
    }
}

/* 0 goes right by a column */
void move_right(struct node * pnode){
    if(pnode->zero_column+1 < N){
        swap(pnode->zero_row, pnode->zero_column, pnode->zero_row, pnode->zero_column+1, pnode);
        pnode->zero_column++;
    }else{
        pnode = NULL;
    }
}

/* 0 goes up by a row */
void move_up(struct node * pnode){
    if(pnode->zero_row-1 > -1){
        swap(pnode->zero_row, pnode->zero_column, pnode->zero_row-1, pnode->zero_column, pnode);
        pnode->zero_row--;
    }else{
        pnode = NULL;
    }

}

/* 0 goes left by a column */
void move_left(struct node * pnode){
    if(pnode->zero_column-1 > -1) {
        swap(pnode->zero_row, pnode->zero_column, pnode->zero_row, pnode->zero_column - 1, pnode);
        pnode->zero_column--;
    }else{
        pnode = NULL;
    }
}

/* expand a node, get its children nodes, and organize the children nodes using
 * array succ_nodes.
 */
void expand(struct node *selected) {
    for(int i = 0; i < N; i++){
        succ_nodes[i] = (struct node *) malloc(sizeof(struct node));
        memcpy(succ_nodes[i]->tiles, selected->tiles, NxN*sizeof(int));
        succ_nodes[i]->zero_row = selected->zero_row;
        succ_nodes[i]->zero_column = selected->zero_column;
        succ_nodes[i]->parent = selected;

    }

    move_down(succ_nodes[0]);
    move_right(succ_nodes[1]);
    move_up(succ_nodes[2]);
    move_left(succ_nodes[3]);

    for(int i = 0; i < N; i++){
        update_fgh(succ_nodes[i]);
    }
}

int nodes_same(struct node *a,struct node *b) {
        int flg=FALSE;
        if (memcmp(a->tiles, b->tiles, sizeof(int)*NxN) == 0)
                flg=TRUE;
        return flg;
}

void filter(int i, struct node *pnode_list){
    if(pnode_list == NULL || succ_nodes[i] == NULL){
        return;
    }
    struct node *temp = pnode_list;
    while(temp != NULL){
        if(nodes_same(succ_nodes[i], temp)){
            succ_nodes[i] = NULL;
            return;
        }
        temp = temp->next;
    }
}

void *filter_threads(void *id){
        int *myid = (int *)id;
        while(1){
        pthread_barrier_wait(&barrier_before_filtering);
        if(finish == TRUE){
            pthread_exit(NULL);
        }
                filter(*myid, open);
                filter(*myid, closed);
        pthread_barrier_wait(&barrier_after_filtering);

    }
}

int main(int argc,char **argv) {
        int iter,cnt;
        struct node *copen, *cp, *solution_path;
        pthread_t thread[N-1];
        int ret, i, pathlen=0, index[N-1];

        solution_path=NULL;
        if(strcmp(argv[1], "-s") == 0){
        multithread = 0;
        }else if(strcmp(argv[1], "-m") == 0){
        multithread = 1;
        }else{
        printf("incorrect threading option, first argument must be (-s/-m), not %s", argv[1]);
        return 0;
        }
        start=initialize(argc-1,argv+1);
        open=start; 
        if(multithread){
        pthread_barrier_init(&barrier_before_filtering,NULL,N);
        pthread_barrier_init(&barrier_after_filtering,NULL,N);
        int id[N-1];
        for(i = 0; i < N-1; i++){
            id[i] = i+1;
            pthread_create(&thread[i], NULL, filter_threads, &id[i]);
            }
        }

        iter=0; 
        while (open!=NULL) {
                copen=open;
                open=open->next;
                if(nodes_same(copen,goal)){
                    /* goal is found */
                        if(multithread){
                finish=1;
                pthread_barrier_wait(&barrier_before_filtering);
            }
                        do{
                                copen->next=solution_path;
                                solution_path=copen;
                                copen=copen->parent;
                                pathlen++;
                        } while(copen!=NULL);
                        printf("Path (lengh=%d):\n", pathlen); 
            /* print out the nodes on the list */
            do{
                print_a_node(solution_path);
                solution_path = solution_path->next;
            }while(solution_path != NULL);
                        break;
                }
                expand(copen);
                if(multithread){
                        /* barrier sync */
            pthread_barrier_wait(&barrier_before_filtering);
            filter(0,open);
                        filter(0,closed);
            pthread_barrier_wait(&barrier_after_filtering);
            /* barrier sync */
                }
                else{
                        for(i=0;i<4;i++){
                                filter(i,open);
                                filter(i,closed);
                        }
                }
                merge_to_open();
                copen->next=closed;
                closed=copen;

                iter++;
                if(iter %1000 == 0){
            printf("iter %d\n", iter);
                }

        }

        if(multithread){
        pthread_barrier_destroy(&barrier_before_filtering);
        pthread_barrier_destroy(&barrier_after_filtering);

        for(i = 0; i < N-1; i++) {
            pthread_join(thread[i], NULL);
        }

    }
        return 0;
}