# sudoku /

Filename Size Date modified Message
7.3 KB
1.3 KB
5.8 KB
5.7 KB
5.4 KB
2.0 KB
2.9 KB

# sudoku!

A history of free-time sudoku development. Created to squash the urge to ever do
a sudoku by hand. Sudoku's rules are simple.
See Peter Norvig's Solving Every Sudoku Puzzle
for a general idea of how to solve them programmatically.

## Limitations

• If a puzzle is unsolvable, there's no feedback as to why.
• If there is more than one solution, the solver stops after finding the first.

## Evolution

### sudoku-bigmodel-cloned.html

My first attempt included a literal translation of the possible sudoku outcomes -
81 cells with the nine possible values marked true (still possible) or false
(eliminated).

To mark a value x, every other value in its cell is eliminated. x is
then eliminated in every other cell in the row, column, and section/block/region.

```function markImpl(row,col,val,m){

var v = (1 * val) - 1;

for(var i=0;i<9;i++){

//everything else in the cell
if(v != i){
m[row][col][i] = false;
}
//everything in the row
if(col != i){
markOne(row,i,v,m);
}
//everything in the column
if(row != i){
markOne(i,col,v,m);
}
}
m[row][col].marked = 1;

//everything in the 'section'
var srow = Math.floor(row / 3) * 3;
var scol = Math.floor(col / 3) * 3;
for(var i = 0; i < 3; i++){
for(var j = 0; j < 3; j++){
if(srow + i != row && scol + j != col){
markOne(srow + i,scol + j,v,m);
}
}
}
}
```

To solve the puzzle, create a model and eliminate the first non-eliminated
value in the first unsolved cell. The remaining cells are solved by recursively
cloning the model and eliminating the first non-eliminated value in the next
unsolved cell. If no valid elimination remains, the recursion unwinds and tries
the next non-eliminated value.

As you might imagine, this approach is slow. At its deepest, the model is cloned
80 times. That's 81 cells * 9 values * 81 models, or 59049 booleans to solve a
simple puzzle. In addition, marking a single value involves three loops and five
comparisons. I added small optimizations to avoid locking IE:

• track the possible values remaining (marked) to avoid scanning the
array on each operation.
• when eliminating values, do a secondary elimination when only one value remains
in a value array (versus waiting for the recursive step)

Regardless, this approach stinks.

### sudoku-smallmodel-cloned.html

My first improvement came from an article on the
eight queens puzzle.
The author (I can't recall the source) noticed that students usually modeled the
problem with a literal and naive two dimensional array where each cell represents
a square on the chess board. Since each column and row can contain only one queen,
you can shrink the model by using a column array and row array where each cell
indicates the queen's position in that column or row. (that's 8 + 8 data items versus
8 * 8 in the two-dimensional array). Dijkstra went one better and
showed you can represent positions with a single
array

(that's 8 items) where x[i] is the column in which the queen at row i resides.

Since I was using a literal and naive model, I figured I could shrink it. The
easiest reduction was to use three arrays, one per possible values in a row,
column, and section/block/region. To avoid scanning arrays, I also added a two
dimensional array to represent a cell's current value. All together, I could
represent the current state with 324 data items versus 512. Not great, but better.

Marking a value x doesn't require iteration. Simply flip the boolean per row,
column, and section. Then set the solved cell to x.

```model.solved[row][col] = x;
model.rows[row][x] = false;
model.cols[col][x] = false;
model.sect[sect][x] = false;
```

Solving works as before: recursively eliminate possibilties in cloned
representations until you find a solution.

```function brute(index, m){

if(index == 81){
return m;
}

var i = Math.floor(index / 9);
var j = index % 9;

if(m.solved[i][j] > -1){
return brute(index + 1,m);
}

var sect = section(i,j);

for(var k=0;k<9;k++){
if(m.rows[i][k] && m.cols[j][k] && m.sect[sect][k]){
var clone = \$.extend(true, {}, m);
mark(i,j,k+1,clone);
var result = brute(index + 1,clone);
if(result != null){
return result;
}
}
}
return null;
}
```

This approach is better - marking values is much faster and the model is smaller
- but it still leaves me cold.

### sudoku-smallmodel.html

The next improvement was indirectly inspired by Donald Knuth's
algorithm. It turns out there's a cottage industry dedicated to solving sudoku
with Dancing Links. Jonathan Chu's
explanation
is excellent.

While studying Dancing Links and Exact Cover
problems, I realized a key property of Dancing Links is easy reversibility.
This allows solution searching and backtracking on a single model. An operation
on my first model is not easily reversible because you have to scan rows, columns,
and sections to guarantee a value is not eliminated by more than one constraint.
This isn't a problem on my latest model. As long as you're careful not to mark
a value that's already marked, when x is marked it can be easily reversed:

```//rollback changes
model.solved[row][col] = -1;
model.rows[row][x] = true;
model.cols[col][x] = true;
model.sect[sect][x] = true;
```

With reversibility, the recursive search can be re-written without cloning the
model. This has several positive side-effects:

• Code is simplified
• The space required to compute a solution drops from a worst case 59049 data
items to 324
• It's fast

Dancing Links boasts impressive performance because of its unique representation
of options and constraints. Still, in the typical "hard" sudoku puzzle with
26 values pre-determined, my simple model and recursive search performs well
enough. It has the added benefit of being extremely easy to follow and use.

### sudoku.js, sudokuUI.js

My final product (sudoku isn't actually that interesting, so I don't imagine
continued development) fixes a few glaring problems in my prototypes:

• Eliminates the one big ugly HTML file with embedded JavaScript
• Separates the solver from the UI
• Reduces JavaScript global namespace pollution
• Fixes a bug that allowed an invalid state to be loaded (the same value in a
row, column, or section). This caused the solver to hang as it futility searched
for a solution with the remaining options.