Thread: Linked List Infinite Loop

  1. #1
    Registered User
    Join Date
    Nov 2018
    Posts
    8

    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;
    Last edited by pboy; 11-17-2018 at 01:59 PM.

  2. #2
    Registered User john.c's Avatar
    Join Date
    Dec 2017
    Posts
    616
    Can you post the whole code? Or a link to a zip (if it's multiple files)?
    The world hangs on a thin thread, and that is the psyche of man. - Carl Jung

  3. #3
    Registered User
    Join Date
    Nov 2018
    Posts
    8
    Quote Originally Posted by john.c View Post
    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. #4
    Registered User john.c's Avatar
    Join Date
    Dec 2017
    Posts
    616
    If it lets you paste it here then you may as well. :-)
    The world hangs on a thin thread, and that is the psyche of man. - Carl Jung

  5. #5
    Registered User
    Join Date
    Nov 2018
    Posts
    8
    Quote Originally Posted by john.c View Post
    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
    Last edited by pboy; 11-17-2018 at 04:02 PM.

  6. #6
    Registered User john.c's Avatar
    Join Date
    Dec 2017
    Posts
    616
    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.
    The world hangs on a thin thread, and that is the psyche of man. - Carl Jung

  7. #7
    Registered User john.c's Avatar
    Join Date
    Dec 2017
    Posts
    616
    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';
    }
    Last edited by john.c; 11-17-2018 at 05:18 PM.
    The world hangs on a thin thread, and that is the psyche of man. - Carl Jung

  8. #8
    Registered User
    Join Date
    Nov 2018
    Posts
    8
    Quote Originally Posted by john.c View Post
    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. #9
    Registered User john.c's Avatar
    Join Date
    Dec 2017
    Posts
    616
    Yeah, that works. I'll try some tests....
    The world hangs on a thin thread, and that is the psyche of man. - Carl Jung

  10. #10
    Registered User
    Join Date
    Nov 2018
    Posts
    8
    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. #11
    Registered User john.c's Avatar
    Join Date
    Dec 2017
    Posts
    616
    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!
    The world hangs on a thin thread, and that is the psyche of man. - Carl Jung

  12. #12
    Registered User john.c's Avatar
    Join Date
    Dec 2017
    Posts
    616
    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!
    The world hangs on a thin thread, and that is the psyche of man. - Carl Jung

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 3
    Last Post: 10-14-2011, 11:33 PM
  2. Help with running a double for loop on a linked list
    By Seabass6741 in forum C Programming
    Replies: 4
    Last Post: 03-15-2009, 02:22 PM
  3. a double linked list loop
    By elton_fan in forum C Programming
    Replies: 1
    Last Post: 10-01-2007, 11:26 AM
  4. loop in a linked list
    By krithi in forum C Programming
    Replies: 3
    Last Post: 12-03-2002, 06:06 PM

Tags for this Thread