'''sudokut''' is a command line Sudoku Solver written in Tcl. This page documents version 0.1.2 of '''sudokut'''. 1. Introduction 1. Usage 1. Synopsis 1. Description 1. Command line options 1. Displaying the grid 1. Checking the validity 1. Solving the sudoku 1. Counting the solutions 1. Processing a file 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. '''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]. '''''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 compiler is: sudokut [-c] [-g] [-q] [-r] [-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 ''-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 as 9x9 grids; * the ''-t'' option lets you check 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; ---- 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.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 '''''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. 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. ---- Please e-mail any problem or bug you encounter: bdesgraupes@users.sourceforge.net '''sudokut''' is distributed under the same BSD License as Tcl