SUDOGNU(1) User Commands SUDOGNU(1) NAME sudognu - manual page for sudognu version 1.09 SYNOPSIS sudognu < command > [ options ] DESCRIPTION sudognu can solve and create sudokus. It can print 4 sudokus to a pdf or an svg page and it comes with example cgi scripts for integration into www sites. EXAMPLES sudognu -s -v 1 < sud.in > sol.out solve sudokus sudognu -c -n 20 > sud.out create 20 sudokus sudognu -p -o sud < sud.in print 4 sudokus to sud.pdf & sud.svg Commands (only one of these may be present): -c create sudokus and print four of them to pdf/svg file -p read sudokus from stdin and print four of them to pdf/svg file -s read sudokus from stdin and solve them -w read one sudoku and candidates from stdin and generate a html table -N read sudokus from stdin and canonicalize them (output to stdout) -h display usage information -V display version and copyright information Options (not all options work for every command): -n num_sudokus number of sudokus to create -i file read sudokus from file and not from stdin -o file html or pdf file name for formatted output -P sol_techn apply solution techniques according to sol_techn The sol_techn string must consist of the characters ".-dDbBt- TqQXcSJF" in arbitrary order. ".-dDbltTqQXcSJF" is the default, when -P is not present. For further explanation of the sol_techn string use the -h command (or see "Sudoku solving" below, if you are looking at the documentation). -v verbosity for explaining solution techniques (one of 0, 1, 2, 10 or 11) -f wsudognu location of wsudognu.cgi wsudognu.cgi is a script necessary for processing the sudoku urls created for the -s command with a verbosity of 11 (default value for wsudognu is ./wsudognu.cgi) -t use one thread for each available CPU (no pdf/svg file will be created) -S symmetry create axi- or point-symmetrical sudokus Slow; symmetry is 'a' or 'p'. Sudoku format: The input and output format for sudokus uses one string per sudoku: concatenate the 81 numbers line by line from top left to bottom right without white space between the numbers. Empty fields are to be denoted by "0" (zero). Sudoku solving: Various elimination techniques for solving sudokus are implemented, starting with easy techniques such as singles and hidden singles. Com- plex techniques for candidate elimination (tuple / hidden tuple, line-block interaction, forcing chain, X-wing, swordfish, jellyfish) are applied only if necessary, reverting to backtracking (guessing) at last resort. Solutions are checked for uniqueness. sudognu can display the solution process. When you set verbosity to 2, sudognu will display a string of characters, each one stands for one solution step: . hidden single - single d hidden double D double b line-block interaction B block-line interaction t hidden triple T triple q hidden quadruple Q quadruple W xy-wing Y xyz-wing X X-wing c two-color S swordfish J jellyfish F forcing chain to a common value with length of forcing chain f forcing chain to a contradiction for one of the branches e forcing chain to the end of the sudoku g guess during backtracking process w last guess turned out to be wrong. The default order for applying the solution steps is to start with hid- den singles and singles before trying to eliminate candidates with hid- den tuples and tuples from doubles to quadruples. Line-block interac- tions are applied between doubles and triples. Then the more complex techniques X-wing, 2-color swordfish and jellyfish are used and if all these fail. Forcing chains are tried, before reverting to guessing and starting a backtracking process. You can influence the order, in which the techniques above are applied, by means of the -P option. As described above, the default order is ".-dDbBtTqQWYXcSJF". If you want the steps to be applied in a different order, just shuffle these characters and pass them to sudognu with the -P flag. The sudoku solution performance can be improved greatly, if you leave out the 'q', 'Q' and 'J' techniques, which occur only very rarely, but need a lot of computation time. Forcing chains are not applied during backtracking (i.e. after the first value had to be guessed). While searching for forcing chains, only a subset of the available techniques is applied. Forcing chains are only tried for cells with two candidates. All of such cells are checked and sudognu will apply the shortest forcing chain it finds. Since only one solution path is evaluated for each possible starting cell of a forcing chain, sudognu does not always find the shortest forcing chain. Sudoku generation: All sudokus generated by sudognu are minimal sudokus, meaning that all givens are required to ensure a unique solution to the sudoku. Option- ally symmetric sudokus can be generated by specifying '-S' on the com- mand line. Generation of symmetric sudokus requires much more time than the generation of unsymmetric sudokus. It is not possible to specify a desired difficulty rating for genera- tion of sudokus. To produce sudokus with a certain difficulty, just create a whole batch (say 100) and pick the ones with the desired dif- ficulty. Sudoku rating: At first the sudoku is assigned a basic rating of 1, 10 or 100, depend- ing on the most difficult technique required for its solution: a basic rating of 1 is assigned for the techniques .-d a basic rating of 10 is assigned for the techniques DbBtTqQ a basic rating of 100 is assigned for the techniques WYXcSJFfeg. Next, each solution step is assigned a difficulty rating, starting with 1 for hidden singles up to 18 for guesses during the backtracking process. In each step the two easiest applicable techniques are taken into account. The individual ratings for each solution step are added to the basic rating. Finally, 1 is subtracted from the sudoku rating for each cell to be solved. The smallest possible rating of 1 is assigned to a sudoku, if there are always at least two choices for the application of the hidden singles technique in the solution path chosen by sudognu. AUTHOR Written by Jens Baaran REPORTING BUGS Report bugs toCOPYRIGHT Copyright © 2007-2009 Jens Baaran (http://baaran.de) This is free software. You may redistribute copies of this software under the terms of the GNU General Public License Version 2, June 1991 (http://www.gnu.org/licenses/gpl-2.0.html). There is NO WARRANTY, to the extent permitted by applicable law. The authors of this software cannot be held responsible for any damage it may cause. sudognu version 1.09 March 2009 SUDOGNU(1)

created with: # man sudognu.1 | col -b

© 2007-2009, Jens Baaran, Germany.