sudokut

sudokut is a command line Sudoku Solver written in Tcl. This file documents version 0.2 of sudokut.

Introduction
Usage
Synopsis
Description
Command line options
Examples
Displaying the grid
Checking the validity
Solving the sudoku
Counting the solutions
Processing a file
Getting suggestions
Probing a sudoku
Disabling backtracking
Comparing sudokus
Verbosity
Troubleshooting
Technicalities
Known problems
Version history
License and disclaimer

Introduction edit

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 [1].

Usage edit

Synopsis edit

The syntax of the sudokut command is:

         sudokut options (string | -f file)
         sudokut -diff string1 string2
         sudokut (-help | -version)

Description edit

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 -version

the 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 edit

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:

the -c option tells sudokut to only count the solutions;
the -f option is used to specify that the last argument of the command is a file;
the -g option displays the sudoku strings as a 9x9 grid;
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 (aka brute force method);
the -o option means only one solution. It tells the script to return 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 a particular technique. The command returns the information which can be obtained with the specified technique. Techniques are designated using a short code: see below the list of supported codes;
the -q option lets the command execute silently (it is equivalent to setting the -v option to 0);
the -r option tells the command to return the solutions as raw strings rather than 9x9 grids;
the -s option lets you ask for a suggestion about the next possible step to solve the sudoku;
the -t option lets you test the validity of a sudoku string. It will report an error if it finds incompatibilities between the rows, columns and blocks;
the -v option lets you specify the verbosity: its value is a number between 0 and 3 which indicates how much information you want sudokut to write to the console while solving a problem. The default value is 1. Note that the -c option sets verbosity to 0 and that the -s and -p options set it to 2, overriding the -v option.

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.

Examples edit

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

Displaying the grid edit

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 edit

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

Solving the sudoku edit

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 edit

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.

Processing a file edit

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

This 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

Getting suggestions edit

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.

Probing a sudoku edit

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.

Disabling backtracking edit

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

Comparing sudokus edit

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 edit

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 edit

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 edit

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 [2] strategy. The exact cover algorithm guarantees to find all the solutions. Future versions of sudokut will implement other reduction techniques.

Known Problems edit

Version history edit

License and disclaimer edit

Download edit

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: bdesgraupes@users.sourceforge.net

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 [3] 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 [4].

(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:

naked quadruplets reduction.
hidden quadruplets reduction.
swordfish reduction.
new option -e to put in explanatory mode.
new option -i to ignore some solving techniques.
new option -l to rate the level of difficulty.
support for pipes: sudokut can now read from standard input.
improved readability of messages.

Category Application

Category Toys

Category Games