#include
#include
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;
}
No comments:
Post a Comment