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