Sudoku solver: pencil marks & recursive patience

Question

Here is my attempt at Weekend Challenge #3.

Out of scope:

• It only will do 9*9
• It will stop at the first solution
• Could have been smarter at re-using the cache when recursively calling solveGrid
• I ignored OO as this is not an app, but a simple script

In scope:

• Bitflags & cache for pencil marks

var grid = "...84...9\n" +
           "..1.....5\n" +
           "8...2146.\n" +
           "7.8....9.\n" +
           ".........\n" +
           ".5....3.1\n" +
           ".2491...7\n" +
           "9.....5..\n" +
           "3...84...";

var N = 3, //Changing N wont do much, solvedValues would have to be updated as well
    impossible = 511, //parseInt("111111111",2)
    solvedValues = 
    { 
      510 : 1, //parseInt("111111110",2)
      509 : 2, //parseInt("111111101",2)
      507 : 3, //parseInt("111111011",2)
      503 : 4, //parseInt("111110111",2)
      495 : 5, //parseInt("111101111",2)
      479 : 6, //parseInt("111011111",2)
      447 : 7, //parseInt("110111111",2)
      383 : 8, //parseInt("101111111",2)
      255 : 9  //parseInt("011111111",2)
    };

/* Create a grid array from a string */
function createGrid( s )
{
  return s.split("\n").map( function(v)
  { 
    return v.split("").map( function(v)
    { //Each cell is an array [value, pencilmarks as binary bitflag ]
      return [v=="."?0:v*1,0]; //Dots or 0 are accepted as blanks
    }); 
  });
}
/* Create a string from a grid array */
function createString( grid )
{
  return grid.map( function(row){ return row.map( function(v){ return v[0]; } ).join(""); } ).join("\n");
}
/* Determine which 3*3 zone a given location belongs to */
function deriveZone( x , y )
{
  return Math.floor( x / N ) * N + Math.floor( y / N );
}
/* Create a cache, to make addToCache cleaner, I preset the values to 0 */
function Cache()
{
  this.rows  = []; /* What numbers are already used in a given row    */
  this.cols  = []; /* What numbers are already used in a given column */
  this.zones = []; /* What numbers are already used in a given zone   */
  for( var i = 0 ; i < N*N ; i++ )
  {
    this.rows.push(0);
    this.cols.push(0);
    this.zones.push(0);
  }  
}
/* Add a data point to the cache */
function addToCache( cache , x , y , value )
{
  value--; // Value 1 would be shifting 0 times to the right etc.
  cache.rows[x] |=  1 << value;
  cache.cols[y] |=  1 << value;
  cache.zones[deriveZone( x , y )] |= 1 << value;
}
/* Collect a cache of all numbers, assign them to their respective rows and columns */
function buildGridCache( grid )
{
  var cache = new Cache(), x, y ,value;

  for( x = 0 ; x < N*N ; x++ )
    for( y = 0 ; y < N*N ; y++ )
      if( value = grid[x][y][0] )
        addToCache( cache, x , y , value );

  return cache;
}
/* Cache what we know, analyze each cell in the grid, see if anything comes up */
function solveObvious( grid , cache)
{ 
  var redo, x, y;

  if( !cache )
    cache = buildGridCache( grid );

  for( x = 0 ; x < N*N ; x++ )
    for( y = 0 ; y < N*N ; y++ )
      if( !grid[x][y][0] )
      {
        grid[x][y][1] |=  cache.rows[x] | cache.cols[y] | cache.zones[ deriveZone(x,y) ];
        grid[x][y][0] = solvedValues[ grid[x][y][1] ] || 0;
        if( grid[x][y][0] )
        {
          addToCache( cache , x , y , grid[x][y][0] );
          redo = true;
        }
        else if( grid[x][y][1] == impossible )
          return false;
      }
  if(redo)
    solveObvious( grid , cache );

  return true;
}
/* Is there a cell that still has value 0 ? */
function findUnsolved( grid )
{
  var x, y ;
  for( x = 0 ; x < N*N ; x++ )
    for( y = 0 ; y < N*N ; y++ )
      if(!grid[x][y][0] )
        return grid[x][y];
}
/* Solve the grid, if solving all obvious cells is not enough, try recursive guessing */
function solveGrid( grid )
{
  var possible  = solveObvious( grid ),
      unsolved  = findUnsolved( grid ),
      newGrid, i;

  if( possible && !unsolved )
    return grid;

  if( unsolved )
    for( i = 0 ; i < N*N ; i++ )
      if( unsolved[1] != ( unsolved[1] |= 1<<i ) && ( unsolved[0] = i+1 ) )
        if( newGrid = solveGrid( JSON.parse( JSON.stringify( grid ) ) ) )
          return newGrid;

  return false;
}
/* Parse a grid string, return a grid string if the grid is solved */
function solve( s )
{
  var grid = solveGrid( createGrid( s ) );
  return grid?createString( grid ):"The puzzle is unsolvable: it has no solution";
}
/* Test case */
console.log( solve( grid ) );

