C: 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;
}

---

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.

temp is not something you have allocated using malloc, why suddenly comes free into play?

Quote:

---

Originally Posted by Adak

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.

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.

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

---

Code:

---

if (tempPtr->value == a)
        {
            boolean = 1;
            return;  //ooops!  return what?
        }

---

Quote:

---

Originally Posted by tabstop

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.

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.

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.

Quote:

---

Originally Posted by laserlight

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.

Quote:

---

Originally Posted by thealmightyone

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?

I'll have to back out, because my compiler is full of warnings and errors - just stops at 25.

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;

    /* ... */
}

---