Sudoku Solver Program in C: Lightning Fast
===========================================
Steve Jacobson
November 25, 2019
Introduction:
-------------
This program is a Sudoku puzzle solver written in C. It uses repetitive
application of algorithms to arrive at a solution, very much as does a
human. Because of this approach, it is many orders of magnitude faster
than programs relying on brute-force guessing.
The sudoku program reads the puzzle to be solved from an ASCII file, an
example of which is below. This is ./puzzles1/l3-5.txt.
#
# Source:
# Date:
# Level:
#
3,.,., .,2,8, .,.,1
2,.,., 9,.,., .,4,5
9,.,., .,.,., .,.,.
#
.,.,., 2,5,., 6,.,.
.,.,6, .,.,., 3,.,.
.,.,8, .,1,3, .,.,.
#
.,.,., .,.,., 4,.,9
7,.,., .,.,9, .,.,2
.,.,., 5,7,., .,.,.
This (standard) format is a visual representation of a printed puzzle; the
data lines are in a mandatory rigid format. "#" prefaces an optional
comment line, the entirety of which is disregarded by the program. Commas
and spaces in data lines are separators, and must appear as shown. "."
represents a cell which has no value specified. Integers 0-9 represent
cells with initially specified values.
Note: Setting the window width to 110 columns works best when running
the sudoku program (and when reading this file).
To compile the program:
-----------------------
1. cd into the sudoku source code directory
2. type "make"
To obtain help from the program:
--------------------------------
stevej@bsd11_2:~/sudoku % ./sudoku -h
usage: ./sudoku [-?hbIrRV] [-d ] [-D ]
[-i ] [-s ] -fF
-b: try breadth-first search if needed
-d: set debug flags
-D: maximum depth for depth-first recursion
-f: specify puzzle filename (standard format)
-F: specify puzzle filename (linear format)
-?h: print help and exit
-i: specify starting index for puzzle search
-I: enable random starting index for puzzle search
-r: try recursive descent if needed
-R: use only recursive descent (unimplemented)
-s: silent mode level
-V: print version string and exit
stevej@bsd11_2:~/sudoku %
Running the program using the basic algorithmic solver:
-------------------------------------------------------
Here is an example of running the sudoku solver program on the l3-5.txt
puzzle, shown above.
stevej@bsd11_2:~/sudoku % ./sudoku -f ./puzzles1/l3-5.txt -s 1
"-f ./puzzles1/l3-5.txt" specifies the standard format puzzle file to
be solved.
"-s 1" specifies the level of silence (the opposite of verbosity).
"-s 0" prints more chatter about the algorithms solving the puzzle than
will interest most users. "-s 1" prints the starting and ending states
of the puzzle, followed by a summary of the solution. In this case the
program determined that the puzzle was actually solved, and verified that
the solution was actually sane.
"| 3 |" represents a single cell of the puzzle. It is a fully
determined cell that contains, and can only contain, the value 3.
"| 123456789 |" represents an undetermined single cell of the puzzle.
It may ultimately contain any value in the range 0..9. It is unknown
at this time which one of those values it will end up containing.
=====================================
| 3 | 123456789 | 123456789 |
| 2 | 123456789 | 123456789 |
| 9 | 123456789 | 123456789 |
=====================================
The above represents a square of the puzzle, containing 3 x 3 cells.
Three of the cells are determined, and six are not.
=============
| 3 |
| 2 |
| 9 |
=============
| 123456789 |
| 123456789 |
| 123456789 |
=============
| 123456789 |
| 7 |
| 123456789 |
=============
The above represents a single column of the puzzle. It contains
nine cells.
| 3 | 123456789 | 123456789 | 123456789 | 2 | 8 | 123456789 | 123456789 | 1 |
The above represents a single row of the puzzle. It also contains
nine cells.
stevej@bsd11_2:~/sudoku % ./sudoku -f ./puzzles1/l3-5.txt -s 1
=============================================================================================================
| 3 | 123456789 | 123456789 | 123456789 | 2 | 8 | 123456789 | 123456789 | 1 |
| 2 | 123456789 | 123456789 | 9 | 123456789 | 123456789 | 123456789 | 4 | 5 |
| 9 | 123456789 | 123456789 | 123456789 | 123456789 | 123456789 | 123456789 | 123456789 | 123456789 |
=============================================================================================================
| 123456789 | 123456789 | 123456789 | 2 | 5 | 123456789 | 6 | 123456789 | 123456789 |
| 123456789 | 123456789 | 6 | 123456789 | 123456789 | 123456789 | 3 | 123456789 | 123456789 |
| 123456789 | 123456789 | 8 | 123456789 | 1 | 3 | 123456789 | 123456789 | 123456789 |
=============================================================================================================
| 123456789 | 123456789 | 123456789 | 123456789 | 123456789 | 123456789 | 4 | 123456789 | 9 |
| 7 | 123456789 | 123456789 | 123456789 | 123456789 | 9 | 123456789 | 123456789 | 2 |
| 123456789 | 123456789 | 123456789 | 5 | 7 | 123456789 | 123456789 | 123456789 | 123456789 |
=============================================================================================================
=============================================================================================================
| 3 | 4 | 5 | 7 | 2 | 8 | 9 | 6 | 1 |
| 2 | 8 | 1 | 9 | 3 | 6 | 7 | 4 | 5 |
| 9 | 6 | 7 | 1 | 4 | 5 | 8 | 2 | 3 |
=============================================================================================================
| 4 | 3 | 9 | 2 | 5 | 7 | 6 | 1 | 8 |
| 1 | 2 | 6 | 8 | 9 | 4 | 3 | 5 | 7 |
| 5 | 7 | 8 | 6 | 1 | 3 | 2 | 9 | 4 |
=============================================================================================================
| 6 | 5 | 2 | 3 | 8 | 1 | 4 | 7 | 9 |
| 7 | 1 | 3 | 4 | 6 | 9 | 5 | 8 | 2 |
| 8 | 9 | 4 | 5 | 7 | 2 | 1 | 3 | 6 |
=============================================================================================================
>>>>>> ./puzzles1/l3-5.txt solved, sane!
Iterations: 7. Changes: Rows 190, cols 145, squares 121, tot 456
stevej@bsd11_2:~/sudoku %
"-s 2" prints only the summary. It is useful for scripting, and/or
when you are testing modifications to the program.
stevej@bsd11_2:~/sudoku % ./sudoku -f ./puzzles1/l3-5.txt -s 2
>>>>>> ./puzzles1/l3-5.txt solved, sane!
Iterations: 7. Changes: Rows 190, cols 145, squares 121, tot 456
stevej@bsd11_2:~/sudoku %
"-s 3" prints nothing. It is useful for shell scripts, which can make
control decisions based on the status value returned when the sudoku
program completes.
stevej@bsd11_2:~/sudoku % ./sudoku -f ./puzzles1/l3-5.txt -s 3
stevej@bsd11_2:~/sudoku %
stevej@bsd11_2:~/cvs_sudoku/sudoku % cd scripts
stevej@bsd11_2:~/cvs_sudoku/sudoku/scripts % cat quick_test
#!/bin/sh
../sudoku -f ../puzzles1/l3-5.txt -s 3
if [ $? -eq 0 ]
then
echo "Puzzle solved!"
else
echo "Puzzle not solved!"
fi
stevej@bsd11_2:~/cvs_sudoku/sudoku/scripts % sh quick_test
Puzzle solved!
Running the program, intermediate use:
--------------------------------------
Basic application of the program, as shown above, should solve all
puzzles where repetitive application of the algorithms is sufficient.
In other words, puzzles that do not require guessing.
For puzzles requiring guessing, there is a breadth-first (-b) option
that can solve all puzzles where correctly guessing only one cell is
sufficient. If the algorithms do not solve the puzzle, it makes and
tests one guess at a time, then re-applies the algorithms. It is
effectively a recursive descent solver with a single level of recursion.
stevej@bsd11_2:~/sudoku % ./sudoku -f ./puzzles1/l4-1.txt -s 2 -b
"-b" enables the breadth-first search solver, if needed. Breadth-first
search is only invoked if the basic algorithmic solver fails to arrive
at a solution.
stevej@bsd11_2:~/sudoku % ./sudoku -f ./puzzles1/l4-1.txt -s 2
*** ./puzzles1/l4-1.txt NOT solved, sane! Solution failed!
Iterations: 6. Changes: Rows 170, cols 139, squares 86, tot 395
stevej@bsd11_2:~/sudoku %
stevej@bsd11_2:~/sudoku % ./sudoku -f ./puzzles1/l4-1.txt -s 2 -b
>>>>>> ./puzzles1/l4-1.txt solved, sane!
Iterations: 11. Changes: Rows 185, cols 152, squares 94, tot 431
bfs: cells 2, values 3
stevej@bsd11_2:~/sudoku %
stevej@bsd11_2:~/sudoku % ./sudoku -f ./puzzles1/l4-1.txt -s 1
=============================================================================================================
| 123456789 | 123456789 | 123456789 | 3 | 123456789 | 123456789 | 123456789 | 123456789 | 123456789 |
| 123456789 | 1 | 123456789 | 123456789 | 123456789 | 123456789 | 3 | 4 | 5 |
| 3 | 9 | 123456789 | 123456789 | 123456789 | 123456789 | 123456789 | 123456789 | 123456789 |
=============================================================================================================
| 123456789 | 3 | 123456789 | 9 | 123456789 | 1 | 123456789 | 123456789 | 6 |
| 6 | 123456789 | 123456789 | 4 | 2 | 5 | 123456789 | 123456789 | 9 |
| 1 | 123456789 | 123456789 | 7 | 123456789 | 6 | 123456789 | 2 | 123456789 |
=============================================================================================================
| 123456789 | 123456789 | 123456789 | 123456789 | 123456789 | 123456789 | 123456789 | 1 | 8 |
| 8 | 7 | 4 | 123456789 | 123456789 | 123456789 | 123456789 | 5 | 123456789 |
| 123456789 | 123456789 | 123456789 | 123456789 | 123456789 | 4 | 123456789 | 123456789 | 123456789 |
=============================================================================================================
=============================================================================================================
| 2 7 | 4 | 56 | 3 | 1 5 | 2 78 | 2 6 9 | 6 89 | 1 7 |
| 2 7 | 1 | 8 | 2 6 | 67 9 | 2 7 9 | 3 | 4 | 5 |
| 3 | 9 | 56 | 1 5 | 4 | 2 78 | 2 6 | 6 8 | 1 7 |
=============================================================================================================
| 4 | 3 | 2 | 9 | 8 | 1 | 5 | 7 | 6 |
| 6 | 8 | 7 | 4 | 2 | 5 | 1 | 3 | 9 |
| 1 | 5 | 9 | 7 | 3 | 6 | 8 | 2 | 4 |
=============================================================================================================
| 5 9 | 6 | 3 | 2 5 | 5 7 9 | 2 7 9 | 4 | 1 | 8 |
| 8 | 7 | 4 | 1 6 | 1 6 9 | 3 | 6 9 | 5 | 2 |
| 5 9 | 2 | 1 | 8 | 56 9 | 4 | 7 | 6 9 | 3 |
=============================================================================================================
*** ./puzzles1/l4-1.txt NOT solved, sane! Solution failed!
Iterations: 6. Changes: Rows 170, cols 139, squares 86, tot 395
stevej@bsd11_2:~/sudoku %
stevej@bsd11_2:~/sudoku % ./sudoku -f ./puzzles1/l4-1.txt -s 1 -b
=============================================================================================================
| 123456789 | 123456789 | 123456789 | 3 | 123456789 | 123456789 | 123456789 | 123456789 | 123456789 |
| 123456789 | 1 | 123456789 | 123456789 | 123456789 | 123456789 | 3 | 4 | 5 |
| 3 | 9 | 123456789 | 123456789 | 123456789 | 123456789 | 123456789 | 123456789 | 123456789 |
=============================================================================================================
| 123456789 | 3 | 123456789 | 9 | 123456789 | 1 | 123456789 | 123456789 | 6 |
| 6 | 123456789 | 123456789 | 4 | 2 | 5 | 123456789 | 123456789 | 9 |
| 1 | 123456789 | 123456789 | 7 | 123456789 | 6 | 123456789 | 2 | 123456789 |
=============================================================================================================
| 123456789 | 123456789 | 123456789 | 123456789 | 123456789 | 123456789 | 123456789 | 1 | 8 |
| 8 | 7 | 4 | 123456789 | 123456789 | 123456789 | 123456789 | 5 | 123456789 |
| 123456789 | 123456789 | 123456789 | 123456789 | 123456789 | 4 | 123456789 | 123456789 | 123456789 |
=============================================================================================================
=============================================================================================================
| 2 | 4 | 5 | 3 | 1 | 8 | 6 | 9 | 7 |
| 7 | 1 | 8 | 6 | 9 | 2 | 3 | 4 | 5 |
| 3 | 9 | 6 | 5 | 4 | 7 | 2 | 8 | 1 |
=============================================================================================================
| 4 | 3 | 2 | 9 | 8 | 1 | 5 | 7 | 6 |
| 6 | 8 | 7 | 4 | 2 | 5 | 1 | 3 | 9 |
| 1 | 5 | 9 | 7 | 3 | 6 | 8 | 2 | 4 |
=============================================================================================================
| 5 | 6 | 3 | 2 | 7 | 9 | 4 | 1 | 8 |
| 8 | 7 | 4 | 1 | 6 | 3 | 9 | 5 | 2 |
| 9 | 2 | 1 | 8 | 5 | 4 | 7 | 6 | 3 |
=============================================================================================================
>>>>>> ./puzzles1/l4-1.txt solved, sane!
Iterations: 11. Changes: Rows 185, cols 152, squares 94, tot 431
bfs: cells 2, values 3
stevej@bsd11_2:~/sudoku %
Running the program, advanced use:
----------------------------------
So far, all newspaper and most Internet-available puzzles tested have been
solved by the algorithmic solver alone, or by the algorithms + breadth-first
search. However, more complicated puzzles can be found, such as the
"unsolvable" puzzles on certain websites, that can only be solved using the
recursive descent feature. It must be used with caution, however, as the
amount of computation can grow exponentially with the number of levels of
recursion; it depends entirely on the puzzle. Solutions have been measured
as taking from milliseconds to days, with the possibility of taking weeks,
months or years.
The following program invocations test variants of l4-27.txt, from
which some of the specified values have been removed.
stevej@bsd11_2:~/sudoku % ./sudoku -f ./puzzles_test1/l4-27.test1.txt -s 2 -r
"-r" specifies recursive descent, if needed because the basic algorithms
fail to arrive at a solution.
"-D 20" permits recursion to a depth of 20 levels. The default is -D 4.
Note that "-r -D 1" is roughly equivalent to "-b".
stevej@bsd11_2:~/sudoku % ./sudoku -f ./puzzles_test1/l4-27.test1.txt -s 2
*** ./puzzles_test1/l4-27.test1.txt NOT solved, sane! Solution failed!
Iterations: 5. Changes: Rows 158, cols 140, squares 73, tot 371
stevej@bsd11_2:~/sudoku %
stevej@bsd11_2:~/sudoku % ./sudoku -f ./puzzles_test1/l4-27.test1.txt -s 2 -b
*** ./puzzles_test1/l4-27.test1.txt NOT solved, sane! Solution failed!
Iterations: 5. Changes: Rows 158, cols 140, squares 73, tot 371
bfs: cells 40, values 117
stevej@bsd11_2:~/sudoku %
stevej@bsd11_2:~/sudoku % ./sudoku -f ./puzzles_test1/l4-27.test1.txt -s 2 -r
>>>>>> ./puzzles_test1/l4-27.test1.txt solved, sane!
Iterations: 17. Changes: Rows 184, cols 166, squares 93, tot 443
dfs: cells 4 vals 4 rec 3 bt 0 ns 0 mrl 3
stevej@bsd11_2:~/sudoku %
With the more difficult "l4-27.test2.txt" puzzle:
stevej@bsd11_2:~/sudoku % ./sudoku -f ./puzzles_test1/l4-27.test2.txt -s 2
*** ./puzzles_test1/l4-27.test2.txt NOT solved, sane! Solution failed!
Iterations: 2. Changes: Rows 90, cols 91, squares 40, tot 221
stevej@bsd11_2:~/sudoku %
stevej@bsd11_2:~/sudoku % ./sudoku -f ./puzzles_test1/l4-27.test2.txt -s 2 -b
*** ./puzzles_test1/l4-27.test2.txt NOT solved, sane! Solution failed!
Iterations: 2. Changes: Rows 90, cols 91, squares 40, tot 221
bfs: cells 67, values 382
stevej@bsd11_2:~/sudoku %
stevej@bsd11_2:~/sudoku % ./sudoku -f ./puzzles_test1/l4-27.test2.txt -s 2 -r -D 20
>>>>>> ./puzzles_test1/l4-27.test2.txt solved, sane!
Iterations: 44. Changes: Rows 174, cols 226, squares 105, tot 505
dfs: cells 16 vals 17 rec 15 bt 0 ns 1 mrl 15
stevej@bsd11_2:~/sudoku %
Specifying both breadth-first and recursive descent searches:
-------------------------------------------------------------
Both breadth-first ("-b") and recursive descent ("-r") searches can be
requested on the same command line. This results in a hierarchy of
possible testing:
If the algorithmic solver is able to solve the puzzle, then neither
breadth-first nor recursive descent testing is performed.
If the algorithmic solver fails to solve the puzzle, then breadth-first
testing is attempted. If breadth-first testing succeeds in solving the
puzzle, then recursive descent testing is not done.
If both the algorithmic solver and breadth-first testing fail to solve
the puzzle, then recursive descent testing is performed.
stevej@bsd11_2:~/sudoku % ./sudoku -f ./puzzles1/l3-1.txt -s 2 -b -r -D 20
>>>>>> ./puzzles1/l3-1.txt solved, sane!
Iterations: 9. Changes: Rows 195, cols 178, squares 83, tot 456
stevej@bsd11_2:~/sudoku %
stevej@bsd11_2:~/sudoku % ./sudoku -f ./puzzles1/l4-1.txt -s 2 -b -r -D 20
>>>>>> ./puzzles1/l4-1.txt solved, sane!
Iterations: 11. Changes: Rows 185, cols 152, squares 94, tot 431
bfs: cells 2, values 3
stevej@bsd11_2:~/sudoku %
stevej@bsd11_2:~/sudoku % ./sudoku -f ./puzzles_test1/l4-27.test2.txt -s 2 -b -r -D 20
>>>>>> ./puzzles_test1/l4-27.test2.txt solved, sane!
Iterations: 44. Changes: Rows 174, cols 226, squares 105, tot 505
bfs: cells 67, values 382
dfs: cells 16 vals 17 rec 15 bt 0 ns 1 mrl 15
stevej@bsd11_2:~/sudoku %
Specifying a starting cell index when running:
----------------------------------------------
The "-i " and "-I" options apply to both recursive descent ("-r")
and breadth-first search ("-b"). These options have been shown to be
useful when solving certain difficult puzzles with recursive descent.
They have not proven useful so far with breadth-first search.
There are 81 cells (small squares) in a standard 9 x 9 Sudoku puzzle.
Normally, testing starts at cell 0, the cell in the upper left-hand
corner of the puzzle.
Certain difficult Sudoku puzzles expose the extreme computational complexity
that is possible with deep, depth-first recursion. Those puzzles may take
many days to solve under default conditions. To give a better chance of
finding a solution, the cell at which testing starts can be changed in
one of two ways.
stevej@bsd11_2:~/sudoku % ./sudoku -f ./puzzles1/l4-19.txt -r -D 20 -s 2 -i 41
stevej@bsd11_2:~/sudoku % ./sudoku -f ./puzzles1/l4-19.txt -r -D 20 -s 2 -I
"-i 41" causes testing to start at, in this example, cell 41 instead of
the default cell 0. The starting point will be cell 41 for every single
level of the recursion.
"-I" causes testing to start at some random cell index for each level of
the recursion. A new cell index is chosen at each recursion level.
Possible values for the cell index are in the range 0 - 80, inclusive.
stevej@bsd11_2:~/sudoku % ./sudoku -f ./puzzles1/l4-19.txt -r -D 20 -s 2
^C
The invocation above was not completing in a reasonable amount of time,
so it was halted with ctrl-C.
stevej@bsd11_2:~/sudoku % ./sudoku -f ./puzzles1/l4-19.txt -r -D 20 -s 2 -i 41
>>>>>> ./puzzles1/l4-19.txt solved, sane!
Iterations: 12. Changes: Rows 184, cols 166, squares 108, tot 458
dfs: cells 2 vals 7 rec 1 bt 0 ns 5 mrl 1
stevej@bsd11_2:~/sudoku %
The invocation above completed immediately as a result of adding "-i 41".
Note that some experimentation was needed to find a value (41) leading to
success with this puzzle.
stevej@bsd11_2:~/sudoku % ./sudoku -f ./puzzles1/l4-19.txt -r -D 20 -s 2 -I
^C
stevej@bsd11_2:~/sudoku % ./sudoku -f ./puzzles1/l4-19.txt -r -D 20 -s 2 -I
^C
stevej@bsd11_2:~/sudoku % ./sudoku -f ./puzzles1/l4-19.txt -r -D 20 -s 2 -I
>>>>>> ./puzzles1/l4-19.txt solved, sane!
Iterations: 13. Changes: Rows 189, cols 163, squares 108, tot 460
dfs: cells 2 vals 4 rec 1 bt 0 ns 2 mrl 1
stevej@bsd11_2:~/sudoku %
Using "-I", the program had to be invoked three times (in this particular
example) before the program completed quickly. Since the cell index at
every level is random, not pseudo-random, results will likely differ with
every test run.
Summary output fields:
----------------------
Preface to summary line:
- solved and sane: >>>>>>
- not solved, but sane: ***
- not solved and not sane: ******
Summary line
- solved: Every cell contains exactly one value.
- NOT solved: Not every cell contains a single value.
- sane: Every determined value is unique in the row, column and square
that contains it.
- NOT sane: At least one determined value is not unique within a row,
column and/or square.
Iterations: Number of times the algorithmic solver was applied to
all rows, columns and squares of the puzzle.
Changes: The number of times a possible value is eliminated in a cell.
- rows: Number of eliminations in analysis of rows.
- cols: Number of eliminations in analysis of columns.
- squares: Number of eliminations in analysis of squares.
- tot: Total number of changes in rows, columns and squares.
BFS fields:
- cells: Total number of cells where values were guessed.
- vals: Total number of values tried in guessed cells.
DFS fields:
- cells: Total number of cells where values were guessed.
- vals: Total number of values tried in guessed cells.
- rec: Total number of recursions.
- bt: Total number of backtracks.
- ns: Number of paths that were found to not be sane.
- mrl: Maximum number of recursion levels reached.
Linear file format:
-------------------
The sudoku program accepts an alternate input file format, the linear file.
Linear input is popular on certain websites due to its single line format.
Each cell is represented by a single character; 0-9 specifies the cell
value, with 0 indicating an unspecified cell.
The sudoku_io_test program can be used to convert from standard to linear,
and from linear to standard formats. The following example converts the
standard puzzle file l3-5.txt to linear file l3-5.lin.
stevej@bsd11_2:~/git_sudoku % ./sudoku_io_test -i ./puzzles1/l3-5.txt -O ./puzzles1/l3-5.lin
stevej@bsd11_2:~/git_sudoku % cat ./puzzles1/l3-5.lin
300028001200900045900000000000250600006000300008013000000000409700009002000570000
stevej@bsd11_2:~/git_sudoku %
To run the file,
stevej@bsd11_2:~/cvs_sudoku/sudoku % ./sudoku -F ./puzzles1/l3-5.lin -s 2
>>>>>> ./puzzles1/l3-5.lin solved, sane!
Iterations: 7. Changes: Rows 190, cols 145, squares 121, tot 456
stevej@bsd11_2:~/cvs_sudoku/sudoku %
For comparison,
stevej@bsd11_2:~/cvs_sudoku/sudoku % ./sudoku -f ./puzzles1/l3-5.txt -s 2
>>>>>> ./puzzles1/l3-5.txt solved, sane!
Iterations: 7. Changes: Rows 190, cols 145, squares 121, tot 456
stevej@bsd11_2:~/cvs_sudoku/sudoku %