Here we present a very compact Sudoku Solver. The actual functions for solving the game is less than 40 lines long. The code is written in C++, compiled and tested with Microsoft VC++ 6.0 compiler. A VC++ 6.0 project is included that can be readily built and run. Permission is granted for personal, non-commercial use only.
The solver is coded in a C++ class as listed below :
class CSudokuSolver
{
public :
enum CELL_STATE { STATE_NOTSET=0, STATE_FIX, STATE_FIXTEMP, };
private :
char CellValue[9][9];
int IsValueOkAt(int iValue,int atX,int atY) const;
int FixCellAt(int ix, int iy);
public :
CSudokuSolver( );
void SetValue(int ix,int iy, int iValue, CELL_STATE
iState=STATE_FIX);
int GetValue(int ix,int iy) const;
CELL_STATE GetState(int ix,int iy) const;
int Solve();
static int Box3x3Start(int
idx) { return 3*(idx/3); };
};
To use the solver, create an instance of the class. Set the fixed values of the puzzle to be solved. Then call function Solve() and check the return value. See the main() function in the project code.
Mainly 2 functions are involved in the solving process. The first one is IsValueOkAt(...). This function checks, using Sudoku rules, if a given value is ok or not at a given cell position. The 2nd function is FixCellAt(...). This function is listed below.
int
CSudokuSolver::FixCellAt(int ix,int iy)
{
if( GetState(ix,iy)==STATE_FIX ) { // do the next cell
if( ix==8 && iy==8 ) return 1;// The last cell, done
successfully
if( ix<8 ) ix++; else { iy++; ix=0; }
return FixCellAt(ix,iy);
}
else {
int i,j,iv; // Try numbers from 1 to 9
for(iv=1; iv<10; iv++) { //---- Reset the values to 0
for(i=ix; i<9; i++) if(
GetState(i,iy)!=STATE_FIX) SetValue(i,iy,0);
for(i=iy+1; i<9; i++) {
for(j=0; j<9; j++) if(
GetState(j,i)!=STATE_FIX) SetValue(j,i,0);
}
if( IsValueOkAt(iv,ix,iy) ) {
SetValue(ix,iy,iv,STATE_FIXTEMP);
if( ix==8 && iy==8 ) return
1; // The last cell, done successfully
i = ix;
j = iy;
if( i<8 ) i++; else { j++;
i=0; }
if( FixCellAt(i,j) ) return 1;
}
}
return 0; // Cannot find a value. Must change the previous
cell.
}
}
Notice that this function is recursive(that means it calls itself). It is the recursion that makes the code so compact. In fact, this solution may not be possible without recursion. The solution starts with a call to FixCellAt(0,0). The steps are :
-
If the current cell is already fixed, move to the next cell.
-
For the current cell, try values from 1 to 9. If a number is OK, then sets the cell and move onto the next cell.
-
If all numbers failed, then move back to the previous cell and try a different value.
Advantages : The code is very
compact. Multiple solutions, if any, can be found. The solutions (or no
solution) are complete and absolute.
Disadvantage : An exhaustive search may take
several minutes on a PC.
On the other hand, an intuitive solution uses Sudoku logic to solve a puzzle, immitating how a brain works. This method is computationally faster. But the coding is much lengthier and there is no guarantee of a solution, as in case of a human being. A combination of both may be used, as in our Sudoku PC program.
