#include
struct state_t {
short S[9][9]; /* The Sudoku matrix, each cell has 9 bits representing each possible value for that cell */
short D[9][9]; /* Number of bits still on for each cell */
} ;
typedef struct state_t state_t;
/* Initialize the object */
void init_SD(state_t *S)
{
int i, j, k;
if (S == NULL) {
printf("ERROR NULL S pointer\n");
return;
}
for (i=0; i<9; i++)
for (j=0; j<9; j++)
S->S[i][j]=511; /* 511 is 1 1111 1111 in binary */
for (i=0; i<9; i++)
for (j=0; j<9; j++)
S->D[i][j]=9; /* no cell is done yet, so each cell has 9 possibilities */
}
/* Print a Sudoku matrix */
void print_S(state_t *S)
{
int i, j, k;
if (S == NULL) {
printf("ERROR NULL S pointer\n");
return;
}
printf("-------------------------------------------------------------------------------------------\n");
for (i=0; i<9; i++) {
for (j=0; j<9; j++)
switch (S->S[i][j]) {
case 0: printf("print_S() ERROR! Zero in S[%d][%d]\n", i, j); break;
case 1: printf("| 1 "); break;
case 2: printf("| 2 "); break;
case 4: printf("| 3 "); break;
case 8: printf("| 4 "); break;
case 16: printf("| 5 "); break;
case 32: printf("| 6 "); break;
case 64: printf("| 7 "); break;
case 128: printf("| 8 "); break;
case 256: printf("| 9 "); break;
default : printf("| "); break; /* unsolved cell */
}
printf("|\n");
printf("-------------------------------------------------------------------------------------------\n");
}
printf("\n");
}
/* Print the "Done" matrix */
void print_D(state_t *S)
{
int i, j, k;
if (S == NULL) {
printf("ERROR NULL S pointer\n");
return;
}
printf("-------------------------------------------------------------------------------------------\n");
for (i=0; i<9; i++) {
for (j=0; j<9; j++)
switch (S->D[i][j]) {
case 0: printf("print_D() ERROR! D[%d][%d] has value 0\n",i, j); break;
case 1: printf("| X "); break; /* when that cell has exactly one possibily, it's done */
case 2:
case 3:
case 4:
case 5:
case 6:
case 7:
case 8:
case 9: printf("| "); break;
default : printf("print_D() ERROR! D[%d][%d] has value > 9\n", i, j); break;
}
printf("|\n");
printf("-------------------------------------------------------------------------------------------\n");
}
printf("\n");
}
/* show the possibilities remaining in a cell */
void show_cell(state_t *S, int x, int y)
{
int m;
int i, j, k;
if (S == NULL) {
printf("ERROR NULL S pointer\n");
return;
}
for (i=1; i<=9; i++) {
m = 1 << (i-1); /* 0 0000 0001 moved 0-8 times */
if (S->S[x][y] & m) /* bit-wise AND to see if that bit is still on */
printf("%d", i);
else
printf(" ");
}
}
/* get the value of a cell whose value has been determined */
int get_cell(state_t *S, int x, int y)
{
int m;
int i, j, k;
int return_value, found;
if (S == NULL) {
printf("ERROR NULL S pointer\n");
return;
}
if (S->D[x][y] > 1) { /* assert: cell's value must have been determined */
printf("get_cell() called on a that is NOT done, x=%d, y=%d\n", x, y);
show_cell(S, x, y);
return 0;
}
found = 0;
return_value = 0;
for (i=1; i<=9; i++) {
m = 1 << (i-1); /* 0 0000 0001 moved 0-8 times */
if (S->S[x][y] & m) { /* bit-wise AND to find the cell's value */
if (! found) {
found = 1;
return_value += i;
}
else {
printf("get_cell(): ERROR! D[%d][%d] is 1 but S shows more than one possibility\n", x, y);
printf("get_cell(): the cell is: ");
show_cell(S, x, y);
printf("\n");
return return_value; /* return the old value */
}
}
}
return return_value;
}
/* given that a cell S(x,y) has been set to v, prune v from the rest of the row */
int prune_row(state_t *S, int x, int y, int v)
{
int m, i, j, k;
int made_change = 0;
int m_prime;
if (S == NULL) {
printf("ERROR NULL S pointer\n");
return;
}
m = ~ (1 << (v-1)); /* complement of mask */
m_prime = 1<< (v-1); /* mask for value v */
// printf("prune_row(): v is %x and mask for v, m, is %x\n", v, m);
for (j=0; j<9; j++)
if ( (S->D[x][j] > 1) && /* that cell has > 1 possibilities */
(S->S[x][j] & m_prime) && /* has v amongst those possibilities */
(j != y) ) { /* NOT the cell that we just set, unlikely, given first condition of >1 possibilities */
// printf("prune_row(): BEFORE S[%d][%d] = ", x, j);
// show_cell(S, x, j);
// printf("\n");
S->S[x][j] &= m; /* mask out that bit */
S->D[x][j]--; /* one possibility less */
made_change++; /* count it as a change made */
// printf("prune_row(): AFTER S[%d][%d] = ", x, j);
// show_cell(S, x, j);
// printf("\n");
}
if (made_change > 8) {
printf("prune_row(): ERROR! made more than 8 prunes in a row for S[%d][%d] value %d\n", x, y, v);
}
return made_change;
}
/* given that a cell S(x,y) has been set to v, prune v from the rest of the column */
int prune_column(state_t *S, int x, int y, int v)
{
int m, i, j, k;
int made_change = 0;
int m_prime;
if (S == NULL) {
printf("ERROR NULL S pointer\n");
return;
}
m = ~ (1 << (v-1)); /* complement of mask */
m_prime = 1<< (v-1); /* mask for value v */
// printf("prune_column(): v is %x and mask for v, m, is %x\n", v, m);
for (i=0; i<9; i++)
if ( (S->D[i][y] > 1) && /* that cell has > 1 possibilities */
(S->S[i][y] & m_prime) && /* has v amongst those possibilities */
(i != x) ) { /* NOT the cell that we just set, unlikely, given first condition of >1 possibilities */
// printf("prune_column(): BEFORE S[%d][%d] = ", i, y);
// show_cell(S, i, y);
// printf("\n");
S->S[i][y] &= m; /* mask out that bit */
S->D[i][y]--; /* one possibility less */
made_change++; /* count it as a change made */
// printf("prune_column(): AFTER S[%d][%d] = ", i, y);
// show_cell(S, i, y);
// printf("\n");
}
if (made_change > 8) {
printf("prune_column(): ERROR! made more than 8 prunes in a row for S[%d][%d] value %d\n", x, y, v);
}
return made_change;
}
/* given that a cell S(x,y) has been set to v, prune v from the rest of the block */
int prune_block(state_t *S, int x, int y, int v)
{
int m, i, j, k;
int made_change = 0;
int m_prime;
int Bx = x/3;
int start_x = Bx * 3;
int end_x = start_x + 2;
int By = y/3;
int start_y = By * 3;
int end_y = start_y + 2;
m = ~ (1 << (v-1)); /* complement of mask */
m_prime = 1<< (v-1); /* mask for value v */
if (S == NULL) {
printf("ERROR NULL S pointer\n");
return;
}
if (S->D[x][y] != 1) {
printf("loop_neighbour(): ERROR! given a cell S[%d][%d] that has not been set to $d\n", x, y, v);
return 0;
}
for (i=start_x; i<=end_x; i++) {
for (j=start_y; j<=end_y; j++) {
if ((i != x) && (j != y) && /* not the cell that we just set */
(S->D[i][j] > 1) && /* that cell has > 1 possibilities, must be */
(S->S[i][j] & m_prime)) { /* and v is in that cell's possibilities */
S->S[i][j] &= m; /* mask out that bit */
S->D[i][j]--; /* one possibility less */
made_change++; /* count it as a change made */
}
}
}
return made_change;
}
/* given S(x, y) which has been set to v, remove v from its neighbours in the same block */
int loop_neighbour(state_t *S, int x, int y, int v)
{
int i, j, k;
int m, m_prime;
int made_change = 0;
/* neighbour calculation worked out with Jeff Barto :-) */
int r = x/3;
int start_x = r*3;
int end_x = start_x + 2;
int rr = y/3;
int start_y = rr*3;
int end_y = start_y + 2;
/*
printf("loop_neighbour() called with S[%d][%d] = %d --- cell is: ", x, y, v);
show_cell(S, x, y);
printf("\n");
*/
if (S == NULL) {
printf("ERROR NULL S pointer\n");
return;
}
if (S->D[x][y] != 1) {
printf("loop_neighbour(): ERROR! given a cell S[%d][%d] that has not been set to $d\n", x, y, v);
return 0;
}
m = ~ (1 << (v-1));
m_prime = 1 << (v-1);
for (i = start_x; i <= end_x; i++)
for (j = start_y; j <= end_y; j++) {
/*
printf("loop_neighbour(): testing neighbour S[%d][%d] %d --- cell is: ", i, j, v);
show_cell(S, i, j);
printf("\n");
*/
if ((i != x) && (j != y) && /* not the cell itself */
(S->D[i][j] != 1) && /* not a set cell */
(S->S[i][j] & m_prime) ) { /* but that cell has v as a possibility */
/*
printf("loop_neighbour(): changing neighbour S[%d][%d] masking out %d --- cell is: ", i, j, v);
show_cell(S, i, j);
printf("\n");
*/
S->S[i][j] &= m;
S->D[i][j]--;
/*
printf("loop_neighbour(): after changing S[%d][%d] masking out %d --- cell is: ", i, j, v);
show_cell(S, i, j);
printf("\n");
*/
made_change++;
}
}
return made_change;
}
/* set the value of a cell to v, update the corresponding "Done" value for that cell */
/* then, prune the row and column */
int set_cell(state_t *S, int x, int y, int v)
{
int m, i, j, k;
if (S == NULL) {
printf("ERROR NULL S pointer\n");
return;
}
// printf("set_cell() setting S[%d][%d] to %d; value of S is origininally ---- ", x, y, v);
// show_cell(S, x, y);
// printf("\n");
switch (v) {
case 0: break;
case 1: S->S[x][y] = 1; S->D[x][y] = 1; break;
case 2: S->S[x][y] = 2; S->D[x][y] = 1; break;
case 3: S->S[x][y] = 4; S->D[x][y] = 1; break;
case 4: S->S[x][y] = 8; S->D[x][y] = 1; break;
case 5: S->S[x][y] = 16; S->D[x][y] = 1; break;
case 6: S->S[x][y] = 32; S->D[x][y] = 1; break;
case 7: S->S[x][y] = 64; S->D[x][y] = 1; break;
case 8: S->S[x][y] = 128; S->D[x][y] = 1; break;
case 9: S->S[x][y] = 256; S->D[x][y] = 1; break;
default : printf("set_cell(): ERROR! Value in a cell can only be 0-9\n"); break;
}
// printf("set_cell() result of setting S[%d][%d] to %d; value of S now ---- ", x, y, v);
// show_cell(S, x, y);
// printf("\n");
return 1+prune_row(S, x, y, v)+prune_column(S, x, y, v)+prune_block(S, x, y, v);
}
/* Get input from the command line, 0 for a blank cell and all others can only have values of 1-9 */
void read_S(state_t *S, int argc, char *argv[])
{
int n, i, j, k;
if (S == NULL) {
printf("ERROR NULL S pointer\n");
return;
}
if (argc != 82) {
printf("Usage %s data\n", argv[0]);
printf("(Use 0 to represent a blank)\n");
return;
}
for (n=1; n i = %d j = %d ---> k = %d\n", n, argv[n], i, j, k);
}
}
/* check out all the "Done" values in a Sudoku matrix to determine if we have finished */
int done(state_t *S)
{
int i, j, k;
int d = 1;
if (S == NULL) {
printf("ERROR NULL S pointer\n");
return;
}
for (i=0; i<9; i++)
for (j=0; j<9; j++)
d = d && (S->D[i][j] == 1); /* every "DONE" value must be exactly 1 */
return d;
}
/* print out the full Sudoku matrix with the possibilities of each cell */
void print_full_S(state_t *S)
{
int i, j, k;
if (S == NULL) {
printf("ERROR NULL S pointer\n");
return;
}
printf("-------------------------------------------------------------------------------------------\n");
for (i=0; i<9; i++) {
printf("|");
for (j=0; j<9; j++) {
show_cell(S, i,j);
printf("|");
}
printf("\n");
printf("-------------------------------------------------------------------------------------------\n");
}
printf("\n");
}
/* given a block, make sure a value v appears only once in the 9 cells that make up that block, return non-zero if error found */
int once_in_block(state_t *S, int Bx, int By, int *made_change)
{
int i, j, k;
int m;
int found;
int num;
int num_x = -1;
int num_y = -1;
if (S == NULL) {
printf("ERROR NULL S pointer\n");
return;
}
for (num=1; num<=9; num++) {
m = 1 << (num-1);
found = 0;
for (i = Bx*3; i < 3*Bx+3; i++)
for (j = By * 3; j < 3*By+3; j++)
if (S->S[i][j] & m) {
found++;
num_x = i;
num_y = j;
}
if (! found) {
// printf("once_in_block: ERROR %d not found in block Bx=%d By=%d\n", Bx, By);
return num;
}
else if ((found == 1) && (S->D[num_x][num_y] != 1)) {
/* found a value in this block that can only appear in one cell, and that cell has NOT been set to value */
// printf("once_in_block: calling set_cell for S[%d][%d] = %d; cell is --- ", num_x, num_y, num);
// show_cell(S, num_x, num_y);
// printf(" with D value = %d", S->D[num_x][num_y]);
// printf("\n");
*made_change += set_cell(S, num_x, num_y, num);
// printf("once_in_block: made_change: S[%d][%d] = %d\n", num_x, num_y, num);
}
/* else, v is in more than one cell in block, ie: we can't eliminate the possibilities for that value v in that block yet */
}
return 0;
}
/* given a column, make sure a value v appears only once in the 9 cells that make up that column */
int once_in_column(state_t *S, int column, int *made_change)
{
int i, j, k;
int v;
int m;
int found;
int found_row;
if (S == NULL) {
printf("ERROR NULL S pointer\n");
return;
}
for (v=0; v<9; v++) {
m = 1 << v;
found = 0;
for (i=0; i<9; i++)
if (S->S[i][column] & m) {
found++;
found_row = i;
}
if (! found) {
// printf("once_in_column: ERROR %d not found in column %d\n", v+1, column);
return v+1;
}
else if ((found == 1) && (S->D[found_row][column] != 1)) { /* found v only in a cell but that cell is not set to v */
// printf("once_in_column: calling set_cell setting %d in S[%d][%d]; cell is --- ", v+1, found_row, column);
// show_cell(S, found_row, column);
// printf("\n");
*made_change += set_cell(S, found_row, column, v+1);
}
/* else, v is in more than one column, ie: we can't eliminate the possibilities for that value v in that column yet */
}
return 0;
}
/* given a row, make sure a value v appears only once in the 9 cells that make up that row */
int once_in_row(state_t *S, int row, int *made_change)
{
int i, j, k;
int v;
int m;
int found;
int found_column;
if (S == NULL) {
printf("ERROR NULL S pointer\n");
return;
}
for (v=0; v<9; v++) {
m = 1 << v;
found = 0;
for (j=0; j<9; j++)
if (S->S[row][j] & m) {
found++;
found_column = j;
}
if (! found) {
// printf("once_in_row: ERROR %d not found in row %d\n", v+1, row);
return v;
}
else if ((found == 1) && (S->D[row][found_column] != 1)) { /* found v only in a cell but that cell is not set to v */
// printf("once_in_row: calling set_cell setting %d in S[%d][%d]; cell is --- ", v+1, row, found_column);
// show_cell(S, row, found_column);
// printf("\n");
*made_change += set_cell(S, row, found_column, v+1);
}
/* else, v is in more than one row, ie: we can't eliminate the possibilities for that value v in that row yet */
}
return 0;
}
/* find the cell with the least number of possibilities and set its coordinates in the (x,y) pointers given */
void find_cell_with_min(state_t *S, int *x, int *y)
{
int i, j, k;
int min = 9;
if (S == NULL) {
printf("ERROR NULL S pointer\n");
return;
}
for (i=0; i<9; i++)
for (j=0; j<9; j++)
if ((S->D[i][j] > 1) && (S->D[i][j] < min)) {
min = S->D[i][j];
*x = i;
*y = j;
}
}
/* clone source Sudoku to destination Sudoku */
void clone(state_t *src, state_t *dest)
{
int i, j, k;
if (src == NULL) {
printf("clone(): ERROR NULL source pointer\n");
return;
}
if (dest == NULL) {
printf("clone(): ERROR NULL destination pointer\n");
return;
}
for (i=0; i<9; i++)
for (j=0; j<9; j++) {
dest->S[i][j] = src->S[i][j];
dest->D[i][j] = src->D[i][j];
}
}
/* reduce as much as possible, if not, generate candidates and reduce them */
reduce_to_min(state_t *S, int iteration_count)
{
int i, j, k;
char r;
state_t *new_S;
int made_change;
int m;
int v;
int x, y;
if (S == NULL) {
printf("ERROR NULL S pointer\n");
return;
}
// printf("reduce_to_min(): Entering reduce_to_min() with count %d\n", iteration_count);
// printf("reduce_to_min(): Candidate matrix is: \n");
// print_S(S);
do {
made_change = 0;
// printf("reduce_to_min(): Iteration %d\n", ++iteration_count);
/*
for (i=0; i<9; i++)
for (j=0; j<9; j++)
if (S->D[i][j] == 1)
made_change += loop_neighbour(S, i, j, get_cell(S, i, j));
*/
for (i=0; i<3; i++)
for (j=0; j<3; j++)
if (once_in_block(S, i, j, &made_change)) {
// printf("reduce_to_min() found_error when trying block Bx=%d By=%d\n", i, j);
return;
}
for (i=0; i<9; i++)
if (once_in_row(S, i, &made_change)) {
// printf("reduce_to_min() found_error when trying row %d\n", i);
return;
}
for (j=0; j<9; j++)
if (once_in_column(S, j, &made_change)) {
// printf("reduce_to_min() found_error when trying column %d\n", j);
return;
}
// print_D(S); print_full_S(S); print_S(S);
} while (made_change && ! done(S));
if (! made_change) {
// printf("reduce_to_min(): Not Done\n");
find_cell_with_min(S, &x, &y);
// printf("reduce_to_min(): Found cell S[%d][%d]; cell is ---- ", x, y);
// show_cell(S, x, y);
// printf("\n");
for (v=1; v<=9; v++)
if (S->S[x][y] & (1 << (v-1))) { /* v is a possible value in cell S[x][y] */
new_S = (state_t *) malloc(sizeof(state_t));
if (new_S == NULL) {
printf("Out of memory\n");
return 0;
}
clone(S, new_S);
made_change += set_cell(new_S, x, y, v);
reduce_to_min(new_S, iteration_count);
}
}
else {
// printf(" ***** ----- ^^^^^ ===== vvvvv Done ***** ----- ^^^^^ ===== vvvvv \n");
print_S(S);
}
}
/* 20 Mar 2008, created by Chia-Ling Lee */
int main(int argc, char *argv[])
{
int i, j, k;
state_t *S;
if (argc != 82) {
printf("Usage %s data\n", argv[0]);
printf("(Use 0 to represent a blank)\n");
return 0;
}
S = (state_t *) malloc(sizeof(state_t));
if (S == NULL) {
printf("Out of memory\n");
return 0;
}
/*
for (i=0; i