Sudoku solver: pencil marks & recursive patience

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 33 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 num

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 NN. N and NN are effectively constants... you should have a second global variable GRIDSIZE = ZONESIZE ZONESIZE, and then replacing all the NN 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




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 n1 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:v1,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

StackExchange Code Review Q#37517, answer score: 7