sudokut is a command line Sudoku solver. It is written in Tcl, a
platform-independent scripting language, so it should work on any platform
(Unix, Mac OS X, Windows) provided a Tcl interpeter is installed (which is
usually the case by default on Unix and Mac OS X).
This file documents version 0.7 of sudokut.
Introduction
Sudoku is a logic game which has gained a wide popularity. The game
operates thusly: using numbers 1 through 9, you must fill in a nine-column,
nine-row grid (made of 9 3x3 blocks) without repeating digits. All the
digits between 1 and 9 must be present once and only once in each row, each
column and each block. See the Learn more about Sudokus
section below.
sudokut is a command line tool which is executed from the shell. It
has no graphic interface: you just pass your sudoku problem as a string to
the sudokut command and it returns all possible solutions.
sudokut is a free software.
Prerequisites
sudokut is written in fact in Tcl (the
Tool Command Language): of course, you do
not have anything to know about this language to run the tool but you must
just make sure there is a Tcl interpreter installed on your machine in
order to execute sudokut. Tcl is a widely used Open Source and
platform-independent scripting language. It has been ported to all the main
platforms (Unix, Mac OS X, Windows):
the t at the end of sudokut stands for Tcl !
The Tcl shell interpreter is usually
called tclsh under Unix and Mac OSX, tclsh.exe under
Windows, or sometimes its name contains a version number, like
tclsh85 or tclsh85.exe for version 8.5:
- Tcl is usually present, by default, in any Unix distribution.
- Tcl is also installed, by default, on Mac OS X since version 10.3 (aka
Panther) so tclsh is normally present on every Mac OS X system
starting from this version.
- Under Windows, you might have to install a distribution of Tcl
(see here for a free download).
Usage
Synopsis
The syntax of the sudokut command is:
sudokut options (string | -f file)
sudokut -d string1 string2
sudokut -m row col val ?row col val...? string
sudokut (-h|-t|-v)
Description
The first form of the command processes one or several sudoku problems.
Each sudoku is represented by a 81-characters string listing all the cells
in row order: you can use any symbol other than 1-9 digits for the unsolved
cells (for instance, a dot, or a zero, or whatever).
Here are a few valid examples:
% ./sudokut ...3..8..64.8...5.875.....15...7.2.6....9....2.9.8...54.....769.2...8.13..7..5...
% ./sudokut 000300800640800050875000001500070206000090000209080005400000769020008013007005000
% ./sudokut " 3 8 64 8 5 875 15 7 2 6 9 2 9 8 54 769 2 8 13 7 5 "
The last argument of the command can be either a sudoku string or a file
containing sudoku strings: in such a file, there must be one sudoku string
per line. Lines starting with a # character are considered as comments and
are ignored by the command. Empty lines are ignored too. If the last
argument is a dash, sudokut reads data from the standard input.
The available options are explained below.
The second form of the command (-d option) compares two
sudoku strings: the command returns the list of all the cells whose value
differs.
The third form of the command (-m option) modifies a sudoku
string.
In the fourth form
sudokut (-h|-t|-v)
the command prints the usage string, the list of techniques or the current
version number respectively.
Command line options
The complete syntax to run the solver is:
sudokut [-b] [-c] [-e] [-g] [-j] [-k[n]] [-l] [-n] [-o]
[-i codes] [-p codes] [-q] [-r] [-s] [-t] [-u] [-v num]
(string | -f file)
sudokut [-h|-t|-v]
The options have the following meaning:
- the -b option forces the use of the exact cover algorithm (the
b stands for backtracking) in order to solve the problem as fast as
possible without attempting to apply any reduction technique.
- the -c option counts the solutions.
- the -e option puts sudokut in explanatory mode so
that the process leading to the solution is carefully explained.
- the -f option specifies that the last argument
of the command is a file.
- the -g option displays the sudoku strings as a 9x9 grid.
- the -i option lets you specify a list of techniques to ignore.
Techniques are designated using a two-letter code: see
below the list of supported codes.
- the -j option tests the validity of a sudoku string.
It will report an error if it finds incompatibilities between the rows,
columns and blocks.
- the -k option displays a grid with the candidate sets for each
cell. If the option is followed by a digit (like -k1) only the candidate
sets containing this value are displayed.
- the -l option rates the level of difficulty of the
sudoku. It returns an integer value between 1 and 10.
- the -n option means no backtracking. It turns backtracking
off at the risk of finding only a partial solution: when all the usual
techniques have been applied, the only way of solving a puzzle completely is
by backtracking (exact cover algorithm).
- the -o option means only one solution. In that case the
script returns as soon as one solution has been found, instead of looking
for all solutions. This option is ignored if the -c option is used.
- the -p option lets you probe the sudoku with one ore more
specified techniques. The value of this option is a string of technique
codes separated by spaces: see below the list of supported codes. The
command returns the information which can be obtained with the specified
techniques.
- the -q option lets the command execute silently (it is
equivalent to -v 0).
- the -r option returns the solutions as
raw strings rather than 9x9 grids.
- the -s option asks for a suggestion about the next
possible step to solve the sudoku.
- the -t option prints the list of available techniques.
- the -u option tests the unicity of the
solution. The command returns 1 if and only if there is a unique solution.
it returns 0 in all other cases (which means no solution, or multiple
solutions, or an error occured).
- the -v option lets you specify the verbosity: its
value is a number between 0 and 4 which indicates how much information you
want sudokut written to the console while solving a problem. The
default value is 1. Note that the -c and -u options
automatically set the verbosity to 0 and that the -e, -s
and -p options set it to (at least) 3. Level 4 is for debugging.
Technique codes
Here is the list of the currently available codes used to specify reduction
techniques with the options -i and -p:
alsxyw | ALS-XY-Wing reduction |
alsxz | ALS-XZ reduction |
bb | block to block reduction |
br | block to row/col reduction |
hp | hidden pair reduction |
hq | hidden quadruplet reduction |
hs | hidden single reduction |
ht | hidden triplet reduction |
jf | jellyfish reduction |
lv | leviathan reduction |
np | naked pair reduction |
nq | naked quadruplet reduction |
ns | naked single reduction |
nt | naked triplet reduction |
sb | squirmbag reduction |
sf | swordfish reduction |
wh | whale reduction |
xw | X-Wing reduction |
xyw | XY-Wing reduction |
Execution
The script can be installed anywhere on your machine. It is a bash
script which magically redirects the instructions to tclsh, that is
the Tcl shell.
On a Unix system (including Mac OS X), it is easier to put it in a
directory where it can be found automatically, i-e in a directory which is
in your PATH
environment variable. In that case, you would execute
it like this:
sudokut
sudoku_string
where sudoku_string is the 81-chars string representing your sudoku.
Otherwise, you'll have to type the entire path of the script like, for
instance,
/home/bernardo/mytools/sudokut sudoku_string
or, alternatively, change the directory to where the script is installed and
execute it as ./sudokut. For instance:
cd /home/bernardo/mytools/
./sudokut sudoku_string
On Windows, you should launch tclsh.exe and type directly, in the
Tcl shell, the command to execute. This is done with the exec
command, like this:
exec path/to/the/script options sudoku_string
where path/to/the/script is the path to the location where you installed
the sudokut script on your machine.
Examples
In all the examples below, shell>
designates your shell prompt. It
is assumed that sudokut is automatically found by the shell (i-e
can be invoked as sudokut rather than ./sudokut as
explained above).
Displaying the grid
You can just display the sudoku string as a 9x9 grid using the -g option.
For instance:
shell> sudokut -g ...3..8..64.8...5.875.....15...7.2.6....9....2.9.8...54.....769.2...8.13..7..5...
+-----------------------+
| . . . | 3 . . | 8 . . |
| 6 4 . | 8 . . | . 5 . |
| 8 7 5 | . . . | . . 1 |
|-------|-------|-------|
| 5 . . | . 7 . | 2 . 6 |
| . . . | . 9 . | . . . |
| 2 . 9 | . 8 . | . . 5 |
|-------|-------|-------|
| 4 . . | . . . | 7 6 9 |
| . 2 . | . . 8 | . 1 3 |
| . . 7 | . . 5 | . . . |
+-----------------------+
Checking the validity
You can check whether if a sudoku is valid (i-e does not contain
incompatible cell values) using the -j option (t stands for
test). For instance:
shell> sudokut -j ...3..8..64.8...5.875.....15...7.2.6....9....2.9.8...54.....769.2...8.13..7..5...
sudoku is valid
shell> sudokut -j ...3..8.364.8...5.875.....15...7.2.6....9....2.9.8...54.....769.2...8.13..7..5...
invalid row 1: multiple digit 3
Solving the sudoku
Unless the -c, -g, or -j options have been specified, the command will solve
the sudoku and return all the possible solutions. For instance:
shell> sudokut ...3..8..64.8...5.875.....15...7.2.6....9....2.9.8...54.....769.2...8.13..7..5...
Solution 1:
+-----------------------+
| 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 81
characters string. For instance:
shell> sudokut -r ...3..8..64.8...5.875.....15...7.2.6....9....2.9.8...54.....769.2...8.13..7..5...
Solution 1:
192356847643817952875429631584173296761592384239684175458231769926748513317965428
To get only the solution string, add the -q (quiet) option:
shell> sudokut -q -r ...3..8..64.8...5.875.....15...7.2.6....9....2.9.8...54.....769.2...8.13..7..5...
192356847643817952875429631584173296761592384239684175458231769926748513317965428
Explaining the resolution
Very often, you will not be only interested in getting the solution but
also in understanding how to get this solution. The -e option puts
sudokut in explanatory mode: in this mode, the program outputs
detailed information about the logics leading to the solution.
shell> sudokut -e ...3..8..64.8...5.875.....15...7.2.6....9....2.9.8...54.....769.2...8.13..7..5...
The output is not reproduced here.
Listing candidates
Starting from version 0.3, the -k option lets you display a grid
with the candidate values for all the unsolved cells. Candidates are determined exclusively by the fact that a particular
value can be present only once in every row, column and block. For
instance:
shell> sudokut -k 812...5937...1...66..3.5..1..9.8.4...2.7.3.1...5.4.3.....2.6..4....5...8....7.932
+-----------------------------------------------------------------+
| 8 1 2 | 46 6 47 | 5 9 3 |
| 7 3459 34 | 489 1 2489 | 28 248 6 |
| 6 49 4 | 3 29 5 | 278 2478 1 |
+-----------------------------------------------------------------+
| 13 367 9 | 156 8 12 | 4 2567 57 |
| 4 2 468 | 7 69 3 | 68 1 59 |
| 1 678 5 | 169 4 129 | 3 2678 79 |
+-----------------------------------------------------------------+
| 1359 35789 1378 | 2 39 6 | 17 57 4 |
| 12349 34679 13467 | 149 5 149 | 167 67 8 |
| 145 4568 1468 | 148 7 148 | 9 3 2 |
+-----------------------------------------------------------------+
If the -r option is
used simultaneously, the candidates are displyed as a list instead of a
grid.
If the option -k is followed by a digit, only the candidate sets containing
this value are displayed. For instance:
shell> sudokut -k8 812...5937...1...66..3.5..1..9.8.4...2.7.3.1...5.4.3.....2.6..4....5...8....7.932
Candidates with value 8:
+-----------------------------------------------------------------+
| . . . | . . . | . . . |
| . . . | 489 . 2489 | 28 248 . |
| . . . | . . . | 278 2478 . |
+-----------------------------------------------------------------+
| . . . | . . . | . . . |
| . . 468 | . . . | 68 . . |
| . 678 . | . . . | . 2678 . |
+-----------------------------------------------------------------+
| . 35789 1378 | . . . | . . . |
| . . . | . . . | . . . |
| . 4568 1468 | 148 . 148 | . . . |
+-----------------------------------------------------------------+
Similarly, with the -k+ option, you obtain the same kind of display
for all the possible values (from 1 to 9).
Counting the solutions
If the -c option is specified, the command will only count the
solutions. For instance, the following puzzle has 7 solutions:
shell> sudokut -c 3.......2..13697..7.4...8.9...8......9.....2....4.6...4.5...1.6..614.2..1.......8
7
Note that with the -c option, the verbosity is automatically set
to 0 and the -o option is ignored.
Testing unicity
With the -u option, one can test the unicity of the solution. This
form of the command will return 1 if a solution does exist and if
it is unique. It returns 0 in all other circumstances.
For instance:
shell> sudokut -u ...3..8..64.8...5.875.....15...7.2.6....9....2.9.8...54.....769.2...8.13..7..5...
1
shell> sudokut -u 3.......2..13697..7.4...8.9...8......9.....2....4.6...4.5...1.6..614.2..1.......8
0
Note that with the -u option, the verbosity is automatically set
to 0 and the -o option is ignored.
Processing a file
You can process several sudokus at a time by storing them in a file and
executing sudokut on this file with the -f option. The path
of the file must be the last argument of the command, immediately preceded
by the -f option. A sudoku file must have one sudoku per line and
nothing else on this line. The file can also contain comments: a comment is
a line starting with a #
character. Empty lines are also
accepted.
Here is an example of a file containing two sudokus with two
comments:
# "Le Figaro" - 25 nov 2005
...1..754.45..........65...1....698.5.......2.798....6...57..........23.387..1...
# "The Times" - 22 nov 2005
.43.8.25.6.............1.949....4.7....6.8....1.2....382.5.............5.34.9.71.
The path of the file can be absolute or relative. A relative path is
relative to the current directory (which is not necessarily where the
script is located).
The usual Unix expansions for file names (using the ~, ./ or ../ syntax)
are supported. So the following commands are all valid:
shell> sudokut -f /home/bernardo/puzzles/mysudokus.txt
shell> sudokut -f ~/puzzles/mysudokus.txt
shell> sudokut -f ../puzzles/mysudokus.txt
This last example assumes that the sudokut script is executed from a sibling
directory of the puzzles directory.
All the options apply in the case of an input file. For instance, the
following command will check the validity of all the sudokus in the given
file:
shell> sudokut -j -f ~/puzzles/mysudokus.txt
Getting suggestions
You can ask sudokut for a hint about what might be the next step in
the resolution process. The -s option will try to apply various
reduction techniques until it finds a clue. When the suggested step
does determine the value of a particular cell, the command also prints
the modified sudoku as an 81-chars string: this can be useful to take a
further step. For instance:
shell> sudokut -s ...1..754.45..........65...1....698.5.......2.798....6...57..........23.387..1...
insert value 4 at position L3C4 in row 3
...1..754.45.........465...1....698.5.......2.798....6...57..........23.387..1...
The returned string has the value 4 inserted at position L3C4 and can be
used in a new sudokut -s command.
The -s option returns the results it can find with a particular
technique and, if no such result is found, it switches to another
technique. This is different from the -p option which reports as
much information as it can gather about the sudoku, using the specified
technique.
The option -s can be combined with the option -i to skip some techniques.
For instance, using the same sudoku as in the previous example:
shell> sudokut -s -i "hs" ...1..754.45..........65...1....698.5.......2.798....6...57..........23.387..1...
* naked single reduction
* block to row/col reduction
Value 1 for block 1 can only be in row 3
removed candidate 1 from L3C7
removed candidate 1 from L3C8
removed candidate 1 from L3C9
Note that option -s automatically sets the verbosity to (at least) 3.
Probing a sudoku
Option -p offers a better granularity than option -s: it lets you
probe the sudoku and see what information can be obtained when applying
a particular solving technique. Solving techniques are specified using a
short code (see the
Solving techniques section for a
list of the codes). For instance, one can probe the following sudoku with
the Block to range (row or column) reduction technique
(code br
) like this:
shell> sudokut -p br ..37..65..7.45.8..1....6..4592....4.8..9245.6.....59.23..54...77.4.9..6..2...74..
Value 6 for block 4 can only be in row 6
remove candidate 6 from L6C4
remove candidate 6 from L6C5
Value 6 for block 8 can only be in row 9
remove candidate 6 from L9C1
remove candidate 6 from L9C3
...
Here is another example, looking for naked pairs (np
):
shell> sudokut -p np 2.6..5.9.9......313.1...6.......7..6...3.6...4..2.......2...9.518......2.9.8..3.7
Cells L1C9 and L3C9 have only the same two values 4, 8:
remove these candidates from the other cells in column 9
remove candidate 4 from L5C9
remove candidate 8 from L5C9
remove candidate 8 from L6C9
Cells L1C9 and L3C9 have only the same two values 4, 8:
remove these candidates from the other cells in block 3
remove candidate 4 from L1C7
remove candidate 4 from L2C7
remove candidate 4 from L3C8
remove candidate 8 from L1C7
remove candidate 8 from L2C7
remove candidate 8 from L3C8
Starting from version 0.3, it is possible to specify several techniques at
a time in order to probe a sudoku: the argument of the -p option is
a space separated list of technique codes (enclosed between double quotes).
The corresponding techniques are applied in the order specified by the
list. If the applied techniques did introduce modifications,
sudokut also returns the modified sudoku as an 81-chars string. For
instance:
shell> sudokut -p "hs hp ns" 812...5937...1...66..3.5..1..9.8.4...2.7.3.1...5.4.3.....2.6..4....5...8....7.932
insert value 7 at position L1C6 in row 1
Cells L3C7 and L3C8 alone share the same two values 7 and 8
remove the other candidate(s) from these cells
insert value 4 at position L5C1
812..75937...1...66..3.5..1..9.8.4..42.7.3.1...5.4.3.....2.6..4....5...8....7.932
In particular, a technique code can be used repeatedly in a list. The
following example attempts to find three unique candidates:
shell> sudokut -p "uc uc uc" .9...3....6...9.8223.......3..9....8.7..8...4.46...1.778.6...2......57.....73...1
insert value 3 at position L2C7 in row 2
insert value 8 at position L6C1 in row 6
insert value 9 at position L6C8 in row 6
.9...3....6...938223.......3..9....8.7..8...4846...19778.6...2......57.....73...1
Note that the -p option automatically sets the verbosity to (at
least) 3.
Controlling backtracking
Backtracking is the only way of solving completely a sudoku: it is a brute
force method which tries all possible solutions using a trial and
error approach. This is done by sudokut in an efficient and
well organized way, but, while this is something natural for a computer, it
is considered a dishonest (or at least inhuman) way of finding a solution.
One can disable backtracking with the -n option. In that case
sudokut will try to apply all the reduction techniques it knows of, and
will return the (possibly partial) solution thus obtained: for easy and
medium force puzzles like those found in newspapers, this will lead to a
complete solution, but there is no guarantee. On the contrary, if
backtracking is not disabled, all the solutions will be found. To follow the various
techniques used by sudokut, you should set verbosity to 3 (with the
-v option). For instance:
shell> sudoku -n -v 3 .....39483.9..85....4.....25..9.......7.1.6.......7..1692...1..4387..2.91753.....
In order to force the use of the algorithm implementing backtracking (aka
exact cover algorithm), one can specify the -b option. In that
case, sudokut will not attempt any reduction technique and will start
immediately the algorithm.
Modifying a sudoku string
The -m option lets you modify a sudoku string. This is useful when
you want to insert incrementally some solved values and re-apply the
command. The returned value is the new sudoku string obtained after inserting
the new values at the specified position.
For instance, the following instruction inserts a value 6 in the cell L1C4
and a value 4 in the cell L9C7:
shell> sud=.....39483.9..85....4.....25..9.......7.1.6.......7..1692...1..4387..2.917.3.....
shell> sudokut -m 1 4 6 9 7 4 $sud
The command returns the following string:
...6.39483.9..85....4.....25..9.......7.1.6.......7..1692...1..4387..2.917.3..4..
Comparing sudokus
The -d option lets you compare two sudoku strings. For
instance:
shell> sudokut -d 359784612821369745764251839247893561698517324513426987485932176976148253132675498
359784612821369745764251839547823961698517324213496587485932176976148253132675498
Found 6 differences
L4C1: 2 <> 5
L4C5: 9 <> 2
L4C7: 5 <> 9
L6C1: 5 <> 2
L6C5: 2 <> 9
L6C7: 9 <> 5
Verbosity
You can use the -v option to specify the quantity of output you want from
the solver. It is a value between 0 and 4. With value 0, no information
is sent to the console while solving the sudoku: the command will only
return the solution(s). Be aware that with the verbosity set to 4, there
can be a huge amount of output: this value is useful only for debugging
and you should normally use a verbosity of 3 in order to follow the
resolution process.
The default value for -v is 1. The -q option is equivalent to -v 0.
The -e option is a shortcut to set the verbosity to at least 3. It
is what you would use most of the time in order to get a nice report about
the solving process.
Rating a sudoku
sudokut can estimate the level of difficulty of a sudoku puzzle.
This level is an integer value between 1 and 10. This estimation is
obtained with the -l option (l stands for level).
For instance:
shell> sudokut -l 3..4.....615...9844...563...7...4....5.2.3.47.34..5.197685.94..52.64....14....5..
Level 4 (ns,hs,br,np,hp)
The techniques used to solve the sudoku are indicated between parentheses.
In order to obtain just the level, use the -q option:
shell> sudokut -l -q 3..4.....615...9844...563...7...4....5.2.3.47.34..5.197685.94..52.64....14....5..
4
Some sudokus can't be solved using only the reduction techniques and must
resort to the backtracking algorithm: if backtracking is necessary, the level
is followed by a plus sign, like in
shell> sudokut -l 38.6.......9.......2..3.51......5....3..1..6....4......17.5..8.......9.......7.32
Level 7+ (hs,br,np,hp,nq,bt)
If a sudoku has no solution or has multiple solutions, no rating can be
produced: sudokut returns "n/a" with an explanatory message. For
instance:
shell> sudokut -l .........64.8...5.875.....15...7.2.6....9....2.9.8...54.....769.2...8.13..7..5...
Level n/a (multiple solutions)
Ignoring some techniques
With the -i option, one can specify a space-separated list of
techniques that sudokut should not use to solve
the sudoku. For instance:
shell> sud=...3..8..64.8...5.875.....15...7.2.6....9....2.9.8...54.....769.2...8.13..7..5...
shell> sudokut -i "xw nq hq nt ht hp bb hs" $sud
If more than one technique is specified, the double quotes are necessary
to delimit the value of the option as shown in the previous example.
Command pipes
sudokut will read the sudoku strings from standard input when the
last argument on the command line is a single dash (instead of an 81-char string or a file with
the -f option). It is thus possible to use it in pipes. Here is an
example:
head -n 5 somefile | sudokut -
In this example, assuming that somefile is a file containing sudoku strings, the
Unix command head reads only the first five lines of the file and
passes them to sudokut via the pipe.
Any option can be specified for sudokut: the only important point
for the pipe to function is that the last argument be a dash. Here is
another example:
tail -n 10 $somefile | grep -E "^[1-9\.]{81}$" | sudokut -r -q -
In this example, the tail command reads the last 10 lines of somefile, then
the grep command filters the lines containing 81 characters (dots
or digits between 1 and 9) which are finally passed to sudokut for
solving with the -r and the -q options on.
Troubleshooting
Here are a few suggestions if something does not work as expected.
Under Unix, make sure that sudokut is executable ! It must have the x
permission flag set. If it does not, make it executable with the following
command:
chmod a+x sudokut
Make sure that the script has the correct line endings: under Unix
and Mac OS X, it must have Unix line endings (lf). This is normally
the case if you received the script from an official distribution. Under
Windows, the line endings should probably be DOS line endings (crlf).
Make sure that there is a Tcl interpreter on your machine and that it is
found by the shell. For instance, try to execute the tclsh command:
if it brings a Tcl prompt (a line starting with a percent sign), it is fine
(you can then quit it with the exit command and go back to the
shell).
If the command fails to execute sudokus from a file complaining about their
length not being 81 chars, although you know they are correct, this might
also have to do with the file not having the right line endings for your
platform. Try to save your file with different line endings.
Technicalities
Solving techniques
There are several common techniques used to solve sudoku problems. See
some useful links in the
Learn more about Sudokus section below.
sudokut implements several reduction techniques (see in the
Solving techniques section)
If they do not solve the sudoku entirely, it applies an exact cover
algorithm: the method relies on D. Knuth's
dancing links strategy.
The exact cover algorithm guarantees to find all the solutions.
Benchmark
sudokut has been tested with all kinds of sudokus, from easy to
extremely difficult ones. Using the exact cover algorithm, the average time
to solve a medium force sudoku is less than 0.1 second (well, obviously, it
depends on your microprocessor).
sudokut has successfully solved all the
Top95
sudokus, all the
Impossible 520,
all the difficult samples of the
Adobe Standard Library
distribution, and many others.
Learn more about Sudokus
There are many sites and forums on the Internet related to sudokus. Here
are a few links discussing different solving techniques to get you started:
Angus Johnson's page,
Paul Stephens' page,
Glenn Fowler's page
at ATT, or the
SadMan Software's page.
The Sudoku forum covers many
sudoku related topics.
For the mathematically inclined, there is a page on the
Wikipedia discussing more
algorithmic aspects. It also has a nice historical survey.
Download
sudokut is an Open Source Project. Its source code is freely
available and can be freely distributed and modified provided you respect
the licensing terms. If you have code contributions in order to improve
this tool, I'll be glad to include them in a next release.
The code is hosted on the SourceForge site at the following address:
http://sourceforge.net/projects/sudokut.
sudokut releases are available
on the file releases page at SourceForge.
The code is under Subversion control. You can retrieve the latest stage of
development using any Subversion client. See instructions at:
http://sourceforge.net/p/sudokut/code/HEAD/tree/.
The distribution also contains a man page for Unix systems: the file
sudokut.1 should be copied to one of the locations where the man pages are
stored on your machine (e-g /usr/share/man/man1). Then it can be invoked from the
shell with the usual man command like this:
man sudokut
Known problems
Please e-mail any problem or bug you encounter:
<bdesgraupes@users.sourceforge.net>
The official web page is
https://sourceforge.net/projects/sudokut.
There is also a mailing list, sudokut-users, for discussing any
topics related to the usage of sudokut and its development.
You can subscribe or unsubscribe from the following address:
<http://lists.sourceforge.net/mailman/listinfo/sudokut-users>.
To post to this list, send a mail to
<sudokut-users@lists.sourceforge.net>
There is a page dedicated to sudokut on the
Tcl'ers wiki.
Version history
- 2005-11-24 - 0.1 - First public release.
- 2005-12-15 - 0.2 - Implemented new -n, -o, -p, -s options. Implemented
more reduction techniques (block to row/col, block to block, naked pairs,
hidden pairs, x-wing).
- 2006-09-15 - 0.3 - Implemented more reduction techniques (naked
triplets, hidden triplets). Implemented -m option to modify a sudoku string
and -u option to test the unicity of the solution.
- 2007-08-27 - 0.4 - Implemented naked quadruplets, hidden quadruplets
and swordfish reduction. Improved readability of output. Introduced new
options: -e to explain the resolution, -l to rate the level, -i to ignore
some techniques. Added support for shell pipes.
- 2013-06-12 - 0.5 - Implementation of XY-Wing and ALS-XZ reduction. New
option -a to list almost locked sets. Improved method to rate the level of
difficulty. Improved option -k: candidates are now displayed in a grid.
Better display of cell coordinates.
- 2013-06-21 - 0.6 - Implementation of new incremental strategy. New
fish techniques (jellyfish, squirmbag, whale, leviathan).
- 2014-01-03 - 0.7 - Implementation of ALS-XY-Wing technique.
License and disclaimer
sudokut is distributed under the same BSD License as the Tcl language
itself: see the file License_terms in the distribution or
the Open Source Initiative site.
Last updated 2014-01-04 13:01:20
sudokut is hosted by
SourceForge.net