Introduction
fu-sudoku is the Freaks Unidos' set of tools for working with sudokus.
It was written by Alejandro Forero Cuervo while he was traveling to Venezuela, during some long and lonely evenings. You might want to contact him by writting email or Jabber messages to azul@freaks-unidos.net.
You can see a sample of challenges generated by fu-sudoku as well as the render to HTML here:
fu-sudoku consists of the following command line programs writen in Chicken Scheme:
- sudoku
- Generates a challenge and prints it to its standard output. Since this operation takes a bit of time, progress information is printed to the standard error output.
- sudokutohtml
- Receives a sudoku from the standard input and produces to its standard output an HTML representation that can be used to play it on a browser.
- sudokushow
- A CGI application that can be used to browse a library of challenges and play them.
- sudokusolve
- Receives a (possibly incomplete) sudoku from standard input, solves it and prints the results to its standard output.
- sudokugenloop.sh
- A simple shell script that repeatedly calls sudoku to produce sudokus to some directory.
Solving challenges
Solving challenges is easy, one merely needs to apply backtracking / brute force, which seems to be rather fast.
Our solver procedure will return two values:
- A solution, selected non-deterministically (assuming the challenge has multiple solutions).
- A procedure that can be used to resume the backtracking and produce two new values (solution and resuming procedure).
Generating challenges
Basic Algorithm
The algorithm for generating challenges is the following:
- Randomly find a valid way to fill all positions (a solution).
- Based on the solution produce a challenge by iteration. Start with a table where all numbers are allowed in all positions and:
- Pick a position and modify the table so only its actual number is allowed on it. This number will be given explicitly in the actual challenge.
- Use the deduction rules described below to disallow numbers based on the new information.
- If at least one position has more than one allowed number, go back to step 1.
Step 2.1 picks the position that maximizes the number of deductions that can be made. This makes the algorithm run around 60 times slower (!) than it would if it took just any random position but tends to increase the number of blank spaces in the resulting challenge.
Rules
To make deductions we use the following logic rules, given as a premise and deduction.
Our goals for this set of rules is:
- It should be very simple to formulate (ie. it should be easy to program)
- It should be possible to program it efficiently (ie. it should run fast)
- It should be reasonably complete (ie. it should get the work done)
We believe our current set, of two rules, is very good. However, if you think you can come up with another that you think we should use, please let us now!
Definitions
Box
A box is one of the 9 predefined [[Markup error or TexVC not found]] matrices.
Region
A region is a column, row or box.
Counting Rule
If for some [[Markup error or TexVC not found]] some region has [[Markup error or TexVC not found]] positions where only [[Markup error or TexVC not found]] different numbers are allowed, then those numbers will not be allowed in other positions in the same region.
Explanation
This rule, depending on the value of [[Markup error or TexVC not found]], encapsulates a set of different rules:
- with [[Markup error or TexVC not found]] the rule can be stated as: if one position only has one allowed number, then the number is disallowed elsewhere in the position's regions.
- with [[Markup error or TexVC not found]] we get "naked pairs";
- with [[Markup error or TexVC not found]] we get "naked triples";
- with [[Markup error or TexVC not found]] we get "hidden triples";
- with [[Markup error or TexVC not found]] we get "hidden pairs"; and
- with [[Markup error or TexVC not found]] the rule can be stated as: if a position is the only one from a region where a certain number is allowed, then all other numbers are disallowed in that position.
The reason we don't try with [[Markup error or TexVC not found]] is that "naked quads" and "hidden quads" (the conclusions we could infer with those values) that can't be deduced with the other rule or other cases of this one seem to be extremely rare.
Intersections Rule
If for two different regions [[Markup error or TexVC not found]], where exactly one of them is a box, a given number is not allowed in [[Markup error or TexVC not found]], it will no longer be allowed in [[Markup error or TexVC not found]].
Explanation
This should be a pretty straight forward rule: If the number can't be in [[Markup error or TexVC not found]], then it has to be in [[Markup error or TexVC not found]] (since it has to be in [[Markup error or TexVC not found]]). But then, it can't be in [[Markup error or TexVC not found]].
Note that we only need to consider the case when either [[Markup error or TexVC not found]] or [[Markup error or TexVC not found]] but not both are boxes:
- If [[Markup error or TexVC not found]] is a row and [[Markup error or TexVC not found]] a column or viceversa, [[Markup error or TexVC not found]]. In this case, deductions made by this rule can already be made by repeated applications of the counting rule:
- the first application, with [[Markup error or TexVC not found]], deduces that the number is the only one allowed in [[Markup error or TexVC not found]]; and
- the second application, with [[Markup error or TexVC not found]], deduces that it is not allowed in [[Markup error or TexVC not found]].
- If [[Markup error or TexVC not found]] and [[Markup error or TexVC not found]] are the same type of region, [[Markup error or TexVC not found]] and the condition of this rule will never hold (since every region must have every number).
Storage
Numbers in a sudoku are packed as a stream of 81 numbers from left to right, top to bottom. A value of 0 represents an empty (yet unknown) position. Each number is encoded as its corresponding byte.
Previous versions packed two numbers into one byte using 4 bits each. We decided to simplify and use one byte for each number to make it possible for future versions to work with sudokus with a greater size (using numbers greater than 15). However, we decided not to make it possible to use sudokus with numbers greater than 255 since we don't think that will ever be useful.
Source code
The source code for fu-sudoku is available under the GNU GPL license. It is available here:
You can use "anonymous" as the login and the empty string as the password.
Last update: 2006-11-01 (Rev 9104)