project ksudoku-sudoku app for kde

#316619895

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 graph-based 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)

SudokuSolve()

Check puzzle validity

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