My personal sudoku solver implementation using OCaml (released under MIT licence).
The code and outputs are in french, sorry about that!
I wrote this sudoku solver in December 2007 to see if my personal "manual" algorithm to solve sudokus was enough to solve the sudokus provided by the newspapers. Since I was too lazy to do it by hand, I implemented my algorithm in OCaml since the computer is much faster than I can be :)
My algorithm is as follow: suppose that you have a line like this
|1| | |5| | |6| | |
then I know that the number in every other cell of the line must lie in the set
{2,3,4,7,8,9}
By taking into account the constraints also coming from columns and sub-grids, we might get some constraints informations like this in the line:
|1|{2,3,4}|{2,7,8,9}|5|{3,4}|{4,7,8}|6|{8,9}|{2,3}|
Now look at the union of the constraints on cells 2, 4 and 9, we only
have the 3 possibilities {2,3,4}. But since this is for only 3 cells, we
know that the values 2, 3 and 4 can only appear on these cells. So we
may update the constraints of the other cells:
|1|{2,3,4}|{7,8,9}|5|{3,4}|{7,8}|6|{8,9}|{2,3}|
More generally, if the union of the constraints of n cells in the line is a set of cardinality n, then we know that the values of every other cells in the line cannot be in this set. (If the set if of cardinality strictly smaller than n, then of course the Sudoku is not resolube!)
This generalize the simplest sudoku solving methods called naked singles (which corresponds to n=1) and hidden singles (which corresponds to n=8). This technique seems to be known under the name naked/hidden subsets.
Another "manual" algorithm that I use, is what I call forced cells: suppose that the constraints of the first line look like this
|3|{2,4}|5|{1,6,7,9}|{3,4,7}|{7,8,9}|{2,6}|{8,9}|{6,8,9}|
then you can see that the value 7 can only appear in the top middle
block. Therefore, you know that in the top middle block the value 7 is in
the first line. Therefore you can remove 7 in the second and third lines
of the top middle block.
This give relations between blocks and lines, and between blocks and
columns. Unlike the previous algorithm based on subsets, this work only for
the specific topology of the standard sudokus, while the implementation can
be used for more general sudokus. Therefore you can switch it off by
passing the -nf option.
Now, sometime these two algorithms are not enough to solve a sudoku. In this case we have to use backtracking: we guess the value of a cell, and try to solve the sudoku (eventually using backtracking again: when we have guessed n values, I will say we are in backtracking depth n). We iterate through all possible values of the given cell.
Computers are very good at backtracking, and in fact the simplest solver
that you can write is one that only do backtracking, and only checks when
there is an obvious contradiction to the sudoku rules. I have implemented
one in the code: complete_sudoku, you can see how short it is in the
source code.
But humans are very bad at handling backtracking. A more human way of doing something similar to backtracking would be to make a guess of a value, and use it to update the list of constraints. An easy example is if the value chosen lead to no solutions when using the above two algorithms (subsets and forced cells), then we know that this value is not possible, and we can update the constraints by removing the value. If this is still not enough to solve the sudoku using only one guess at a time, we will allow the program to make another guess after the first one to see if the sudoku has a solution or not, and so on... (I will call that the recursive depth to distinguish it from the backtracking depth, it will be of level n when the program can make up to n guess).
A more efficient way to update the list of constraints is, rather than using the above two algorithms to check if the sudoku has no solution, is we use them and see what new constraint list we get for the value we have guessed. We do that with every possible in the cell, and then we know that the constraint list has to be in the union of all possible constraints list for each possible values of the cell.
Maybe an example will be more clear: suppose that the constraint list for
cell A is {1,3}, and the one for cell B is {4,5,6,7}. Now suppose that
when we fix A to be 1, we get {4,5} for the updated constraint list in
B, and when we fix A to be 3 we get {5,7} for B. Then we know that the
constraint list for B has to be {4,5,7}.
Virtually all sudoku solving methods described in sudoku sites are specific examples of subsets and forced cells with a recursive depth of 1. I will call a sudoku to be of depth n if it requires the algorithm to go up to recursive depth n to solve it. One can assume that depth 2 sudokus would be extremely hard to solve by humans, while sudokus of depth 0 should be relatively easy.
Most of the examples coming from newspapers I tested were of depth 0, but some were of depth 1. Generating 10000 random sudokus, around 1/3 were of depth 0 while the rest of depth 1. Depth 2 Sudokus are very rare, but they do exist. Check ex-sudos for some examples. I don't know of any sudoku of depth 3.
The OCaml implementation use what I call iterators: they are OCaml objects
that have a begin, next, out_of_bounds and category methods.
Category can be either a block, line or column and is mostly used for
verbose output. I use the iterators to iterate through all lines, columns
and blocks of the sudoku, and also to iterate through all cells inside a
line, column or block.
This completly generic implementation makes it very easy to modify the code
to solve sudokus which are not 9x9 cells, or even sudokus of dimension
greater than 2, or even sudoku with satisfy other constraints than the ones
for lines, columns and blocks.
ocaml sudoku.ml sudoku.txt
sudoku.txt should contain a list of numbers (one by cell), where 0 or .
represent the empty cell. Every other character is ignored, which allow to
put sudoku.txt in a nice ascii-art format (see the examples in ex-sudos to
see some sudokus you can input to the program). If you pass no arguments,
then sudoku.ml will listen to the standard input.
The interpreter can be quite slow with hard to solve sodokus that require
backtracking, so you can also compile sudoku.ml using the bytecode ocamlc
compiler or the native code ocamlopt compiler. Consider adding the
-unsafe option to turn off array accesses checks, since the sudoku.ml
code use a lot of these, this option speeds it up a lot.
ocamlopt -unsafe -o sudoku sudoku.ml
./sudoku sudoku.txt
-b
: Set the backtracking method
- 0: don't do recursion or backtrack
- 1: don't do recursion, only backtrack
- 2: do recursions. Backtracking will then not be needed except when the
sudoku has multiple solutions (and hence is not a true solution). In
this case
-b 1will print the solutions much faster because a recursion is a lot more intensive than a backtrack - 3: do recursions, but once at level n, handle all cells at this level
rather than going back to level 0 as soon as we have found a new
constraints (this will usually be faster, but a human solving the
sudoku would usually work like
-b 2than-b 3). - 4: like
-b 2, but store the constraints found during the recursion for a time/memory trade-off (which will only happen when the algorithm need a depth 2). - 5: like
-b 3, but store the constraints found during the recursion for a time/memory trade-off (which will only happen when the algorithm need a depth 2). - Add 10 if during recursion, you do not want to use the full recursion power described in the algorithm (taking the union of the constraints found), but only to check if a value give a non solvable sudoku.
- Add 400 if you want only to do recursions, not backtracking (such if a
sudoku has multiple solutions, they won't be found). Note that
-b 401will be similar to-b 0. Redondant avec les resultats intermediaires, surtout si on backtracke tout de suite Rajouter 400 pour ne pas backtracker une fois qu'on a fini les essais. -b 401 est similaire à -b 0...";
-f/-nf
:Use/Don't use forced cells.
-bo min/max/no
:Which cell to use for recursion/backtracking (min number of constraints, most number of constraints, the first one we find).
-o/-no
: Count/Don't count the number of operations
By defaut the program output the backtracking and recursive depth, the number of iteration (one iteration consist of applying the subsets and forced cells algorithm to every iterators), and the number of operations (how many subsets of length n were used, and how many forced cells).
-ab/-nab
: Print/Don't print extra informations during backtrack.
(You can get more info by adding 100 to -b to print the best looking result
before backtracking, 200 to print the best looking constraints before
recursion, and 300 for both to print both. A bit redondant if -ai is
also enabled).
-ad/-nad
: Print/Don't print extra informations during recursion
-ar/-nar
: Print/Don't print intermediate solutions found during backtracking
-ari/-nari
: Print/Don't print intermediate solutions found during recursion
-ai/-nai
: Print/Don't print the current looking sudoku at each step
-ac/-nac
: Print/Don't print the current constraints at each step
-ao/-nao
: Print/Don't print the number of opeations during each step (if -no, only print the number of iterations made)
-i
: Equivalent to -ai -ad -ao -ari
-ni
: Equivalent to -nai -nad -nao -nari
-quiet
: Only print the solution
(Activates -ni -nar -nac -nab and suppress some informative messages)
The defaut command line is -b 2 -f -bo min -o -ar -ab -ni.
Copyright © 2007–2017 Damien Robert
MIT License. See LICENSE.txt for details.