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 */
char valuestring[23];
};
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 set_value_string(struct node * pnode){
int i,j;
char val[2];
for (i=0;i<4;i++) {
for (j=0;j<4;j++)
{
sprintf(val, "%d", pnode->tiles[i][j]);
strcat(pnode->valuestring, val);
}
}
}
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;
set_value_string(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;
set_value_string(pnode); // NEW LINE HERE
printf("goal state\n");
print_a_node(goal);
return start;
}
/* merge unrepeated nodes into open list after filtering */
void merge_to_open()
{
int j;
for (int i = 0; i < 4; i++)
{
if (open == NULL)
{
for (j = 0; j < 4; j++)
{
if (succ_nodes[j] != NULL)
{
open = succ_nodes[j];
break;
}
}
}
if (succ_nodes[i] != NULL && i != j)
{
struct node* start = open;
// Special Case: The head of list has lesser
// priority than new node. So insert new
// node before head node and change head node.
if (open->f > succ_nodes[i]->f) {
// Insert New Node before head
succ_nodes[i]->next = open;
open = succ_nodes[i];
}
else {
// Traverse the list and find a
// position to insert new node
while (start->next != NULL &&
start->next->f < succ_nodes[i]->f) {
start = start->next;
}
// Either at the ends of the list
// or at required position
succ_nodes[i]->next = start->next;
start->next = succ_nodes[i];
}
}
}
}
/*update the f,g,h function values for a node */
void update_fgh(struct node *pnode){
pnode->g = pnode->parent->g + 1;
pnode->h = 0;
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 4; j++)
{
if (pnode->tiles[i][j] != 0)
{
int x = (pnode->tiles[i][j] - 1) / 4;
int y = (pnode->tiles[i][j] - 1) % 4;
int dx = i - x;
int dy = j - y;
pnode->h += abs(dx) + abs(dy);
}
}
}
pnode->f = pnode->g + pnode->h;
}
/* 0 goes down by a row */
void move_down(struct node * pnode, struct node * cnode){
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 4; j++)
{
if (i == pnode->zero_row + 1 && j == pnode->zero_column)
{
/* Swap tiles */
cnode->tiles[pnode->zero_row][pnode->zero_column] = pnode->tiles[i][j];
cnode->tiles[i][j] = 0;
cnode->zero_row = i;
cnode->zero_column = j;
}
else
{
if (i == pnode->zero_row && j == pnode->zero_column)
continue;
cnode->tiles[i][j] = pnode->tiles[i][j];
}
}
}
}
/* 0 goes right by a column */
void move_right(struct node * pnode, struct node * cnode){
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 4; j++)
{
if (i == pnode->zero_row && j == pnode->zero_column + 1)
{
/* Swap tiles */
cnode->tiles[pnode->zero_row][pnode->zero_column] = pnode->tiles[i][j];
cnode->tiles[i][j] = 0;
cnode->zero_row = i;
cnode->zero_column = j;
}
else
{
if (i == pnode->zero_row && j == pnode->zero_column)
continue;
cnode->tiles[i][j] = pnode->tiles[i][j];
}
}
}
}
/* 0 goes up by a row */
void move_up(struct node * pnode, struct node * cnode){
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 4; j++)
{
if (i == pnode->zero_row - 1 && j == pnode->zero_column)
{
/* Swap tiles */
cnode->tiles[pnode->zero_row][pnode->zero_column] = pnode->tiles[i][j];
cnode->tiles[i][j] = 0;
cnode->zero_row = i;
cnode->zero_column = j;
}
else
{
if (i == pnode->zero_row && j == pnode->zero_column)
continue;
cnode->tiles[i][j] = pnode->tiles[i][j];
}
}
}
}
/* 0 goes left by a column */
void move_left(struct node * pnode, struct node * cnode){
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 4; j++)
{
if (i == pnode->zero_row && j == pnode->zero_column - 1)
{
/* Swap tiles */
cnode->tiles[pnode->zero_row][pnode->zero_column] = pnode->tiles[i][j];
cnode->tiles[i][j] = 0;
cnode->zero_row = i;
cnode->zero_column = j;
}
else
{
if (i == pnode->zero_row && j == pnode->zero_column)
continue;
cnode->tiles[i][j] = pnode->tiles[i][j];
}
}
}
}
/* Move children nodes into succ_nodes */
void expand(struct node *selected) {
// Create a new node
printf("Expanding:\n");
print_a_node(selected);
int i = 0;
if (selected->zero_row > 0)
{
succ_nodes[i] = (struct node *)malloc(sizeof(struct node));
succ_nodes[i]->parent = selected;
succ_nodes[i]->next = NULL;
move_up(selected, succ_nodes[i]);
printf("Moving up\n");
update_fgh(succ_nodes[i]);
set_value_string(succ_nodes[i]); // NEW LINE HERE
printf("Child %d\n", i + 1);
print_a_node(succ_nodes[i]);
i++;
}
if (selected->zero_column > 0)
{
// Move left
printf("Moving left\n");
succ_nodes[i] = (struct node *)malloc(sizeof(struct node));
succ_nodes[i]->parent = selected;
succ_nodes[i]->next = NULL;
move_left(selected, succ_nodes[i]);
update_fgh(succ_nodes[i]);
set_value_string(succ_nodes[i]); // NEW LINE HERE
printf("Child %d\n", i + 1);
print_a_node(succ_nodes[i]);
i++;
}
if (selected->zero_row < N - 1)
{
// move down
printf("Moving down\n");
succ_nodes[i] = (struct node *)malloc(sizeof(struct node));
succ_nodes[i]->parent = selected;
succ_nodes[i]->next = NULL;
move_down(selected, succ_nodes[i]);
update_fgh(succ_nodes[i]);
set_value_string(succ_nodes[i]); // NEW LINE HERE
printf("Child %d\n", i + 1);
print_a_node(succ_nodes[i]);
i++;
}
if (selected->zero_column < N - 1)
{
// move_right
printf("Moving right\n");
succ_nodes[i] = (struct node *)malloc(sizeof(struct node));
succ_nodes[i]->parent = selected;
succ_nodes[i]->next = NULL;
move_right(selected, succ_nodes[i]);
update_fgh(succ_nodes[i]);
set_value_string(succ_nodes[i]); // NEW LINE HERE
printf("Child %d\n", i + 1);
print_a_node(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;
}
/* Filtering. */
void filter(int i, struct node *pnode_list){
// Loop through the list
struct node* cur = pnode_list;
while (cur && succ_nodes[i])
{
if (strcmp(cur->valuestring, succ_nodes[i]->valuestring) == 0)
succ_nodes[i] = NULL;
cur = cur->next;
}
}
int main(int argc,char **argv) {
int cnt;
struct node *copen, *cp, *solution_path;
pthread_t thread[N-1];
int ret, i, pathlen=0, index[N-1];
solution_path=NULL;
start=initialize(argc-1,argv+1); /* init initial and goal states */
open=start;
if(multithread){
/* initialize barriers */
/* create threads */
}
int loopcnt = 0;
while (open!=NULL) { /* Termination cond with a solution is tested in expand. */
printf("\nLoop %d\n", loopcnt + 1);
loopcnt++;
copen=open;
open=open->next; /* get the first node from open to expand */
if (open == NULL) printf("Open is empty\n");
if (closed == NULL) printf("Closed is empty\n");
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 */
struct node* cur = solution_path;
while (cur)
{
print_a_node(cur);
cur = cur->next;
}
break;
}
if (closed == NULL) printf("Closed is empty\n");
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 */
// Print the open list
struct node* cur = open;
printf("Open list\n");
while (cur)
{
print_a_node(cur);
cur = cur->next;
}
copen->next=closed;
closed=copen; /* New closed */
struct node* cur1 = closed;
printf("Closed list\n");
while (cur1)
{
print_a_node(cur1);
cur1 = cur1->next;
}
}
if(multithread){
/* destroy barriers */
/* join threads */
}
return 0;
}
Tested it with ./a.out -s 5 1 2 4 7 6 8 0 9 15 3 11 13 10 14 12