sudokut is a command line Sudoku Solver written in Tcl. This file documents version 0.2 of sudokut.
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. 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. If you're looking for a graphic interface you should see the Sudoku page on this wiki.
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 ].
The syntax of the sudokut command is:
sudokut options (string | -f file)
sudokut -diff string1 string2
sudokut (-help | -version)
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.
The complete syntax to run the solver is:
sudokut [-c] [-g] [-n] [-o] [-p code] [-q] [-r] [-s] [-t] [-v num] (string | -f file)
The options have the following meaning:
Here is the list of the currently available codes to use with option -p:
.________.__________________________________.
|''Code''|''Description'' |
|ns |naked single |
|hs |hidden single |
|np |naked pairs reduction |
|hp |hidden pairs reduction |
|br |block to range (row/col) reduction|
|bb |block to block reduction |
|xw |x-wing reduction |
|________|__________________________________|
Alternatively, one can use lc (lone candidate) instead of ns and uc (unique candidate) instead of hs.
In all the examples below, shell> designates your shell prompt. It is assumed there that the sudokut script is automatically found by the shell (invoked as sudokut rather than ./sudokut).
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 | . . . |
+-----------------------+
You can check whether if a sudoku is valid (i-e does not contain incompatible cell values) using the -t option (t stands for test). 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
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
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 and the -o option is ignored.
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
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 a 81-chars string, for re-use with the -s option in order to take a further step. For instance:
shell> sudokut -s ...1..754.45..........65...1....698.5.......2.798....6...57..........23.387..1...
Hidden single in row 3: insert value 4 at position (3,4)
...1..754.45.........465...1....698.5.......2.798....6...57..........23.387..1...The returned string has value 4 inserted at position (3,4) and can be used in a new sudokut -s command.
The -s option returns only the first meaningful result 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.
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 Command line options section for a list of the currently available codes). For instance, probe the following sudoku with the Block to range (row or column) reduction technique (code br) like this (excerpt of the output):
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 cell (6,4)
remove candidate 6 from cell (6,5)
Value 6 for block 8 can only be in row 9
remove candidate 6 from cell (9,1)
remove candidate 6 from cell (9,3)
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 (1,9) and (3,9) have only the same two values 4, 8:
remove these candidates from the other cells in column 9
remove candidate 4 from cell (5,9)
remove candidate 8 from cell (5,9)
remove candidate 8 from cell (6,9)
Cells (1,9) and (3,9) have only the same two values 4, 8:
remove these candidates from the other cells in block 3
remove candidate 4 from cell (1,7)
remove candidate 4 from cell (2,7)
remove candidate 4 from cell (3,8)
remove candidate 8 from cell (1,7)
remove candidate 8 from cell (2,7)
remove candidate 8 from cell (3,8)
Note that the -p option automatically sets the verbosity to 2.
Backtracking is the only way of solving completely a sudoku when all the other techniques have been applied: 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. To follow the various techniques used by sudokut, you should set verbosity to 2 (with the -v option). For instance:
sudoku -n -v 2 .....39483.9..85....4.....25..9.......7.1.6.......7..1692...1..4387..2.91753.....
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.
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.
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.
There are several common techniques used to solve sudoku problems. See some useful links in the
Learn more about Sudokus section below.
As of version 0.1, sudokut implements the Naked Single and Hidden Single reduction techniques. Version 0.2 added the following: block to row/col, block to block, naked pairs, hidden pairs, x-wing. 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.
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
KPV A couple of comments. First, David Easton's Sudoku program has built into it a sudoku solver (it uses it to generate new playable boards). If you unwrap the starpack, you'll see in the file sudoku-solve.tcl the code that tries 4 different rules to solve a puzzle. Second, here's [L3 ] a really good web site detailing over 10 rules, some exceedingly complex, that you can use to solve the puzzle. It also has example boards where each of the different rules is needed to solve them. Another good web site for sudoku solving techniques is [L4 ].
(bernard) Version 0.2 of sudokut precisely implements several of the techniques explained on the sites you mention: naked singles, hidden singles, naked pairs reduction, hidden pairs reduction, block to range (row/col) reduction, block to block reduction, and x-wing reduction.
HJG A new version Sudokut 0.3 was released on 2006-09-15.
HJG A new version Sudokut 0.4 was released on 2007-08-27.
New features: