# Thread: Linked List Infinite Loop

1. ## Linked List Infinite Loop

I'm implementing the A* algorithm in order to solve a 15 puzzle: 15 puzzle - Wikipedia

It works fine for simple puzzles with few steps but when doing more complex puzzles, the program enters an infinite loop when traversing the closed list (linked list of puzzle states that have been evaluated). I know that the last node in the list is not pointing to NULL as it should but I can't figure out why when it works for simpler puzzles.

Code:
```/* Function I'm using to remove child nodes that have already been put
into the open or closed list */
void filter(int i, struct node* pnode_list){
struct node* cur = pnode_list;
int cnt = 0;

while (cur && succ_nodes[i])
{
if (strcmp(cur->valuestring, succ_nodes[i]->valuestring) == 0)
succ_nodes[i] = NULL;
cur = cur->next;
}
}```
This is what I'm using in the main function to add the node I'm currently evaluating to the closed list
Code:
```cur_open->next = closed;
closed = cur_open;```

2. Can you post the whole code? Or a link to a zip (if it's multiple files)?

3. Originally Posted by john.c
Can you post the whole code? Or a link to a zip (if it's multiple files)?
Yes I have it all in a single file. It is pretty long so what's the best way to post it? Just paste it here?

4. If it lets you paste it here then you may as well. :-)

5. Originally Posted by john.c
If it lets you paste it here then you may as well. :-)
Full code:

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
-s means single thread, I'm planning on implementing multithreaded functionality

6. Yikes! It is a lot of code. Not too much, really, but more than I would expect for this problem (but I haven't solved it myself). It'll take me a while to peruse your code.

7. I found an error, I think. You're using valuestring as a representation of the board state to weed out repeated board positions. But the way you are setting it can look the same for different board states since you can't distinguish between 12 and 1 followed by 2 (for instance). You should sprintf them in a field width of 2 (with or without 0-fill since a space will work just as well).

I guess it's possible that's the source of your infinite loop, but either way it's something you should fix.

BTW, I can't actually compile your code because the spaces are "wacky spaces" of some kind. If you can fix that (and still edit your post) you should repost it. I'll try filtering out those characters....

EDIT: Now that I think about it, you may as well store the number in valuestring in hex so it only takes one character per element.
Code:
```void set_value_string(Node *pnode){
int offset = 0;
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
sprintf(pnode->valuestring + offset++,
"%x", pnode->tiles[i][j]);
pnode->valuestring[offset] = '\0';
}```

8. Originally Posted by john.c
I found an error, I think. You're using valuestring as a representation of the board state to weed out repeated board positions. But the way you are setting it can look the same for different board states since you can't distinguish between 12 and 1 followed by 2 (for instance). You should sprintf them in a field width of 2 (with or without 0-fill since a space will work just as well).

I guess it's possible that's the source of your infinite loop, but either way it's something you should fix.

BTW, I can't actually compile your code because the spaces are "wacky spaces" of some kind. If you can fix that (and still edit your post) you should repost it. I'll try filtering out those characters....
Good catch. I made the change and it did not affect the infinite loop.
Is this better? [C] #include <stdio.h> #include <stdlib.h> #include <string.h> #include <pthread. - Pastebin.com

9. Yeah, that works. I'll try some tests....

10. Upon further investigation, I found that my merge_to_open() function is not doing what I think it is. It is not adding some nodes that should be added.

11. Good. That gives you a place to focus.
I haven't been able to find anything and I think I'm done for the evening.
Good luck!

12. Any progress? It occurs to me that there are over 21 trillion possible configurations, so you better hope your heuristic is guiding you in the right direction!

Popular pages Recent additions