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
Prerequisites
Usage
Execution
Examples
Troubleshooting
Technicalities
- Solving techniques
- Benchmark
Learn more about Sudokus
Download
Known problems
Version history
License and disclaimer

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

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