The core of the program is a fast puzzle solver. The solver starts by generating a list of possible candidates for each empty cell. The solving starts by filling the cells with a single candidate. For cells with more than one candidate, each candidate is tested at a time. This is coded using a simple, recursive algorithm.
Sudoku puzzles are generated starting with an empty board. This "puzzle" is then solved. A special version of the algorithm is used: The list of candidates for a cell is permuted before each possibility is tested. This produces random puzzles.
The numbers are now removed one by one. If the puzzle does not have a single solution the number is inserted again. The numbers are removed in a random order, taking the desired symmetry into account.
When no more numbers can be removed, a special version of the solver is run. This uses additional algorithms. This solver is slower, but is used to classify the difficulty of the puzzle.
A Sudoku puzzle is normally solved like this:
Make a list of possible candidates for each empty cell.
If a cell has one candidate only, choose this, and update the list of possible candidates for the other cells.
If the algorithm keeps finding cells with a single candidate, classify the puzzle as Very easy.
If a cell with a single candidate doesn't exist, the program looks for rows, columns, or boxes where a number can only be in a single cell. Puzzles solvable using this and the first algorithm are classified as Easy.
The program looks for rows or columns, where the candidates for a number all lies within a box. The number is then eliminated from other cells in this box outside the row or column. Puzzles of this type are classified as Medium.
The program looks for subsets of n numbers, occupying n cells. Other candidates for these n numbers can the be eliminated from the row, column, or box. E.g., if two cells on a row both have the candidates 4 and 7, one cell must be 4, and the other 7 (or vice versa). The numbers 4 and 7 can then be eliminated from the other cells on the row. Puzzles of this type are classified as Hard.
Puzzles that can't be solved using these algorithms are classified as Difficult. This can be solved by guessing on one of the candidates and continue the solving. If the solving process reaches a dead end, it goes back and select the next candidate for the cell.
More algorithms are available, but these havn't been added to this program (yet). The algorithm used for the Hard-classification is a bit tricky, as it requires a big lookup-table. This is the reason why I havn't made any 5x6 puzzles of this level.
Sudoku puzzles look nicest, if they are symmetrical.
The program uses three kinds of symmetry: None, mirroring in the x and y axes, and 180° rotation.
Puzzles created without symmetry are created without taking symmetry into account, so by chance, they could turn out being symmetrical!
Symmetrical puzzles are faster to produce, as more than one number are removed at a time.
Symmetrical puzzles can contain extra numbers, i.e. numbers that can be removed, and the puzzle still has only one solution.
In short - you don't! But there is a trick:
Start a text editor (e.g. notepad in windows) and type in the puzzle. Empty cells are written as 0 (zero). A puzzle could look like this:
000650 003000 500000 000002 000300 012000
Copy the numbers with the mouse, and select Paste then the Sudoku program. Prior to this, the size of the puzzle should be selected, in this case 2x3.
The program produces approx. 540 3x3 Sudoku puzzles (x/y mirror symmetrical) per second on a 3.6 GHz Xeon machine.
Larger puzzles can take much longer to produce, several minutes. I've added a limit on how many times the recursive solver may be called (p.t. 100000 times), this cuts down on the run time.
If you download the source code (the .zip or .tar.gz files), and compile the program, a batch version of the program is created as well as the normal interactive.
The batch version produces puzzles of the requested size and symmetry. The puzzles are written out on the console in a format suitable for reading into MySQL database. Scripts on the home page query this database and present the puzzles as HTML or PDF.
The source code for these scripts are included in the .tar.gz and .zip files.
The license for the program and the scripts on the homepage is GPL, described here.
In short, this license means that you can do almost everything with the source code, as long as you make your new source code publicly available, e.g. on a home page. You should explain in the source code what you have done to it, and you can't change the license.
Puzzles produced by the program may freely be distributed, with a reference to this home page.
If you're stuck with a puzzle, you can use this trick to get a hint:
Click on Show solution, and on that page you click on Show explanation. The solution is now shown together with the steps necessary to solve the puzzle.
If you're stuck with a puzzle that you have printed out, you can
find the puzzle on the home page by entering its number on
this page.
If you ask for 20 puzzles on the PDF page,
and only 14 are returned, it is because the database only contains
14 puzzles of the requested type. Try to extend the search with different
types of symmetry. Yes, every night new 2x3 and 3x3 puzzles are added. Larger puzzles are produced "sometimes". Every time a puzzle is display, the date and time is registered
in the database. Puzzles, that havn't been shown, are displayed first. Please note that if you ask for rare puzzles, puzzles that have
been shown previously will be displayed again. I've had my ADSL connection upgraded to a Gigabit connection (1000/1000), so this shouldn't be a limitation any more. The database contains millions of puzzles, so it can
take some time to fetch the information, especially with several concurrent users. More than 10000 have fetched this program, so there is a great interest in Sudoku! I use the MinGW compiler for compiling under Windows. Get and execute the file MinGW-3.1.0-1.exe from
http://www.mingw.org/download.shtml.
The file is located a little more than halfway down the page. This is not the latest version, but it is the easiest
to install. Rename mingw32-make.exe to make.exe in the c:\mingw\bin
folder. Add c:\mingw\bin to the path. On an English Windows 2000 this is done
by right-clicking on "My Computer", select Properties,
Advanced, Environment Variables, System variables, select PATH,
edit and append ";c:\mingw\bin". Unzip the source code zip file, open a command prompt, cd to the
unzipped files, and write the command: make windows This will generate sudoku.exe and the batch version of the program,
bsudoku.exeWhy does it only return 14 puzzles when I've asked for 20?
Will new puzzles be added to the home page?
Why is the home page so slow?
How do I compile the program myself on a Windows machine?
Mogens Kjær, mk@lemo.dk