# 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 Dancing Links 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.