Answer 1

All in all, an interesting approach to the problem, and seeing JavaScript used in such an efficient way is a pleasure (stick it to all those people who think JavaScript is ... ).

I have the following small criticisims of the code (nothing can be perfect, right?)...

Variables

• You declare var N = 3 but:
  • N is a poor variable name choice. In this case, it represents a 'zone dimension'. A name something like ZONESIZE would be better
  • all references to N (except 1 line) perform the square of N*N. N and N*N are effectively constants... you should have a second global variable GRIDSIZE = ZONESIZE * ZONESIZE, and then replacing all the N*N with GRIDSIZE would be better.
• your Cache class consists of rows, columns, and zones, but, when you access the multi-dimensional arrays containing the Cache (and other data), you use variables called x and y. I personally like short variable names like this, but I would choose r and c instead. many lines would be affected by this, for example, if( value = grid[x][y][0] ) ... would become if( value = grid[r][c][0] ) .... Similarly, cache.rows[x] |= 1 << value; becomes cache.rows[r] |= 1 << value;

Details

• in your createGrid function, you nested-map the string input to the multi-dimensional grid output. This method is 'elegant', but I would prefer the more explicit numeric conversion of the String to a Number. You do n*1 for the conversion, but Number(n) would be more structured. Also, putting a space after the array-member comma (and other places) would make it more readable, the line return [v=="."?0:v*1,0]; becomes return [v == "." ? 0 : Number(v), 0]; (P.S. re-reading this comment, I count 11 characters of 'punctuation' in that line - [==""?:*,]; , and just 6 characters of 'value' - v.0v10)
• in your createString method, which converts the solution back to a String, you should use the same form of indenting that you use in the createGrid method. Writing it all as a 1-liner is not helpful.
• in deriveZone ... see my comment about N, which should be ZONESIZE or some better-named variable. As an aside, it may be a nice option to pre-compute the zones for a row/column combination in a separate 2D array, and then your method can become a simple return zone[x][y];
• in buildGridCache you have the line if( value = grid[x][y][0] ). I know this is logically correct, but, the multiple levels of logic here, the assignment, as well as the logical condition of the assignment are more complicated than should be present on a 1-liner. Visibly it looks like a 'classic' bug pattern. Even though it is redundant, I would prefer to make the different 'stages' of execution more visible, say if( (value = grid[x][y][0]) != 0 ), or value = grid[x][y][0]; and if (value) ...
• in solveObvious you 'fake' a data structure in the grid by having a 2-member array in the last dimension. The first member of the array is the 'solution value', and the second member is the 'pencil marks'. You repeatedly reference these two members as grid[x][y][0] and grid[x][y][1] respectively. These 0 and 1 constants (magic numbers) should be decalred as 'globals' with a meaningful name, like grid[r][c][SOLUTION] and grid[r][c][PENCIL]

All in all, the only things i can find to criticize are some naming conventions, formatting, and some pedanticness that is really minor. It's a great solution to the problem. Thanks