JavaScript Sudoku Puzzle Solver | 3
JavaScript Sudoku Puzzle Solver
Strategies
There are a number of distinct strategies for eliminating symbols from cells and the purpose of the iterate() code is to cycle through them one by one. Each strategy is defined by a function that takes the puzzle object as an argument and returns a numeric value to indicate the result of executing the strategy; a value of –1 indicates an error of some kind, a value of 0 indicates that nothing was done and a positive value indicates that modifications were made to the solution. The strategy functions are stored in an array as follows…
SudokuPuzzle.prototype.strategies = [
function(puzzle)
{
...
},
function(puzzle)
{
...
},
etc
];
The advantage of storing them like this is that strategies may be added or removed without needing to modify the iterate() function that calls them. Have a look at the following line of code from the iterate() function…
var nReturn = this.strategies[this.nIteration++ % this.strategies.length](this);
There’s a lot going on in this one line of code. The remainder of this.nIteration over the number of strategies is used to index into the array of strategy functions. This function is then called, passing the SudokuPuzzle object as the argument. Finally, the value of this.nIteration is post-incremented so that for the next iteration, a different strategy will be used.
Let’s have a look at the different strategies…
Strategy 1: Eliminate Dead Certs
This is the simplest and most obvious strategy and it derives directly from the rules of the puzzle; if any cell contains a definite symbol, then all other cells in the same row or column or group must not display that symbol. In other words, that symbol is eliminated from the solution sets of all the other cells in the same row/column/group set.
function(p)
{
var nReturn = 0;
clrDebug();
debug('Eliminate dead certs in row/column/group<br>');
var n = p.width * p.height;
var i,j,k;
for ( i = 0; i < n; i++ )
{
for ( j = 0; j < n; j++ )
{
// calculate group number
var g = Math.floor(i/p.height) * p.height + Math.floor(j/p.width);
// get the solution for this cell and check if it is final
var c = p.solution[i][j].c
if ( c.length > 1 ) continue;
// eliminate symbol from rest of row
for ( k = 0; k < n; k++ )
{
if ( (k != j) && p.solution[i][k].filter(c) ) nReturn++;
}
// eliminate symbol from rest of column
for ( k = 0; k < n; k++ )
{
if ( (k != i) && p.solution[k][j].filter(c) ) nReturn++;
}
// eliminate symbol from rest of group
for ( k = 0; k < n; k++ )
{
if ( (k != g) && p.members[g][k].filter(c) ) nReturn++;
}
}
}
return nReturn;
}
Strategy 2: Isolate individuals on each row/col/group
This strategy is a little more complex than the previous one. The idea is if a token appears only once in any row, column or group, then any other tokens that might appear in the same solution cell can be eliminated. Consider the following example…
|
34 |
1 |
134 |
2 |
46 |
5 |
|
2345 |
12 |
6 |
14 |
4 |
13 |
|
1 |
4 |
3 |
15 |
2 |
6 |
|
26 |
5 |
2 |
14 |
3 |
1 |
|
2456 |
3 |
245 |
456 |
1 |
2 |
|
256 |
126 |
125 |
3 |
56 |
4 |
This grid shows an intermediate state of the puzzle. Numbers in bold show the original starting position, numbers in red indicate potential symbols for a cell. Looking at the first cell in the second row (shown in italics), the symbol “5” appears only once in the top left hand group (also in the same row). It follows therefore that “5” can be placed in that cell and since every row/column/group contains a complete set of symbols, then that cell must contain the symbol “5”
function(p)
{
// look for rows/columns/groups where a token appears only once
var nReturn = 0;
clrDebug();
debug('Isolate individuals on each row/col/group<br>');
var n = p.width * p.height;
var i,j,k, t;
var tCount;
for ( t = 0; t < n; t++ )
{
// for each token
var token = p.tokens[t];
// count its occurrence in each row
for ( i = 0; i < n; i++ )
{
tCount = 0;
for ( j = 0; j < n; j++ )
{
if ( p.solution[i][j].c.search(token) >= 0 )
{
if ( tCount++ == 0 ) k = j;
}
}
// if more than one, move to the next row
if ( tCount > 1 ) continue;
// if not found, its an error
if ( tCount < 1 )
{
debug("Invalid cell state: token missing from row");
return -1;
}
if ( p.solution[i][k].c != token )
{
debug("[" + i + "]["+k+"]: " + p.solution[i][k].c + "-->" + token + "<br>")
p.solution[i][k].c = token;
nReturn++;
}
}
// columns
for ( j = 0; j < n; j++ )
{
tCount = 0;
for ( i = 0; i < n; i++ )
{
if ( p.solution[i][j].c.search(token) >= 0 )
{
if ( tCount++ == 0 ) k = i;
}
}
// if more than one, move to the next row
if ( tCount > 1 ) continue;
// if not found, its an error
if ( tCount < 1 )
{
debug("Invalid cell state: token missing from row");
return -1;
}
if ( p.solution[k][j].c != token )
{
debug("[" + k + "]["+j+"]: " + p.solution[k][j].c + "-->" + token + "<br>")
p.solution[k][j].c = token;
nReturn++;
}
}
// groups
for ( i = 0; i < n; i++ )
{
tCount = 0;
for ( j = 0; j < n; j++ )
{
if ( p.members[i][j].c.search(token) >= 0 )
if ( tCount++ == 0 ) k = j;
}
// if more than one, move to the next row
if ( tCount > 1 ) continue;
// if not found, its an error
if ( tCount < 1 )
{
debug("Invalid cell state: token missing from row");
return -1;
}
if ( p.members[i][k].c != token )
{
debug("[" + i + "]["+k+"]: " + p.members[i][k].c + "-->" + token + "<br>")
p.members[i][k].c = token;
nReturn++;
}
}
}
return nReturn;
}
Strategy 3: Look for Patterns
This strategy is quite subtle and like the previous one it relies on certain properties that emerge from the rules of Sudoku. This time, cells with incomplete solutions are matched against all the other cells in the same row, column and grid, counting the number of cells with exactly the same incomplete solution. In the example grid below, in the fourth column, there are two cells with the value “14” (marked in italics)…
|
34 |
1 |
134 |
2 |
46 |
5 |
|
2345 |
12 |
6 |
14 |
4 |
13 |
|
1 |
4 |
3 |
15 |
2 |
6 |
|
26 |
5 |
2 |
14 |
3 |
1 |
|
2456 |
3 |
245 |
456 |
1 |
2 |
|
256 |
126 |
125 |
3 |
56 |
4 |
Now, if the number of cells is the same as the number of symbols in the string, those symbols must be distributed only amongst those counted cells. In the example grid, there are exactly two cells containing the value “14” (shown in italics ) so either the first one will have the “1” and the second will have the “4” or the other way around. What's certain is that both the “1” and the “4” cannot exist in any other cell in that column. Two other cells in that column - on the third and fifth rows (underlined) - contain those symbols so they can be filtered to become “5” and “56”.
function(p)
{
var nReturn = 0;
clrDebug();
debug('Look for patterns<br>');
var n = p.width * p.height;
var i,j,k,l, tCount;
var kChar, ch, chr;
for ( i = 0; i < n; i++ )
{
for ( j = 0; j < n; j++ )
{
// calculate group number from grid coordinates
var nGroup = Math.floor(i/p.height) * p.height + Math.floor(j/p.width);
// look for incomplete cells
chr = p.solution[i][j].c;
if ( chr.length == 1 ) continue;
// search rows
tCount = 0;
for ( k = 0; k < n; k++ )
{
// count the number of cells with the same incomplete solution
kChar = p.solution[i][k];
if ( kChar.c == chr ) tCount++;
}
// if the number of cells equals the number of symbols
// then none of the symbols may exist elsewhere on the row
if ( tCount == chr.length )
{
for ( k = 0; k < n; k++ )
{
kChar = p.solution[i][k];
ch = kChar.c;
if ( ch != chr )
{
// erase the symbols from all other cells that
// have a different set of symbols.
for ( l = 0; l < chr.length; l++ )
{
ch = ch.erase(chr.charAt(l));
}
if ( kChar.c != ch )
{
// count the number of cells that get modified
kChar.c = ch;
nReturn++;
}
}
}
}
// search again with columns this time
tCount = 0;
for ( k = 0; k < n; k++ )
{
// count the number of cells with the same incomplete solution
kChar = p.solution[k][j];
if ( kChar.c == chr ) tCount++;
}
// if the number of cells equals the number of symbols
// then none of the symbols may exist elsewhere on the column
if ( tCount == chr.length )
{
for ( k = 0; k < n; k++ )
{
kChar = p.solution[k][j];
ch = kChar.c;
if ( ch != chr )
{
// erase the symbols from all other cells that
// have a different set of symbols.
for ( l = 0; l < chr.length; l++ )
{
ch = ch.erase(chr.charAt(l));
}
if ( kChar.c != ch )
{
// count the number of cells that get modified
kChar.c = ch;
nReturn++;
}
}
}
}
// search yet again, but within groups this time
tCount = 0;
var ijGroup = nGroup;
for ( k = 0; k < n; k++ )
{
// count the number of cells with the same incomplete solution
kChar = p.members[i][k];
if ( kChar.c == chr ) tCount++;
}
// if the number of cells equals the number of symbols
// then none of the symbols may exist elsewhere in the group
if ( tCount == chr.length )
{
for ( k = 0; k < n; k++ )
{
kChar = p.members[i][k];
ch = kChar.c;
if ( ch != chr )
{
// erase the symbols from all other cells that
// have a different set of symbols.
for ( l = 0; l < chr.length; l++ )
{
ch = ch.erase(chr.charAt(l));
}
if ( kChar.c != ch )
{
// count the number of cells that get modified
kChar.c = ch;
nReturn++;
}
}
}
}
}
}
return nReturn;
}
Strategy 4: Look for row or column limited symbols
In this strategy, each token in each group is analysed to see whether inside a group, a token is limited to a single column or row. Consider the example below…
|
34 |
1 |
134 |
2 |
46 |
5 |
|
2345 |
12 |
6 |
14 |
4 |
13 |
|
1 |
4 |
3 |
15 |
2 |
6 |
|
26 |
5 |
2 |
14 |
3 |
1 |
|
2456 |
3 |
245 |
456 |
1 |
2 |
|
256 |
126 |
125 |
3 |
56 |
4 |
In the bottom left group the symbol “4” appears only on one row (underlined). This implies that wherever the “4” goes in that group, it will be on that row and the logical conclusion is that it will not in any other group on that row. Using this strategy in the example grid above, the fourth column in that row containing the symbols “456” can be changed to “56”.
function(p)
{
var nReturn = 0;
clrDebug();
debug('Look for column/row limited tokens<br>');
var n = p.width * p.height;
var i,j,k,l, tCount;
var oChar, oChar2, ch;
for ( i = 0; i < n; i++ )
{
// for each group
var group = p.members[i];
for ( j = 0; j < n; j++ )
{
// for each token
var token = p.tokens[j];
var nColMin = n;
var nColMax = -1;
var nRowMin = n;
var nRowMax = -1;
// iterate over members in group
for ( k = 0; k < n; k++ )
{
// find max and min rows and columns for token
var oChar = group[k];
if ( oChar.c.search(token) >= 0 )
{
if ( oChar.nColumn > nColMax ) nColMax = oChar.nColumn;
if ( oChar.nColumn < nColMin ) nColMin = oChar.nColumn;
if ( oChar.nRow > nRowMax ) nRowMax = oChar.nRow;
if ( oChar.nRow < nRowMin ) nRowMin = oChar.nRow;
}
}
// if token not found in group, error!
if ( (nColMax == -1) || (nRowMax == -1) )
{
clrDebug();
debug("Invalid cell state");
return -1;
}
// if token is limited to one column
if ( nColMin == nColMax )
{
// remove token from this column in all other groups
for ( l = 0; l < n; l++ )
{
oChar2 = p.solution[l][nColMin];
if ( oChar2.nGroup == i ) continue;
ch = oChar2.c.erase(token);
oChar2.c = ch;
if ( oChar2.c != ch )
{
debug("[" + l + "]["+ nColMin +"]: " + ch + "-->" + oChar2.c + "<br>");
nReturn++;
}
}
}
// if token is limited to one row
if ( nRowMin == nRowMax )
{
// remove token from this row in all other groups
for ( l = 0; l < n; l++ )
{
oChar2 = p.solution[nRowMin][l];
if ( oChar2.nGroup == i ) continue;
ch = oChar2.c;
oChar2.c = ch.erase(token);
if ( oChar2.c != ch )
{
debug("[" + nRowMin + "]["+ l +"]: " + ch + "-->" + oChar2.c + "<br>");
nReturn++;
}
}
}
}
}
return nReturn;
}
Demo
To see the SudokuPuzzle solver in action click here
Source Code
Copy the following code and save as SudokuPuzzle.html
Conclusion
In this article I've created a JavaScript Sudoku puzzle solver program. The program allows a user to enter any size of puzzle and starting position and the solver will search for the solution. Four separate solver strategies were shown and when used in combination, solved all of the Sudoku puzzles I was able to test.
Disclaimer
While I have endeavoured to make this code as browser compatible as possible, it's only been tested it with Internet Explorer (6.0) and Netscape (7.1) as these browsers are used by a large proportion of users.
About the Author
Guyon Roche is a freelance web developer in London, Great Britain. He specializes in Windows platforms with an interest in bridging the gaps between different technologies, visit www.silver-daggers.co.uk for more details. He can be reached via e-mail at guyonroche@silver-daggers.co.uk
Created: March 27, 2003
Revised: October 21, 2005
URL: https://webreference.com/programming/javascript/gr/column16/1
Find a programming school near you