What`s inside, some mathematical stuff
There are srong connections between between group theory in mathematics and sudoku. In fact, the completed sudoku puzzle is a latin square (discovered by Euler), that is the structure of a quasigroup, with the additional constraint of 3x3 boxes.
That's why the use of numerals in sudoku puzzles is just a convention: in quasigroups and groups the element can be the elements of any set!
For the program algorithm I used a graphbased rappresentation of the board. In fact you can think that every cell is a node and it is linked with the cells that are in its row, column and box. So when a cell is connected directly with another it can not contain the same number that the other cell contains (this is the constraint).
In fact the problem of sudoku solving has become a graph coloring problem.
The rows, columns and sub boxes are found by the program since they are the strongly connected components of the graph.
Here is the pseudocode of my algorithm (base guideline, does not contain optimizations) (see source for more)
For every cell see what's linked and place a flag if it can contain each number or not
Find the cell with the lowest acceptable numbers nn
Find the strongly connected subgraph that has the least candidates (lc) for a value (deprecated, not worth)
Select n as the lowest between lc and nn
if (n lower than 0) error
if (n==1) write down and new SudokuSolve() call
if (n greater than 1) recursive fork with all possibilities
it works! (in testing it filled 3000 puzzles/second)
To create playable puzzles, first I call SudokuSolve on a blank puzzle, and then I remove numbers cheching each time (with dynamical programming optimizations) that the puzzle has only one solutions (for the last difficulty level I remove a couple of numbers more).
Francesco Rossi
