Code:
/* Sudoku solver
1. Read in the unsolved puzzle from a file, converting
to an array of binary flags.
2. Scan array, using known quantities to turn off flags
for related cells (by row, column, and 3x3 square)
3. Locate cells that represent the only possibility for
a number in their row/column/3x3, and update flags.
4. Save partial solution, guess a missing number, and
find complete solution or return to saved solution and
guess again. !!! Need to implement this step !!!
5. Convert the binary flags into integers and print the
solution.
Written by Tyler Smith, 6 March, 2006 */
#include <stdio.h>
#include <math.h>
/* Bit-flag constants. */
#define ONE 1 /* 2^0 */
#define TWO 2 /* 2^1, etc. */
#define THREE 4
#define FOUR 8
#define FIVE 16
#define SIX 32
#define SEVEN 64
#define EIGHT 128
#define NINE 256
#define UNKNOWN 511
#define SOLVED 512
int search (), excluder();
void display ();
/* The sudoku board is stored as a four dimensional board.
The first two dimensions locate the row and column of
the cell within the 3x3 grid, and the third and fourth
dimensions locate the row and column of the 3x3 grid
relative to the other grids. The array is an external
variable, to avoid problems passing it back and forth
to the search function. */
int sudoku[3][3][3][3];
int main ()
{
extern int sudoku[3][3][3][3];
int minrow, mincol, majrow, majcol, i; /*counters*/
int inputvalue, outputvalue, changecount;
changecount = 0;
/* Populate the matrix */
/* The input stream must be uninterupted integers, no newlines, no spaces */
for (majrow = 0; majrow < 3; majrow++)
for (minrow = 0; minrow < 3; minrow++)
for (majcol = 0; majcol < 3; majcol++)
for (mincol = 0; mincol < 3; mincol++)
{
inputvalue = (getchar() - '0');
if (inputvalue != 0)
sudoku [minrow][mincol][majrow][majcol] =
pow (2, (inputvalue-1));
/* bit-flags correspond to 2 raised to (actual value - 1) */
else if (inputvalue == 0)
sudoku [minrow][mincol][majrow][majcol] = UNKNOWN;
else goto end; /* bail if the input is bad */
}
do
{
changecount = search();
if (changecount == 0) /* calls exclude when search() fails */
{
changecount = excluder();
}
}
while (changecount != 0); /* continue calling search () until both
search() and excluder () fail */
display ();
return 0;
end:
printf("Danger Will Robinison!\n");
return 1;
}
int search ()
{
/* printf ("Entered Search\n"); FOR DEBUGGING */
extern int sudoku[3][3][3][3];
int minrow, mincol, majrow, majcol; /*counters*/
int tmpminrow, tmpmincol, tmpmajrow, tmpmajcol; /* temporary counters */
int setvalue; /* store known value for flag-setting */
int changes = 0; /* track the number of changes made */
/* Search for known values, turn off related flags */
for (majrow = 0; majrow < 3; majrow++)
for (minrow = 0; minrow < 3; minrow++)
for (majcol = 0; majcol < 3; majcol++)
for (mincol = 0; mincol < 3; mincol++)
if ((sudoku [minrow][mincol][majrow][majcol] & SOLVED) == SOLVED)
continue; /* If the solved flag is set move on */
else if ((sudoku [minrow][mincol][majrow][majcol] != ONE) &&
(sudoku [minrow][mincol][majrow][majcol] != TWO) &&
(sudoku [minrow][mincol][majrow][majcol] != THREE) &&
(sudoku [minrow][mincol][majrow][majcol] != FOUR) &&
(sudoku [minrow][mincol][majrow][majcol] != FIVE) &&
(sudoku [minrow][mincol][majrow][majcol] != SIX) &&
(sudoku [minrow][mincol][majrow][majcol] != SEVEN) &&
(sudoku [minrow][mincol][majrow][majcol] != EIGHT) &&
(sudoku [minrow][mincol][majrow][majcol] != NINE))
continue; /* If the value is unknown move on */
else
{
setvalue = sudoku [minrow][mincol][majrow][majcol];
/* Set flags for the mini-grid */
for (tmpminrow = 0; tmpminrow < 3; tmpminrow++)
for (tmpmincol = 0; tmpmincol < 3; tmpmincol++)
if (tmpminrow == minrow && tmpmincol == mincol) continue;
else
sudoku [tmpminrow][tmpmincol][majrow][majcol] =
~setvalue & sudoku [tmpminrow][tmpmincol][majrow][majcol];
/* Set flags for major row */
for (tmpmajcol = 0; tmpmajcol < 3; tmpmajcol++)
for (tmpmincol = 0; tmpmincol < 3; tmpmincol++)
if (tmpmajcol == majcol && tmpmincol == mincol) continue;
else
sudoku [minrow][tmpmincol][majrow][tmpmajcol] =
~setvalue & sudoku [minrow][tmpmincol][majrow][tmpmajcol];
/* Set flags for major col */
for (tmpmajrow = 0; tmpmajrow < 3; tmpmajrow++)
for (tmpminrow = 0; tmpminrow < 3; tmpminrow++)
if (tmpmajrow == majrow && tmpminrow == minrow) continue;
else
sudoku [tmpminrow][mincol][tmpmajrow][majcol] =
~setvalue & sudoku [tmpminrow][mincol][tmpmajrow][majcol];
/* Set solved flag so procedure isn't repeated */
sudoku [minrow][mincol][majrow][majcol] =
sudoku [minrow][mincol][majrow][majcol] | SOLVED;
changes++;
}
/* printf("Changes %d\n",changes); FOR DEBUGGING */
return changes;
}
int excluder ()
{
/* printf ("Entered excluder\n"); FOR DEBUGGING */
extern int sudoku[3][3][3][3];
int minrow, mincol, majrow, majcol, i; /*counters*/
int changes = 0, index;
int possibles [9] = { 0, 0, 0, 0, 0, 0, 0, 0, 0 };
/* Exclude by rows */
for (majrow = 0; majrow < 3; majrow++)
for (minrow = 0; minrow < 3; minrow++)
{
for (majcol = 0; majcol < 3; majcol++)
for (mincol = 0; mincol < 3; mincol++)
{
if ((sudoku [minrow][mincol][majrow][majcol] & SOLVED) == 0)
for (i = 0; i < 9; i++)
{
index = (int)pow(2,i);
if((sudoku [minrow][mincol][majrow][majcol] & index) == index)
possibles[i]++;
}
}
for (majcol = 0; majcol < 3; majcol++)
for (mincol = 0; mincol < 3; mincol++)
{
if ((sudoku [minrow][mincol][majrow][majcol] & SOLVED) == 0)
for (i = 0; i < 9; i++)
if (possibles[i] == 1 &&
(sudoku [minrow][mincol][majrow][majcol] & (int)pow(2,i))
== (int)pow(2,i))
{
sudoku [minrow][mincol][majrow][majcol] = (int)pow(2,i);
changes++;
}
}
for (i = 0; i < 9; i++) possibles[i] = 0;
}
/* Exclude by columns */
for (majcol = 0; majcol < 3; majcol++)
for (mincol = 0; mincol < 3; mincol++)
{
for (majrow = 0; majrow < 3; majrow++)
for (minrow = 0; minrow < 3; minrow++)
{
if ((sudoku [minrow][mincol][majrow][majcol] & SOLVED) == 0)
for (i = 0; i < 9; i++)
{
index = (int)pow(2,i);
if((sudoku [minrow][mincol][majrow][majcol] & index) == index)
possibles[i]++;
}
}
for (majrow = 0; majrow < 3; majrow++)
for (minrow = 0; minrow < 3; minrow++)
{
if ((sudoku [minrow][mincol][majrow][majcol] & SOLVED) == 0)
for (i = 0; i < 9; i++)
if (possibles[i] == 1 &&
(sudoku [minrow][mincol][majrow][majcol] & (int)pow(2,i))
== (int)pow(2,i))
{
sudoku [minrow][mincol][majrow][majcol] = (int)pow(2,i);
changes++;
}
}
for (i = 0; i < 9; i++) possibles[i] = 0;
}
/* Exclude by 3x3 grids */
for (majcol = 0; majcol < 3; majcol++)
for (majrow = 0; majrow < 3; majrow++)
{
for (mincol = 0; mincol < 3; mincol++)
for (minrow = 0; minrow < 3; minrow++)
{
if ((sudoku [minrow][mincol][majrow][majcol] & SOLVED) == 0)
for (i = 0; i < 9; i++)
{
index = (int)pow(2,i);
if((sudoku [minrow][mincol][majrow][majcol] & index) == index)
possibles[i]++;
}
}
for (mincol = 0; mincol < 3; mincol++)
for (minrow = 0; minrow < 3; minrow++)
{
if ((sudoku [minrow][mincol][majrow][majcol] & SOLVED) == 0)
for (i = 0; i < 9; i++)
if (possibles[i] == 1 &&
(sudoku [minrow][mincol][majrow][majcol] & (int)pow(2,i))
== (int)pow(2,i))
{
sudoku [minrow][mincol][majrow][majcol] = (int)pow(2,i);
changes++;
}
}
for (i = 0; i < 9; i++) possibles[i] = 0;
}
/* End Exclude by minigrids */
/* printf("Changes %d\n", changes); FOR DEBUGGING */
return changes;
}
void display()
{
/* Print the solved array */
int minrow, mincol, majrow, majcol; /*counters*/
int solution [3][3][3][3];
extern sudoku [3][3][3][3];
for (majrow = 0; majrow < 3; majrow++)
{
for (minrow = 0; minrow < 3; minrow++)
{
for (majcol = 0; majcol < 3; majcol++)
{
for (mincol = 0; mincol < 3; mincol++)
{
switch (sudoku [minrow][mincol][majrow][majcol] - SOLVED)
{
case ONE : solution [minrow][mincol][majrow][majcol] = 1; break;
case TWO : solution [minrow][mincol][majrow][majcol] = 2; break;
case THREE : solution [minrow][mincol][majrow][majcol] = 3; break;
case FOUR : solution [minrow][mincol][majrow][majcol] = 4; break;
case FIVE : solution [minrow][mincol][majrow][majcol] = 5; break;
case SIX : solution [minrow][mincol][majrow][majcol] = 6; break;
case SEVEN : solution [minrow][mincol][majrow][majcol] = 7; break;
case EIGHT : solution [minrow][mincol][majrow][majcol] = 8; break;
case NINE : solution [minrow][mincol][majrow][majcol] = 9; break;
default : solution [minrow][mincol][majrow][majcol] = 0; break;
}
printf("%4d",solution [minrow][mincol][majrow][majcol]);
}
printf(" ");
}
printf("\n");
}
printf("\n\n");
}
}