Tech » Sudoku

About – Usage – Change Log – Issues – Algorithm – Details

Yet another sudoku online

---

Usage

---

... should be pretty simple.
Click on the link above and enter numbers in the free cells. User mouse or cursor-keys to navigate.

Click on the "Help..." section at the bottom of the game to get some more info.

Change Log and previous releases

---

Known Issues

---

1. Not tested well. Especially support for other browsers than mentioned above may be poor.
2. New games are not guaranteed to have an unique solution. This should be addressed by an improved game generation algorithm (see below).

The Algorithm

---

Glossary

board

Grid of 9x9 cells

cell

One single field in the board

move

Entering a possible value into a cell.

region

Subgrid of 3x3 cells

related cells

For one given cell: all cells that are located in the same row, column or region.
Any cell has 20 related cells: 8 in the same row, 8 in the same column, 8 in the same region (4 duplicate cells can be removed).

position

A grid with its 81 current values

possible value

A digit that may be entered into a cell without breaking the rules.

value

The value of a cell can be a digit (1..9) or 0, if the cell is empty

Data Model

The implementation uses two classes:
CYasonPos defines one board with it's current cell values. Also the algorithmns for creating and soving puzzles are implemented here.
CYason defines hi-level functions to display and control the game.

The current value of every cell is stored in an array. Possible values are (0..9), 0 meaning 'empty'.
This is also the string representation.

The application keeps track of allowed values for every (empty) cell.
For an empty board, all digits are allowed for every cell. As soon as one digit is entered, this digit is no longer allowed in all related cells.
(Use the "Cheat... \ Show/hide hints" to display the possible values for every cell.)

CYasonPos {
    var aVal[81];    // current value of every cell (0..9), 0 means 'empty'
    var aOpts[81[9]; // current is-allowed-status for every digit for every cell
    [...]
    solve();
    [...]
}

Creating new puzzles

We start with a valid solution ('seed'), and apply a number of random, non-destructive transformations.
'Non-destructive' are transformations that do not turn a valid position into an invalid position. Examples are mirroring along vertical, horizontal and diagonal axis, rotation aboubt 90° and swapping rows (or columns) that share the same regions.

From the newly created valid random solution, we can now remove values, to create a new puzzle.
The number of empty cells depends on the desired level of difficulty.

As a side effect, this approach also gives the solution, so we don't need an algorithm here.

Trivial and Simple Moves

The box below shows a region of a sudoku board, with four cells already filled. The gray numbers in the empty cells list all possible digits that are allowed.

If a cell has only one possible value left, I call this a Trivial Move. In this example '4' and '9' are trivial moves. If any digit is only allowed in one of the nine cells of a row (or column or region), then this is a Simple Move. '5' is a simple move.

Trivial and Simple Moves can always be done without breaking a rule or impacting the solveability of the puzzle.
Since any move may produce new possible simple moves, they are applied repeatedly until no more value could be set. For example performing the trivial move '4' in the lower left corner will create a new trivial move '2' in the cell above.

Some puzzles of easy or intermediate levels may be solved by simple moves alone.

Solving / Backtracking

Since we know the solution for every puzzle in advance (see sction 'Cretaing new puzzles'), a solution algorithm is not really required. But - hey, this is why I started this little project.
Also, the solving algorithm can be used to solve manually entered puzzles or to check if a new puzzle has only one unique solution.

I use a simple backtracking algorithm here. When simple moves don't bring a solution, we pick a cell with the smallest number of possible values. Then we try them one by one until a solution is found.

Simplified:

_solve: function() {
    // do all trivial and simple moves first
    while ( this.simpleMoves()>0 )
        ;
    if ( this.isSolved() )
        return true;
    // pick one cell with a minimum number of possible values
    var tryList = this.getTryList();
	// remeber current position
    var savePos = new CYasonPos (this);
    // try the possible moves one by one
    for (var i=0; i<tryList.aMoves.length; i++) {
        this.setValueAt (tryList.idx, tryList.aMoves[i]);
        if ( this._solve() )
            return true;
        // reset and try next option: 'Backtracking'
        this.copyFrom (savePos);
    }
	// none of the tried moves was successfull: the current position is not solveable!
    return false;
}

Some Implementation Details

---

Optimizations

(todo)

Genreral JavaScript

Some random issues about JavaScript programming.