JavaScript Sudoku Puzzle Solver

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…

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.

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 ');

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 ');

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 + " ")

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 + " ")

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 + " ")

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 ');

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 ');

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 + " ");

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 + " ");

nReturn++;

}

return nReturn;

}

Demo

Source Code

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.