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