----------------------
ReadMe.txt for
Col's SuDoku Solver v4
----------------------
Hello, and congratulations for downloading Col's SuDoku Solver v4!
Welcome to one of the most powerful SuDoku tools on the web. You are
ready to ally yourself with a flexible suite of problem-solving tools,
and actually learn HOW the computer solves these fiendishly addictive
problems. What's more, you can follow the thinking process yourself
and step through it one stage at a time. Thanks to an advanced array
of analytical techniques, you can now solve nearly all SuDoku puzzles
you will ever come across, and you can do this using logic alone!
There's no guesswork involved, folks!
This ReadMe file is designed to introduce you to how Col's SuDoku
solver works, and how it will help you to improve your problem-solving
skills. It contains three sections:
(1) How to use Col's SuDoku Solver
(2) The Algorithms
(3) What am I working on for new versions?
If you have any comments on Col's SuDoku solver, or if you have
suggestions for the next version, then please feel free to email me
at colin@frayn.net.
Happy solving!
Col
-----------------
Dr. Colin Frayn
22nd August, 2007
colin@frayn.net
-----------------
----------------------------------
(1) How to use Col's SuDoku Solver
----------------------------------
Col's SuDoku solver doesn't need any special installation - it's deliberately
as simple as possible to use. All you need to do is to unzip the distribution
files into a directory somewhere on your hard drive, and then you can start
playing! If you need a copy of WinZip then you can get an evaluation version
from the following website: http://www.winzip.com/
To start the solver, run the SuDoku.exe file.
You will initially be presented with two windows (you can move them around
so that they fit nicely into your monitor, if you wish.) One screen is the
SuDoku grid itself, and the other is the control panel. The SuDoku grid can
be re-sized by using the drag-and-resize control at the corners of the window.
The fonts automatically re-size. In order to set up a new puzzle, either load
one of the bundled data files (see the list below) using the File->load menu
option, or else make your own. You can click on any of the grid squares and
input a number, either using the keypad, or by scrolling with your mouse wheel.
You can also generate random puzzles from the File->New-> menu. This may take
some time for the more difficult puzzles, as they are much harder to generate.
If it is taking too long, then you can cancel the generation procedure at any
time. All puzzles can be saved using the File->save menu option, so that
you can come back to them at a later date.
Contained within the .zip file are:
- SuDoku.exe (The main executable)
- ReadMe.txt (This file)
- Progress.txt (Indicates changes in this version)
- Simple.dat (A simple SuDoku puzzle)
- Complex1.dat, Complex2.dat, Complex3.dat
These are unsolvable using simple methods.
- Unsolved1.dat, Unsolved2.dat, Unsolved3.dat
These are unsolvable without using guesswork methods (Nishio pruning)!
In terms of solving problems, there are two linked methods. The first one is the
basic set of techniques that were included in versions v1.0 and v2.0. That is to say:
#1 'fill in any cells which only have one single permission.' and #2 'if there is
only one cell in any row/column/box that could have a certain value, then it MUST
have that value'. Or, put simply, these two correspond to "Which cells could only
be one possible number?" and "which numbers could only be in one possible cell?"
These two simple rules are available near the top of the control pad, named
"Only one option", and then three boxes named "Box", "Row" and "Col", filling in
values that could only occur in one possible place in every box, row or column.
The "Do All" button repeatedly applies these rules until it can get no further.
And the "Clear" option clears the potential solutions. Potential solutions can
be accepted using the "Update Board" button. At this stage, the solutions become
fixed on the board, though they can still be undone. The Undo/Redo options are
in the 'Edit' menu in the main board window.
Also in the main window menus are options to display the current code version,
to reset the current solution and to load/save a problem file. You can also start
a new puzzle, or exit the programme. In the Help menu, you have the option of opening
an "Explanation Window" which explains in words exactly what the solver has done.
You can get extended information by clicking the "Details" button after highlighting
any particular line. In the "Edit" menu, you can automatically solve, or rate any
SuDoku puzzle, though this solver won't give any feedback - it purely uses a blind
search technique (Knuth's "Dancing Links" algorithm).
Returning to the control panel, you have a second set of buttons towards the
middle of the panel. These deal with the "permission matrix". That is to say, the
possible values available for every cell. By pressing 'Show Permissions' you can
view those values. Pressing the same button again hides them. 'Reset Permissions'
resets the values to their default state after being altered. The default state
is to calculate which numbers are possible by eliminating those numbers which already
exist in the same box/row/column. You can toggle permissions on or off in each
cell by clicking them with the right mouse button.
Moving down the panel, we reach the numbers 1-9, plus a blank button. Pressing any
of these greys out the cells in the board which could not possibly contain that
value. Pressing the blank button resets this to the normal view.
Finally, at the bottom of the dialog box are eight buttons which alter the permission
matrix directly. They are another four logical rules which can be used to eliminate
potential values from the permission matrix using logic alone. Explanations for
these algorithms are given in section (2) below. The last two ("Nishio" and "Forcing
Chains") aren't strictly logic rules, but they are included here for completeness.
------------------
(2) The Algorithms
------------------
Versions 1.0 and 2.0 contained simple solving algorithms, which could be
used to complete most of the simpler SuDoku puzzles. However, the more complex
ones require a substantially more advanced set of methods. In version v3.0 I
introduced some advanced methods for reducing the permission matrix. In v4.0
I have introduced some more complex ones. All permission reduction methods
are listed here;
- Manual permission toggling : You can now manually select/remove permission
values in the permission matrix. To do this, click a permission value with
the right mouse button. With a permission value changed, you can then re-run
the solving algorithms from that stage onwards.
- Undo / redo options : Just in case you get stuck! Note that these reset any
permission values that you have changed.
- I have implemented seven 'reducing candidates' rules. The following web page gives an excellent explanation of these:
http://www.sudoku.uk.com/techniques.php
- I have also implemented the 'Forcing Chains' rule, which helps to solve the
very toughest problems.
For further explanations, try using these methods and examine the help given
in the 'Explanations' window. You can switch this on or off via the 'Help' menu.
Full textual explanations of the major algorithms are given there whenever they
are used.
---------------------------------------
(3) What's Coming Up in Future Versions
---------------------------------------
I have absolutely no idea. Any suggestions?
Your feedback is valuable, and I greatly appreciate it. Thanks for helping
me build Col's SuDoku Solver into (soon, I hope) the web's #1 SuDoku solver
resource!
Cheers,
Col