SUDOKU SOLVER

609 words ~ 3-6 mins

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:

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

Other recent experiments

There are many experiments and projects like SUDOKU SOLVER to discover other here.

Let's talk

Don't be shy; get in touch by mail, twitter, github, linkedin or pouet if you have any questions, feedback, speaking, workshop or performance opportunity.