sudokut is a command line Sudoku Solver written in Tcl. This page documents version 0.1.2 of sudokut.
Introduction
Sudoku is a logic game which has recently 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.
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. It comes with a BSD license. See the file License_terms included in this distribution or the Open Source Initiative (OSI) site [L1 ].
Synopsis
The syntax of the sudokut command is:
sudokut options (string | -f file)
sudokut -diff string1 string2
sudokut (-help | -version)
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.
The available options are explained below.
The second form of the script lets you compare two sudoku strings: the command returns the list of all the cells whose value differs. The -diff option can be abbreviated as -d.
In the third form
sudokut -help
sudokut -versionthe script just prints some info in the console window and returns: with -help, it prints the usage string; with -version,it prints the current version number of the script. Note that one can use abbreviated flags like -h or -v for instance.
Command line options
The complete syntax to run the solver is:
sudokut [-c] [-g] [-q] [-r] [-t] [-v num] (string | -f file)
The options have the following meaning:
In all the examples below, shell> designates your shell prompt.
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...
-----------------------
| 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 |
-----------------------
Checking the validity
You can check whether if a sudoku is valid (i-e does not contain incompatible cell values) using the -t option. For instance:
shell> ./sudokut -t ...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 -t ...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 -t 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...
Found 1 solution
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...
Found 1 solution
192356847643817952875429631584173296761592384239684175458231769926748513317965428
Counting the solutions
If the -c option is specified, the command will only count the solutions. For instance:
shell> ./sudokut -c 3.......2..13697..7.4...8.9...8......9.....2....4.6...4.5...1.6..614.2..1.......8
Found 7 solutions
Note that with the -c option, the verbosity is automatically set to 0.
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.
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:
./sudokut -f /home/bernardo/puzzles/mysudokus.txt
./sudokut -f ~/puzzles/mysudokus.txt
./sudokut -f ../puzzles/mysudokus.txtThis last example assumes that the sudokut script is located in 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:
./sudokut -t -f ~/puzzles/mysudokus.txt
Comparing sudokus
The -diff (or just -d) option lets you compare two sudoku strings. For instance:
shell> ./sudokut -diff 359784612821369745764251839247893561698517324513426987485932176976148253132675498
359784612821369745764251839547823961698517324213496587485932176976148253132675498
Found 6 differences
(4,1): 2 <> 5
(4,5): 9 <> 2
(4,7): 5 <> 9
(6,1): 5 <> 2
(6,5): 2 <> 9
(6,7): 9 <> 5
Both sudoku strings must be valid: sudokut will return an error if they are not.
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 3. 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 3, there can be a huge amount of output: this value is useful only for debugging and you should normally use a verbosity of 2 in order to follow the resolution process.
The default value for -v is 1. The -q option is equivalent to -v 0.
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 get 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
There are several common techniques used to solve sudoku problems. As of version 0.1, sudokut implements the Naked Single and Hidden Single reduction techniques. If they did not solve the sudoku entirely, it then applies an exact cover algorithm: the method relies on D. Knuth's dancing links [L2 ] strategy. The exact cover algorithm guarantees to find all the solutions. Future versions of sudokut will implement other reduction techniques.
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
Please e-mail any problem or bug you encounter: [email protected]
sudokut is distributed under the same BSD License as Tcl