SOKUKU - a program to help solve and create Sudoku puzzles Copyright (C) 2005 Andy Pepperdine 1 Clan House, Sydney Road, Bath, UK, BA2 6NS This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License in the archive for this program; if not, write to the Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA Installation Everything that is required to run and modify this program is held in the Java archive file, usually distributed as Sokuku-.jar To install it, merely place it in any convenient directory. To execute it with Java on a Unix machine, call it with java -jar Sokuku-.jar from any convenient directory. The options it can take on the command line are: java -jar Sokuku.jar [[-n]] [-p ] [-s ] [-y ] [-b ] [-x] [-[m|M] ] [-v] [-h] -n is either the number of rows and columns in each box or is of the form x, where is the number of rows, and the number of columns in each box. The number of cells in a box must be not more than 25. -p is a string of candidates as characters, left to right, top to bottom. Whitespace and the characters in [-_=+|!*¦] are ignored. Characters not in the candidate set do not assign a value to the cell. -s is any character string to be used to start the random number generator when creating puzzles. If -p is not specified, then a puzzle is generated immediately. -y specifies the type of symmetry: 0 no symmetry 2- 2-way reflected in x-axis 2| 2-way reflected in y-axis 2\ 2-way reflected in the NW-SE diagonal 2/ 2-way reflected in the NE-SW diagonal 2o 2-way rotation (default) 4+ 4-way refection in x- and y-axis 4x 4-way reflection in both diagonals 4o 4-way rotation 8 8-way reflection in both axes and diagonals -b is a string containing the candidate characters -d is a string of letters identifying the rules which are to be disabled when solving or creating puzzles. a Triangles c Chains g Groups l Loops n Nets p Pairs s Segments t Twins e Trial and error -x suppresses the interactive display, tries to solve the pattern, prints the steps onto the standard output, and then quits. Useful in conjunction with -s to create puzzles. If -s is not also specified, a seed is generated from the current time -[m|M] is the number of puzzles to generate. If -m is given, only the initial grid and basic statistics for each puzzle are printed for. If -M is given, only the puzzle grids are put out one per line. If -x is not also specified, this option is ignored. -z use names for cells, rows, columns and boxes that are the same as are found in internet discussion forums. -v prints the version number and quits immediately. -h prints this message and quits immediately. To drive it, just remember that left click performs some action, and right click gives information. Note that the display is fine for boards of size 3, but for 4, the characters are getting closer together, and for 5, they are really impractical, but I've not had the time to spend on making it easier. In the archive there is an html file, Sokuku-en.html, that your browser can view and display the program. The two files, Sokuku-en.html and Sokuku-.jar must reside in the same directory for this to work, although if you write your own HTML to invoke this applet, then you have more freedom how you do it. You will need a Java plug-in for your browser, but most now come with this already installed. The html file may also be distributed separately. Parameters to the applet are: "size" is either the number of rows and columns in each box or is of the form x, where is the number of rows, and the number of columns in each box. The number of cells in a box must be not more than 25. "seed" is any character string that will be used to prime the random number generator when creating new puzzles. "pattern" is a string representing the position to initialise the board with. The characters are assigned to the cells left to right, top to bottom. Whitespace is ignored. Characters that are part of the diplay set of values are assigned to the cell. Other characters leave the cell unassigned. Warnings There are no known bugs, but there is plenty that could be improved and new features added. There are puzzles that the rules cannot solve. To get the solution to these, the program reverts to trial and error, but there is no hint button to do that. If you do not turn off the "trial and error" rule (by -de or by the settings button), then some of the puzzles it creates will require experimentation. New rules are always welcome, so long as they are not already covered by an existing rule. Implementation comments The program is written in Java 1.4 for ease of development and cross-platform use, and was a learning exercise for me in both Java and window interfaces, in neither of which had I any previous experience. It is adequately fast for 3x3 boards. For 4x4 boards, the speed of creation of a new puzzle is such that only a very limited amount of effort is put into optimising it. For 5x5, you will have to be patient and no optimisation is done at all. This makes for much simpler puzzles, and the real challenge is in handling the size of the boards. Considering the computational load the generation algorithms apply, this is a credit to Java as an interpretive language. The internal construction relies on a set of classes in Sudoku.Engine, which contains a self-contained engine for doing all the internal logical deductions and reporting reasons for the actions taken. It relies on nothing other than the Java language classes. To drive the engine, the order of events is: 1. Instantiate all the cells (class Cell) that are on your board. 2. Instantiate all the tuples (class Tuple) that group together the cells into sets that must contain all the possible values. 3. Instantiate a board (class Board) from the set of Tuples. 4. Call the various methods in Board to do the various logical deductions and get reasons for the results from the class Reason. It assumes nothing about the shape and size of the board or tuples, merely that each tuple should be full, and that all tuples contain the same set of values in a solution. So far as the engine is concerned, it could be operating on a set of tuples that you think are in any dimensional space (cubical Sudoku anyone?). An extension to restrict the possible values allowed in each cell would be easy as the mathematical structures are general. Further details can be found at www.pepsplace.org.uk Acknowledgements The basic idea for the display was already in use by Andrew Stuart on www.scanraid.com/sudoku.html, but this is a major re-organisation. The rules are all mine, although some are very rare. The pairs rule is a special case of the loops rule, and was brought to my attention by an anonymous poster referred to from the scanraid site. The coding and algorithms are, to my knowledge, all original. "A poor thing, Sir, but mine own". Andy Pepperdine 2005-08-19 rev: 2005-09-25 rev: 2005-10-17 rev: 2005-11-22