
Tech » SudokuAbout – Usage – Change Log – Issues – Algorithm – Details This is work in progress.
Let me know, if you find bugs or improvements. Yet another sudoku online

Yason is a free online Sudoku game.
Planned:

... should be pretty simple.
Click on the link above and enter numbers in the free cells. User mouse
or cursorkeys to navigate.
Click on the "Help..." section at the bottom of the game to get some more info.
20061007 
v0.9 
First preview release 
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 hilevel 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 isallowedstatus for every digit for every cell [...] solve(); [...] }
We start with a valid solution ('seed'), and apply a number of random,
nondestructive transformations.
'Nondestructive' 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.
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. 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. 
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.
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; }
(todo)
Some random issues about JavaScript programming.