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).

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 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.

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.)

if the whole grid has been filled then

return true

end if

let

for

if the number

Set

Let

if

return true

end if

Set 0 in the grid at (

end if

end for

return false

}

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