Technical details


I designed Sudoku Solver in C++. It uses both my own math library and the SFML 1.6 library for the graphics part. My math library allows me to handle matrix, its columns and its rows very easily, and to sort arrays. (Those are the main functions I used.) The SFML was only for the graphics part, which includes creating the window, drawing onto it, and handling user inputs (mouse and keyboard).

Operating principle


Sudoku Solver solves every sudoku immediately, which is due both by the fastness of C++ and the algorithm I used. Sudoku Solver does not use a very smart algorithm: it won't solve it in the way you do. It doesn't try to deduce which number goes in which case by using logical rules, as a human would. It doesn't try every possibility randomly either, otherwise it wouldn't be that fast. Here is the trick: it does try every possibility, but it tries the solutions which are more likely to come true first. This is called backtracking.

Backtracking


Backtracking is a theory made to solve some particular problems, where the solution is very hard to find logically, even though a solution must respect some logical rules. And the Sudoku problem is one of those. You must indeed have in every block, row, and column of the sudoky only one occurrence of each figure (from 1 to 9).

Sudoku Solver starts building a solution (i.e. fills the grid) with numbers, by respecting those logical constraints. When it has to put a number into a case, it doesn't pick up the case randomly amongst the blanked ones. It chooses the one which has the minimum of possibilities (for instance if it has the choice between a case where only two numbers are available, and one with four, it will choose the first one).

If it occurs that it cannot build the entire solution (i.e. there is a case in which no numbers are available, because none of them respect the logical constraints), then Sudoku Solver will go backward, changing the last number it wrote by another one, and tries to continue.

Read more about backtracking.

Algorithm


Aside is a simplified version of the actual algorithm which solves the sudoku, written in a human-readable language.

To understand this you must know that pos is a vector with a row component and a column component, and tells the position of a case in the sudoku grid.

pos is also an element of an array which stores every position in the sudoku grid. This array is sorted so we can build a solution quickly. (The less possibilities there are for a case, the more this case is at the head of the array.)

You also need to know that a sudoku is divided in columns (9), in rows (9), and in 3x3-squared blocks (9). So the block variable tells us which block pos is in. (row, column and block are between 0 and 8.)

recursive_solve (Position pos) -> boolean {
    if the whole grid has been filled then
        return true
    end if
    let column = pos.column, row = pos.row, block = ((column / 3) * 3) + row / 3;
    for i from 1 to 9
        if the number i is not in the column column, nor is the row row, nor in the block block then
            Set i in the grid at (row, column)
            Let p be the next position after pos
            if recursive_solve(p) then
                return true
            end if

            Set 0 in the grid at (row, column)
        end if
    end for
    return false
}


Copyright © 2012-2017 Sébastien Bini, all rights reserved. Please report any problem.