Thread: 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;

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

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

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

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.

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';
}

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

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!

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!