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


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.


  • 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.



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

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){
        //everything in the column
        if(row != i){
    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.


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

(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);
            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.


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
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.