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