This file documents version 1.0 of suf.
suf [options] [str...]
suf is a sudoku solver.
It is a command line tool which is executed from the shell. It has no graphic interface: you just specify your sudoku problem as a string and the suf command returns all possible solutions.
suf is very fast: it takes approximately 2 milliseconds to solve a usual 9x9 grid and print the solution (tested on a MacBook Pro). It is based on D. Knuth's dancing links algorithm. used to solve exact cover problems. The exact cover algorithm guarantees to find all the solutions when a grid has several solutions.
suf can solve not only the traditional 9x9 problems but also grids in m:n format, that is to say grids made of mxn blocks with m lines and n columns: each block, each line and each column contains the values from 1 to mxn. For instance, here is a grid in format 2:3 in which all the blocks have two lines and three columns:
+---------------------+
| 1 2 3 | 0 0 0 |
| 0 0 0 | 3 1 2 |
|----------|----------|
| 4 5 6 | 0 0 0 |
| 0 1 0 | 5 0 0 |
|----------|----------|
| 2 0 0 | 6 0 5 |
| 0 0 4 | 0 0 2 |
+---------------------+
The str argument is a string representing the cells in row order: one can use any symbol other than 1-9 digits for the unsolved cells (for instance, a dot, or a zero). Here are a few valid examples:
suf ...3..8..64.8...5.875.....15...7.2.6....9....2.9.8...54.....769.2...8.13..7..5... suf 000300800640800050875000001500070206000090000209080005400000769020008013007005000 suf " 3 8 64 8 5 875 15 7 2 6 9 2 9 8 54 769 2 8 13 7 5 "
If the blocks contain more than 9 values, the multi-digit numbers must be enclosed in parentheses. For instance, the following string corresponds to 12 blocks containing 12 values each (here the string is split for readability in order to fit in the page):
suf -f 3:4 "1234..7.9...56......1.349...1.34.6.8.413.(11).5...6.867...1..4.
(11)5(12).674....1.321(11)5...9....4..1...75(11)....(12)4..81...
1....5(11).8(12).6..(11).(12).2.....(12).....6.(11).."
The format is specified with the -f option. The value of this option has the form m:n and indicates that the sudoku is made of mn blocks with m rows and n columns, so that each block contains mn values. By default, the format is 3:3 which corresponds to the usual sudoku problems with 9 blocks of 9 values.
Several strings can be specified on the command line. They must all be in the same format.
The possible options are:
| -c | count solutions |
| -f m:n | size of blocks (default 3:3) |
| -g | display grid |
| -h | print usage |
| -l n | limit to n solutions |
| -q | quiet |
| -r | print raw strings |
| -v | print version |
| -- | end of options |
The -g option just displays the strings in a grid with horizontal and vertical lines separating the different blocks. No resolution algorithm is executed if this option is specified.
The -c option is used to count the solutions.
With the -r option, the solutions are returned as raw strings rather than grids. The output is faster with the -r option.
The -l option can be specified to limit the number of solutions returned by the command (in case there are multiple solutions).
The -q option limits the output to the bare minimum: only the solutions are printed.
In all the examples below, shell> designates your shell prompt.
You can just display the string as a mxn grid using the -g option. For instance:
shell> suf -g ...3..8..64.8...5.875.....15...7.2.6....9....2.9.8...54.....769.2...8.13..7..5... +--------------------------------+ | 0 0 0 | 3 0 0 | 8 0 0 | | 6 4 0 | 8 0 0 | 0 5 0 | | 8 7 5 | 0 0 0 | 0 0 1 | |----------|----------|----------| | 5 0 0 | 0 7 0 | 2 0 6 | | 0 0 0 | 0 9 0 | 0 0 0 | | 2 0 9 | 0 8 0 | 0 0 5 | |----------|----------|----------| | 4 0 0 | 0 0 0 | 7 6 9 | | 0 2 0 | 0 0 8 | 0 1 3 | | 0 0 7 | 0 0 5 | 0 0 0 | +--------------------------------+
Unless the -c, or -g options have been specified, the command will execute the resolution algorithm and return all the possible solutions. For instance:
shell> suf ...3..8..64.8...5.875.....15...7.2.6....9....2.9.8...54.....769.2...8.13..7..5... Solution +--------------------------------+ | 1 9 2 | 3 5 6 | 8 4 7 | | 6 4 3 | 8 1 7 | 9 5 2 | | 8 7 5 | 4 2 9 | 6 3 1 | |----------|----------|----------| | 5 8 4 | 1 7 3 | 2 9 6 | | 7 6 1 | 5 9 2 | 3 8 4 | | 2 3 9 | 6 8 4 | 1 7 5 | |----------|----------|----------| | 4 5 8 | 2 3 1 | 7 6 9 | | 9 2 6 | 7 4 8 | 5 1 3 | | 3 1 7 | 9 6 5 | 4 2 8 | +--------------------------------+
If the -r option has been specified, the solution is returned as a raw string. For instance:
shell> suf -r ...3..8..64.8...5.875.....15...7.2.6....9....2.9.8...54.....769.2...8.13..7..5... Solution 192356847643817952875429631584173296761592384239684175458231769926748513317965428 Elapsed time: 2 msTo get only the solution string, add the -q option:
shell> suf -q -r ...3..8..64.8...5.875.....15...7.2.6....9....2.9.8...54.....769.2...8.13..7..5... 192356847643817952875429631584173296761592384239684175458231769926748513317965428
shell> suf -f 2:3 "123......312456....1.5..2..6.5..4.2." Solution +---------------------+ | 1 2 3 | 4 5 6 | | 6 4 5 | 3 1 2 | |----------|----------| | 4 5 6 | 2 3 1 | | 3 1 2 | 5 6 4 | |----------|----------| | 2 3 1 | 6 4 5 | | 5 6 4 | 1 2 3 | +---------------------+ Elapsed time: 3 ms
If the -c option is specified, the command will only count the solutions. For instance, the following problem has 7 solutions:
shell> suf -c 3.......2..13697..7.4...8.9...8......9.....2....4.6...4.5...1.6..614.2..1.......8 7 Elapsed time: 2 ms
shell> suf -l 3 -r 3.......2..13697..7.4...8.9...8......9.....2....4.6...4.5...1.6..614.2..1.......8 Solution 359784612821369745764215839247893561698571324513426987485932176976148253132657498 Solution 2 359784612821369745764215839547823961698571324213496587485932176976148253132657498 Solution 3 359784612821369745764215839547832961698571324213496587435928176986147253172653498 Output limited to 3 solution(s).
suf is very fast. It has been tested with all kinds of sudokus, from easy to extremely difficult. The average time to solve a usual 9x9 sudoku is 2 milliseconds (tested on a MacBook Pro). As an example, suf has successfully solved all the Top95 problems in less than 0.2 seconds altogether:
shell> cat top95 | xargs suf -r [...] Elapsed time: 190 ms
The code is hosted on the SourceForge site at the following address: http://sourceforge.net/projects/sufsolver
suf releases are available on the file releases page at SourceForge.
suf is written entirely in Fortran and makes use of features defined in the Fortran 2003 Standard (such as pointers onto polymorphic entities and procedure pointers). In order to compile it, you need a Fortran compiler which supports these features: for instance, gfortran version 4.5 or greater (previous versions of gfortran won't do). The NAG compiler, the Intel compiler or the Cray compiler should be fine too but I haven't tested them.
To compile the command, go to the directory containing the source code and execute the configuration script:
./configure
This will generate a Makefile containing the compiling instructions.
Execute it with the following command:
make
If no error is encountered, this will produce an executable command named
suf. In order to install this command and its man page, execute the following command:
make install
Bernard Desgraupes bdesgraupes@users.sourceforge.net
suf is an Open Source Project. Its source code is freely available and can be distributed and modified provided you respect the licensing terms. It is distributed under a BSD License: see the file License_terms in the distribution or the Open Source Initiative site.
Last updated 2010-07-27 08:51:18
suf is hosted by