I have a code that is supposed to show the paths in solving a 15-puzzle after showing the initial state and goal state. However, while it does show the initial state and goal state, it gives a segmentation fault instead of printing out the path.
Here is the code below:
#include <stdio.h>
#include <stdlib.h>
#include <string.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];
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(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 staten");
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 staten");
print_a_node(goal);
return start;
}
void merge_to_open() {
for (int i = 0; i < N; i++) {
if (succ_nodes[i] == NULL) {
continue;
}
struct node *insert_node = (struct node *) malloc(sizeof(struct node));
memcpy(insert_node->tiles, succ_nodes[i]->tiles, NxN*sizeof(int));
insert_node->f = succ_nodes[i]->f;
insert_node->g = succ_nodes[i]->g;
insert_node->h = succ_nodes[i]->h;
insert_node->zero_row = succ_nodes[i]->zero_row;
insert_node->zero_column = succ_nodes[i]->zero_column;
insert_node->parent = succ_nodes[i]->parent;
if (open == NULL) {
open = insert_node;
continue;
}
struct node *temp = open;
int status = FALSE;
while (temp != NULL && temp->next != NULL) {
if (insert_node->f < temp->next->f) {
insert_node->next = temp->next;
temp->next = insert_node;
status = TRUE;
break;
}
temp = temp->next;
}
if (status == FALSE) {
temp->next = insert_node;
}
}
}
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;
}
int manhattan(int entry, int row, int column) {
for (int i = 0; i < NxN; i++) {
for (int j = 0; j < NxN; j++) {
if(goal->tiles[i][j] == entry) {
return abs(row - i) + abs(column - j);
}
}
}
}
void update_fgh(int t) {
struct node *pnode = succ_nodes[t];
if (pnode -> parent != NULL) {
pnode->g = pnode->parent->g + 1;
} else {
pnode->g = 1;
}
int misplaced = 0, distance = 0, correct = 0;
for (int i = 0; i < NxN; i++) {
for (int j = 0; j < NxN; j++) {
correct++;
if (pnode->tiles[j][i] != correct) {
misplaced++;
}
if (pnode->tiles[j][i] == 0) {
distance = 0;
} else {
distance = manhattan(pnode->tiles[j][i], j, i);
}
}
}
if (misplaced > distance) {
pnode->h = misplaced;
} else {
pnode->h = distance;
}
pnode->f = pnode->g + pnode->h;
}
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;
}
}
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;
}
}
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;
}
}
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;
}
}
void expand(struct node *selected) {
for (int i = 0; i < N; i++) {
succ_nodes[i] = NULL;
}
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(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){
struct node *pnode = succ_nodes[i];
struct node *temp = pnode_list;
while (temp != NULL) {
if (nodes_same(pnode, temp)) {
pnode = NULL;
return;
}
temp = temp->next;
}
}
int main(int argc,char **argv) {
int iter,cnt;
struct node *copen, *cp, *solution_path;
int ret, i, pathlen=0, index[N-1];
solution_path=NULL;
start=initialize(argv);
open=start;
iter=0;
while (open!=NULL) {
copen=open;
open=open->next;
if(nodes_same(copen,goal)){
do{
copen->next=solution_path;
solution_path=copen;
copen=copen->parent;
pathlen++;
} while(copen!=NULL);
printf("Path (length=%d):n", pathlen);
copen=solution_path;
break;
}
expand(copen);
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 %dn", iter);
}
return 0;
}
I used these command line arguments for running the program:
2 3 0 4 1 6 7 8 5 9 10 12 13 14 11 15
When I run a gdb debugging of the program, it prints out this (the value I passed as pnode in the program is succ_nodes[0]):
Program received signal SIGSEGV, Segmentation fault.
0x0000555555555940 in move_down (pnode=0x0) at problem1.c:172
172 if (pnode->zero_row + 1 < N) {
I assume this occurs for all the move functions with the pnode statements. Can you help me figure out a way to fix this?
3