Thread: C: confusing problem with 'for' loops.

  1. #1
    Registered User
    Join Date
    Feb 2009
    Posts
    33

    Confusing problem with 'for' loops.

    The code below is an extract of the main program, as I only need a portion of the program to recreate the problem I'm having.

    If I run this code, the call to 'free' will crash, but only on specific cells, rather than all or none of them.

    What further complicates the problem is on my desktop, the loop will crash on [0][1]. On my netbook, it will crash on [0][2]. Both do use slightly different compilers (netbook uses Dev-cpp 4.xxx, desktop uses Dev-cpp 5.xxx). Could it be Dev-cpp itself that's causing the problem?

    Code:
    #include <stdio.h>
    
    struct cell
    {
        int value;
        struct cell * next;
    } sudokuArray[8][8];
    
    initCell(struct cell * cellPtr, int number)  // Create a linked list, containing numbers 1 to 9, in each array element.
    {
        if (number <= 8)
        {
            cellPtr->next = (struct cell *) malloc(sizeof(struct cell));
            cellPtr->value = number;
            number++;
            initCell(cellPtr->next, number);
        }
        else
        {
            cellPtr->value = number;
            cellPtr->next = NULL;
        }
    }
    
    int main(void)
    {
        int a, b;
        for (a = 0; a <= 8; a++)  // Loop is simply meant to remove head off the linked list for array element.
        {
            for (b = 0; b <= 8; b++)
            {
                initCell(&sudokuArray[a][b], 1);
                printf("Attempting to edit %i, %i\n", a, b);
                struct cell * temp = &sudokuArray[a][b];
                sudokuArray[a][b] = * sudokuArray[a][b].next;
                free(temp);
            }
        }
        getchar();
    
        return 1;
    }
    Last edited by thealmightyone; 02-04-2009 at 05:27 PM.

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    A sudoku puzzle uses a 9 X 9 matrix, (for standard sudoku puzzle), and you've made yours 8 X 8. 1 to 9 is nine, but a[8] only has a[0] to a[7].

    I would fix that first.

  3. #3
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    temp is not something you have allocated using malloc, why suddenly comes free into play?
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  4. #4
    Registered User ralu.'s Avatar
    Join Date
    Feb 2009
    Location
    Bucharest, RO
    Posts
    32
    Quote Originally Posted by Adak View Post
    A sudoku puzzle uses a 9 X 9 matrix, (for standard sudoku puzzle), and you've made yours 8 X 8. 1 to 9 is nine, but a[8] only has a[0] to a[7].

    I would fix that first.
    What u wrote is wrong... he has a 9x9 matrix already... to put it your way 0 to 8 is 9. and a[8] in the 9th element.

  5. #5
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Code:
    sudokuArray[8][8];
    This is a 8 * 8 array any way you look at it.

    Also the loops go out of bounds
    Code:
        for (a = 0; a <= 8; a++)  // Loop is simply meant to remove head off the linked list for array element.
        {
            for (b = 0; b <= 8; b++)
    When the size of the array is N, then array[N] is the first item that is out of range. Normally you use less-than N or even not-equal-to N when looping over arrays.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  6. #6
    Registered User
    Join Date
    Feb 2009
    Posts
    33
    Thank you anon, you are correct. I do have another problem, but it does require me to post most of the code, so I've decided to post it all.

    The problem is in the updateCell procedure, which is:
    Code:
    updateCell(int x, int y, int a)  // Removes 'a' from linked list, pointed to by array[x][y]
    {
        struct cell * cellPtr = &sudokuArray[x][y];
        
        if(!cellPtr->next)  // Already set.
            return;
        if(inPossible(x, y, a))
        {
            struct cell * tempPtr1;
            tempPtr1 = cellPtr;
            if (cellPtr->value == a)  // Value is at start of list.
            {
                * cellPtr = * cellPtr->next;
                if (a != 1)
                    free(tempPtr1);
            }
            else
            {
                struct cell * tempPtr2;
                while((tempPtr1->next->value != a) && (tempPtr1->next->next))
                    tempPtr1 = tempPtr1->next;
                if (tempPtr1->next->value == a)  // Value in middle of list.
                {
                    tempPtr2 = tempPtr1->next;
                    tempPtr1->next = tempPtr1->next->next;
                    free(tempPtr2);
                }
                else
                {
                    while(tempPtr1->next->next)  // Value is at end of list.
                        tempPtr1 = tempPtr1->next;
                    tempPtr2 = tempPtr1->next;
                    tempPtr1->next = NULL;
                    free(tempPtr2);
                }
            }
        }
        //else  // This is problem, not working properly. If else contains nothing, when updateCell(x, y, b) is called, and [x][y] does not contain b, is is re-added.
            //printf("Cell %i, %i unable to take value %i\n", x, y, a);
        if(possibles(x, y) == 0)
            printf("Error - A cell has had all possible values removed from list.\n");
        else if(possibles(x, y) == 1)
            setCell(x, y, a);
    }
    If the else statement is commented out (because it doesn't need to even be in procedure), code misbehaves (shown by the loop in main). However, if the else statement is uncommented, the code works. Any ideas?

    In the main loop, I am setting 4 cells to 9, and adding these cells to a queue, so all cells in same column and row have 9 removed from list of possible value. For some reason for the cells which are updated twice (once by being in same row as, say, [2][0], and second by being in same column as, say, [3][3]), either have 9 removed, then re-added, or not removed at all.

    It is quite tricky to describe the problem, so please ask questions if this confuses you.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    
    
    int update = 1;  // Global boolean, to ensure each update iteration is making progress.
    
    
    
    struct cell
    {
        int value;
        struct cell * next;  // Allows for storage of all possible values that cell can take.
    } sudokuArray[9][9];
    
    
    
    struct list
    {
        int x;
        int y;
        struct list * next;
    } *pendingList;  // When a cell is set, it is added to queue, to keep track of which rows and columns need to be updated.
    
    
    
    initCell(struct cell * cellPtr, int count)  // Each cell needs a linked list of number 1 to 9, inclusive.
    {
        if (count <= 8)
        {
            cellPtr->next = (struct cell *) malloc(sizeof(struct cell));
            cellPtr->value = count;
            count++;
            initCell(cellPtr->next, count);
        }
        else
        {
            cellPtr->value = count;
            cellPtr->next = NULL;
        }
    }
    
    
    
    initialise(void)
    {
        int x, y;
        for (x = 0; x <= 8; x++)
        {
            for(y = 0; y <= 8; y++)
            {
                initCell(&sudokuArray[x][y], 1);
            }
            
        }
    }
    
    
    
    int inPossible(int x, int y, int a)  // Checks if input cell is able to be set to 'a'.
    {
        int boolean = 0;
        struct cell * tempPtr = &sudokuArray[x][y];
        while(tempPtr)
        {
            if (tempPtr->value == a)
            {
                boolean = 1;
                return;
            }
            else
                tempPtr = tempPtr->next;
        }
        return boolean;
    }
    
    
    
    addToPending(int a, int b)
    {
        if (pendingList == NULL)
        {
            pendingList = (struct list *) malloc(sizeof(struct list));
            pendingList->x = a;
            pendingList->y = b;        
            pendingList->next = NULL;
        }
        else
        {
            struct list * tempPtr = pendingList;
            while(tempPtr->next)
                tempPtr = tempPtr->next;
            tempPtr->next = (struct list *) malloc(sizeof(struct list));
            tempPtr->next->x = a;
            tempPtr->next->y = b;
            tempPtr->next->next = NULL;
        }
    }
    
    
    
    possibles(int x, int y)  // Returns number of values cell can possibly take.
    {
        int count = 0;
        struct cell * tempPtr = &sudokuArray[x][y];
        while(tempPtr)
        {
            count++;
            tempPtr = tempPtr->next;
        }
        return count;
    }
            
    
    
    updateCell(int x, int y, int a)  // Removes 'a' from linked list, pointed to by array[x][y]
    {
        struct cell * cellPtr = &sudokuArray[x][y];
        
        if(!cellPtr->next)  // Already set.
            return;
        if(inPossible(x, y, a))
        {
            struct cell * tempPtr1;
            tempPtr1 = cellPtr;
            if (cellPtr->value == a)  // Value is at start of list.
            {
                * cellPtr = * cellPtr->next;
                if (a != 1)
                    free(tempPtr1);
            }
            else
            {
                struct cell * tempPtr2;
                while((tempPtr1->next->value != a) && (tempPtr1->next->next))
                    tempPtr1 = tempPtr1->next;
                if (tempPtr1->next->value == a)  // Value in middle of list.
                {
                    tempPtr2 = tempPtr1->next;
                    tempPtr1->next = tempPtr1->next->next;
                    free(tempPtr2);
                }
                else
                {
                    while(tempPtr1->next->next)  // Value is at end of list.
                        tempPtr1 = tempPtr1->next;
                    tempPtr2 = tempPtr1->next;
                    tempPtr1->next = NULL;
                    free(tempPtr2);
                }
            }
        }
        //else  // This is problem, not working properly. If else contains nothing, when updateCell(x, y, b) is called, and [x][y] does not contain b, is is re-added.
            //printf("Cell %i, %i unable to take value %i\n", x, y, a);
        if(possibles(x, y) == 0)
            printf("Error - A cell has had all possible values removed from list.\n");
        else if(possibles(x, y) == 1)
            setCell(x, y, a);
    }
    
    
    
    getBox(int a)  // Returns top left cell co-ords of 3x3 box containing a, a (requires 2 calls)
    {
        {
            if (a <= 2)
                 return 0;
            else if (a <= 5)
                return 3;
            else
                return 6;
        }
    }        
    
    
    
    simpleUpdate(int x, int y)  // Updates all cells in same column, row and 3x3 box as input cell.
    {
        int a, b, value, boxx, boxy;  // Is getting, as input, 1, 1.
    
        if (!sudokuArray[x][y].next)
        {
            value = sudokuArray[x][y].value;
        }
        else
        {
            printf("Error - Input cell %i, %i has not been set to a value.\n", x, y);  // Should not happen
            return;
        }
        for(b = 0; b <= 8; b++)  // Row
            updateCell(b, y, value);
        for(a = 0; a <= 8; a++)  // Column.
            updateCell(x, a, value);
        /*boxx = getBox(x);
        boxy = getBox(y);
        for(a = 0; a <= 2; a++)  // 3x3 box.
        {
            for(b = 0; b <= 2; b++)
            {
                //printf("x is %i, y is %i\n", boxx + a, boxy + b);
                //printPossibles(&sudokuArray[boxx + a][boxy + b]);
                updateCell(boxx + a, boxy + b, value);  // This line is problem, won't run if it is only member of for loop.
                //printPossibles(&sudokuArray[boxx + a][boxy + b]);
                printf("\n");
            }
        }*/
    }
    
    
    
    rowScan(int y, int value)
    {
        int a, count = 0;
        for (a = 0; a <= 8; a++)
        {
            if (inPossible(a, y, value))
                count++;
        }
        return count;
    }
    
    
    
    columnScan(int x, int value)
    {
        int a, count = 0;
        for (a = 0; a <= 8; a++)
        {
            if (inPossible(x, a, value))
                count++;
        }
        return count;
    }
    
    
    
    boxScan(int x, int y, int value)
    {
        int a, b, count;
        for (a = 0; a <= 2; a++)
        {
            for (b = 0; b <= 2; b++)
            {
                if (inPossible(x + a, y + b, value))
                    count++;
            }
        }
        return count;
    }
    
    
    
    oneCellUpdate()  // Check columns, rows and boxes, to see if a value can only be put in 1 of the 9 cells.
    {
        update = 0;
        int a, b, c, d, temp, count = 0, x, y;
        for(temp = 0; temp <= 8; temp++)  // Run check for all number 1 to 9.
        {
            //printf("Just before loop for temp value %i\n", temp);
            for(a = 0; a <= 8; a++)  // Iterate through 9 rows.
            {
                if (rowScan(a, temp) == 1)
                {
                    b = 0;
                    update = 1;
                    while(!inPossible(b, a, temp))
                        b++;
                    setCell(b, a, temp);
                }
            }
            //printf("Just after loop for temp value %i\n", temp);
            for(a = 0; a <= 8; a++)  // Iterate through 9 columns.
            {
                if (columnScan(a, temp) == 1)
                {
                    b = 0;
                    update = 1;
                    while(!inPossible(a, b, temp))
                        b++;
                    setCell(a, b, temp);
                }
            }
            for(a = 0; a <= 8; a = a + 3)  // Iterate through boxes
            {
                for(b = 0; b <= 8; b = b + 3)
                {
                    //printf("Just before box scan\n");
                    a = 6, b = 0;
                    for(c = 0; c <= 2; c++)  // Iterate through box cell columns
                    {
                        for(d = 0; d <= 2; d++)
                        {
                            if(inPossible(a + c, b + d, temp))
                            {
                                count++;
                                x = a + c, y = b + d;
                            }
                        }
                    }
                    //printf("Just after box scan\n");
                    if (count == 1)
                    {
                        setCell(x, y, temp);
                        update = 1;
                    }
                    count = 0;
                }
            }
        }
    }
    
    
    
    updateGrid(void)
    {
        struct list * tempPtr;
        while(pendingList)
        {
            simpleUpdate(pendingList->x, pendingList->y);
            tempPtr = pendingList;
            pendingList = pendingList->next;
            free(tempPtr);
        }
        /*while(update)
            oneCellUpdate();*/
        printf("No more updates possible.\n");
    }
    
    
    
    clear(struct cell * cellPtr)  // Deletes a linked list.
    {
        if (cellPtr == NULL)
            return;
        else if (cellPtr->next)
            clear(cellPtr->next);
        free(cellPtr);
    }
    
    
    
    setCell(int x, int y, int a)  // Gives cell a value, and deletes linked list (next = NULL indicates cell has been set).
    {
        if (inPossible(x, y, a))
        {
            update = 1;
            printf("x is %i, y is %i\n", x, y);
            sudokuArray[x][y].value = a;
            clear(sudokuArray[x][y].next);
            sudokuArray[x][y].next = NULL;
            addToPending(x, y);
        }
        else
            printf("setCell called when value not a possible value, x is %i, y is %i, value is %i\n", x, y, a);
    }
    
    
    
    printLine(int y)
    {
        int x, count = 0;
        for (x = 0; x <= 8; x++)
        {
            if (possibles(x, y) == 1)
                printf(" %i", sudokuArray[x][y].value);
            else
                printf("  ");
            count++;
            if ((count == 3) & (x != 8))
            {
                printf(" |");
                count = 0;
            }
        }
    }
        
    
    
    
    printGrid()
    {
        int x, y, count = 0;
        printf("   0 1 2   3 4 5   6 7 8\n");
        for (y = 0; y <= 8; y++)
        {
            printf("%i ", y);
            printLine(y);
            count++;
            printf("\n");
            if ((count == 3) & (y != 8))
            {
                printf("  ------------------------\n");
                count = 0;
            }
        }
    }
    
    
    
    printPossibles(struct cell * cellPtr)
    {
        if(cellPtr)
        {
            printf("%i, ", cellPtr->value);
            printPossibles(cellPtr->next);
        }
        else
            printf("\n");
    }
    
    
    
    int main(void)
    {
        initialise();
        
        setCell(2, 0, 9);
        setCell(6, 2, 9);
        setCell(3, 3, 9);
        setCell(5, 6, 9);
    
        updateGrid();
        
        int a, b;
        for (a = 0; a <= 2; a++)
        {
            for (b = 0; b <= 2; b++)
            {
                printf("x is %i, y is %i, possibles are: ", a + 3, b);
                printPossibles(&sudokuArray[3 + a][b]);
            }
        }
    
        printf("\n");
        printGrid();
    
        getchar();
        
        return 1;
    }

  7. #7
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Code:
    if (tempPtr->value == a)
            {
                boolean = 1;
                return;  //ooops!  return what?
            }

  8. #8
    Registered User
    Join Date
    Feb 2009
    Posts
    33
    Quote Originally Posted by tabstop View Post
    Code:
    if (tempPtr->value == a)
            {
                boolean = 1;
                return;  //ooops!  return what?
            }
    That isn't meant to return anything. it's purpose is to exit updateCell. I'll change the layout of procedure, so everything is inside an if statement : if (cellPtr->next).

    EDIT: Just did that (the entire procedure only runs if (cellPtr->next) ), and I still get exactly the same problem with the else statement.
    Last edited by thealmightyone; 02-05-2009 at 07:31 AM.

  9. #9
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by thealmightyone
    That isn't meant to return anything.
    If the function is not supposed to return anything, but relies entirely on side effects, then declare it with a void return type. At the moment you have a bunch of functions with no return type, which means that they implicitly have an int return type.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  10. #10
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Do you have your compiler errors and warnings turned to high detection? Are you getting any errors or warnings?

    I believe you definitely should be.

  11. #11
    Registered User
    Join Date
    Feb 2009
    Posts
    33
    Quote Originally Posted by laserlight View Post
    If the function is not supposed to return anything, but relies entirely on side effects, then declare it with a void return type. At the moment you have a bunch of functions with no return type, which means that they implicitly have an int return type.
    Like so? :

    Code:
    void updateCell(int x, int y, int a)  // Removes 'a' from linked list, pointed to by array[x][y]
    {
        struct cell * cellPtr = &sudokuArray[x][y];
        
        if(!cellPtr->next)  // Already set.
            return;
    Adak, I've looked through options, and any that looked like they affected error detection, were set for maximum detection.
    Last edited by thealmightyone; 02-05-2009 at 08:03 AM.

  12. #12
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by thealmightyone View Post
    That isn't meant to return anything. it's purpose is to exit updateCell. I'll change the layout of procedure, so everything is inside an if statement : if (cellPtr->next).

    EDIT: Just did that (the entire procedure only runs if (cellPtr->next) ), and I still get exactly the same problem with the else statement.
    If that's not meant to return anything, then you might as well throw it all away and start from scratch. How can you test if(inPossible) if inPossible doesn't return anything?

  13. #13
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    I'll have to back out, because my compiler is full of warnings and errors - just stops at 25.

  14. #14
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by thealmightyone
    Like so?
    Yes.

    I suggest that you use typedefs, e.g.,
    Code:
    typedef struct cell
    {
        int value;
        struct cell *next;
    } SudokuCell;
    
    typedef SudokuCell SudokuGrid[9][9];
    Then avoid using the global array by passing a pointer to the first element of the array to the various functions, e.g.,
    Code:
    void updateCell(SudokuGrid grid, int x, int y, int a)
    {
        if (!grid[x][y].next) /* Already set. */
            return;
    
        /* ... */
    }
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Laptop Problem
    By Boomba in forum Tech Board
    Replies: 1
    Last Post: 03-07-2006, 06:24 PM
  2. Replies: 5
    Last Post: 11-07-2005, 11:34 PM
  3. half ADT (nested struct) problem...
    By CyC|OpS in forum C Programming
    Replies: 1
    Last Post: 10-26-2002, 08:37 AM
  4. binary tree problem - help needed
    By sanju in forum C Programming
    Replies: 4
    Last Post: 10-16-2002, 05:18 AM
  5. problem with output
    By Garfield in forum C Programming
    Replies: 2
    Last Post: 11-18-2001, 08:34 PM