JavaScript Sudoku Solver
In Computing science artificial intelligence terms, the game of Sudoku is a constraint satisfaction problem. Constraint satisfaction problems are nice in the regard that there are some very nice heuristics that lead to an easy algorithm to solve them. On the other hand, constraint satisfaction problems with a large problem domain may take an inordinate amount of time to solve.
Sudoku consists of a 9×9 grid, with each grid cell having a possible 9 different values. If we ignore all the constraints, this gives a possible 9^81 boards (1.9662705 × 10^77). Say we can check one-hundred trillion boards a second (100,000,000,000), it would still take ((9^81)/100000000000)/(31556926) = 6.23 × 10^58 years to iterate over all possible combinations! Clearly randomly generating boards and checking if the constraints are fulfilled is not a realistic solution.
Instead, we will implement a backtracking algorithm. In a nutshell, backtracking incrementally builds a solution, buy iteratively assigning possible values and then checking the validity of the assignment against the constraints. If a constraint doesn’t hold, the algorithm immediately backtracks, pruning any other possible (wrong) solution that involved that illegal value.
For efficiency’s sake, we want to prune an incorrect solution as early as possible – that is to say, we want to assign values to a maximally constrained cell. To do this, we want to be assigning values to a maximally constrained cell.
For example, in Sudoku, if we are examining 3 cells in a single row: C1, C2 and C3 and C1 has one legal value (3), C2 has 4 legal values (1,5,3,2) and C3 has 2 legal values (4,3). Obviously we will want to assign the value 3 to C1 (C1=3) first, then 4 to C3 (C3=4), and then figure out C2 down the line.
What if we didn’t assign the value 3 to C1 first, and instead assigned 3 to C2 (C2=3)? Then we would have C3=4, and when we come to assign C1, there are no legal values left, so we have wasted traversing this entire branch!
With Backtracking, and early pruning in mind we can develop the following algorithm:
Let c(j,k) be the cell in column j and row k.
Let V(j,k) be the number of valid values on cell c(j,k).
Let v(j,k,i) be a valid value for a cell.
1. Calculate the possible values for every cell c(j,k) that doesnt have a value v(j,k,i) assigned
if every cell has a value, done.
2. Find the cell cxy, such that for all a, b, V(x,y) < V(a,b). That is to say, find the cell with the least number of possible values.
if V(x,y) = 1 (only one possible value)
assign c(x,y) = v(x,y,1)
goto 1
else
foreach value m in v(x,y)
assign c(x,y) = m
goto 1
To summarize, find the cell that is most constrained (least valid assignments). If there is a single valid assignment, make the assignment and recurse, otherwise, foreach valid assignment, assign the value, and recurse.
In JavaScript, step 1 will look like:
/**
* Gets the values in a given row (meaning iterate through all the columns),
* across all te blocks
*
* @param int row The row to get the column values for
* @param int blockRow The row the block is in (1, 2, 3)
*/
getRowValues: function(row, blockRow){
var values = [];
for(var bcol=1; bcol<=3; bcol++){
for( var col=1; col<=3; col++){
var value = this._boardState[blockRow][bcol][row][col].value;
if(is_numeric(value)){
values[values.length] = value;
}
}
}
return values;
},
/**
* Gets all the values in a given column (meaning iterate through all rows),
* accross all the blocks
*
* @param int column The column to get the row values for
* @param int columnRow The column the block is in (1, 2, 3)
*/
getColumnValues: function(col, blockCol){
var values = [];
for(var brow=1; brow<=3; brow++){
for( var row=1; row<=3; row++){
var value = this._boardState[brow][blockCol][row][col].value;
if(is_numeric(value)){
values[values.length] = value;
}
}
}
return values;
},
getBlockValues: function(blockRow, blockCol){
var values = [];
for(var row=1; row<=3; row++){
for(var col=1; col<=3; col++){
var value = this._boardState[blockRow][blockCol][row][col].value;
if(is_numeric(value)){
values[values.length] = value;
}
}
}
return values;
},
/**
* Gets all possible legal values a cell may possess
*/
getValidCellValues: function(blockRow, blockCol, row, col){
var possibleValues = [1,2,3,4,5,6,7,8,9];
possibleValues = array_diff(possibleValues, this.getRowValues(row, blockRow));
possibleValues = array_diff(possibleValues, this.getColumnValues(col, blockCol));
possibleValues = array_diff(possibleValues, this.getBlockValues(blockRow, blockCol));
return possibleValues;
}
```
We get all the values that appear in the current row, the current column, and the local block (3x3 section the cell is in).
Starting with all the possible assignments, we subtract off any values that appear in the current row, column, or block.
Step 2 is written as:
```
calculateAllValidCellValues: function(){
var unsolvedCells = false;
//Value of current Minimum
var currentMin = {
brow: 0,
bcol: 0,
row: 0,
col: 0,
count: 10
};
//loop through all values
for(var brow=1; brow<=3; brow++){
for(var bcol=1; bcol<=3; bcol++){
for(var row=1; row<=3; row++){
for(var col=1; col<=3; col++){
if(empty(this._boardState[brow][bcol][row][col].value)){
unsolvedCells = true;
var validCellValues = this.getValidCellValues(brow, bcol, row, col);
this._boardState[brow][bcol][row][col].validValues = validCellValues;
//we want to find a maximally constrained cell
var valueCount = count(validCellValues);
if(valueCount < currentMin.count){
currentMin.brow = brow;
currentMin.bcol = bcol;
currentMin.row = row;
currentMin.col = col;
currentMin.count = valueCount;
}
//special break-early case because if we find a value count of 1 we can just go ahead
//and assign it!
if(valueCount == 1){
return this._boardState[currentMin.brow][currentMin.bcol][currentMin.row][currentMin.col];
}
}
}
}
}
}
if(unsolvedCells){
//return the maximally constrained cell
return this._boardState[currentMin.brow][currentMin.bcol][currentMin.row][currentMin.col];
}else{
//We have solved all the cells
return false;
}
},
```
In this step all the possible values are calulated and tallied, and the maximally constrained cell is returned.
Finally, we have the sub-parts of step 2 where the assignment and recurive calls are implemented:
```
/**
* if DieOnError is true, will throw an exception if
* and halt execution if an error is thrown. (This should be set to true, for the
* primary board, but not for any "cloned" sub-boards
*/
solveBoard: function(dieOnError){
try{
do{
console.log('iteration ' + (++this.iteration));
//get a maximally constrained cell
var cell = this.calculateAllValidCellValues();
if(cell === false){
console.log('Solved all cells');
break; //we solved all the cells
}
if(count(cell.validValues) == 0){
throw 'Cant find a solution';
}else if(count(cell.validValues) == 1){
//Assign the value and go to the next step
var value = reset(cell.validValues);
console.log('setting [' + cell.brow + '][' + cell.bcol +']['+ cell.row +']['+ cell.col + ']: ' + value);
this.setCellValue(value, cell.brow, cell.bcol, cell.row, cell.col);
}else{
//There is more than one possible value
console.log("More than one possible outcome. Creating Sub-boards");
for(i in cell.validValues){
var board = dojo.clone(this);
var value = cell.validValues[i];
console.log('setting [' + cell.brow + '][' + cell.bcol +']['+ cell.row +']['+ cell.col + ']: ' + value);
board.setCellValue(value, cell.brow, cell.bcol, cell.row, cell.col);
var subBoardResult = board.solveBoard(false);
if(subBoardResult !== false){
//We got a board solution
console.log('Sub-board solved all cells');
return subBoardResult;
}
}
throw 'Cant find a solution';
}
}while(true);
}catch(e){
if(dieOnError){
alert(e);
console.debug(e);
}
return false;
}
return this;
},Note how we check to see if there is a single valid value, and if not, a sub-board is spawned where each possible value for the maximally constrained cell is explored.
Finally, see it in action for yourself: