Sudoku Solver
Solves a Sudoku grid using magic, recursion, and 140bytes of brute force.
This 140 bytes JavaScript Sudoku Solver was inspired and built on top of the itsy bitsy shoulders of the smallest sudoku solvers in Perl (120b), Ruby (122b), Python (178b), ...
It was a fun project. Reading the source code of the smallest sudoku solvers in various languages taught me a few trick about these languages and clearly showed the most compact strategy: brute force recursion. Also it lead me to think that 140b was not an unrealistic target for JavaScript.
The very first working solver I wrote was 166 bytes. It was clear then that 140b was within reach with a bit of work and a hand or three to golf the last few bytes.
Credits
The credits go this way:
- 166b @p01 .......... initial implementation
- 147b @p01 .......... initial golf
- 146b @qfox ......... loop optimization
- 145b @qfox ......... output with closured callback
- 140b @p01 .......... output with hijacked Array.prototype.toString()
- 141b @maksverver ... fixed the glitchy j^i==j test
- 140b @fgnass ....... ReferenceError exit trick + cross browser fix
Thanks to everyone who helped golf and fix this puppy.
You can find the original gist on github to check the different revisions and the test page.
Source code
function R(a,i,j,m,g){for(i=80;a[i];i--||A);for(m=10;g=a[i]=--m;g&&R(a))for(j in a)g*=i==j||a[j]^m||i/9^j/9&&i%9^j%9&&i/27^j/27|i%9/3^j%9/3}
That's it. This puppy takes an array as of 81 ( 9 by 9 ) numbers as argument with 0
for the empty cells, and throws an exception when the grid is solved. Then you can access the array you passed and see the solution. Also this function does not pollute the global scope.
Annoted source code
Note that this function is written in ES3. It can be shorten by using ES5's Array.indexOf
method.
function R
(
a, // the array representing the sudoko grid
// placeholder arguments
i, // index of the last empty cell
j, // index to check the candidates in 'i'
m, // candidate number for the the cell 'i'
g // flag whether 'm' is a already used in the
// same row|col|node as 'i'
){
// phase 1: look for an empty cell
for
(
i=80;
a[i]; // keep going if the cell isn't empty
i--||A // decrease the index and throw a
// ReferenceError exception if we went
// through the whole grid
);
// phase 2: check all candidate numbers
for
(
m=10;
g=a[i]=--m; // put the candidate in the cell
// 'i' already and set 'g' to
// something truthy at the end of
// phase 2, the cell 'i' is reset
// to 0 for "higher" branches of
// the recursion
g&&R(a) // recurse if 'm' isn't already
// used in the same row|col|node
// as 'i'
)
// phase 3: is the candidate number used already ?
for(j in a) // loop through the whole grid
g*= //
j==i // skip the cell 'i'
|| // turn 'g' falsy if
a[j]^m // the cell 'j' is set to 'm'
|| // and 'i' and 'j' are in the same
// row|col|node
i%9^j%9&&i/9^j/9&&i/27^j/27|i%9/3^j%9/3
}
Usage
var testGrid = [0,0,0,1,5,0,0,7,0,1,0,6,0,0,0,8,2,0,3,0,0,8,6,0,0,4,0,9,0,0,4,0,0,5,6,7,0,0,4,7,0,8,3,0,0,7,3,2,0,0,6,0,0,4,0,4,0,0,8,1,0,0,9,0,1,7,0,0,0,2,0,8,0,5,0,0,3,7,0,0,0];
var myFunction = function R(a,i,j,m,g){for(i=80;a[i];i--||A);for(m=10;g=a[i]=--m;g&&R(a))for(j in a)g*=j==i||a[j]^m||i%9^j%9&&i/9^j/9&&i/27^j/27|i%9/3^j%9/3};
try
{
myFunction(testGrid);
}
catch(e)
{
alert(testGrid);
}