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

   1. Introduction

   1. Usage

   1. Synopsis

   1. Description

   1. Command line options

   1. Examples

   1. Displaying the grid

   1. Checking the validity

   1. Solving the sudoku

   1. Counting the solutions

   1. Processing a file

   1. Getting suggestions

   1. Probing a sudoku

   1. Disabling backtracking

   1. Comparing sudokus

   1. Verbosity

   1. Troubleshooting

   1. Technicalities

   1. Known problems

   1. Version history

   1. License and disclaimer

----


'''''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. 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 [http://www.opensource.org/licenses/bsd-license].


'''''Usage'''''

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

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


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

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

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

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

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. 
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 [http://www-cs-faculty.stanford.edu/~knuth/papers/dancing-color.ps.gz] 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: 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 [http://www.simes.clara.co.uk/programs/sudokutechniques.htm] 
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 [http://www.sudokusolver.co.uk/solvemethods.html].

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

<<categories> Category Application | Category Toys | Category Games