How does it work ?

Previous Suduko solvers that I have see attempt to mimic numerous processes that humans use to solve Sudukos. For this project I have attempted to devise a more mathematical approach ... Then I ran into the 'Guess and Check' problem (see note below).

There two types of operation that are attempted although in reality the 'simple' approach is just a degenerate case of the more complex one. In the following discission I use the terms:-

Term	Meaning
Box	One box, of nine squares, in the puzzle.
Bunch	A bunch of nine related squares i.e. a row, column or box.
Column	One column in the puzzle
Pass	One attempt at solving the puzzle.
Row	One row in the puzzle
Square	One square with a value.

For each 'pass' the logic is as follows:-

For all bunches that are marked as needing update

For all squares in the bunch try the simple solution

If a square was changed mark all bunches related to that square for next update

If any square was changed

Pas is complete ... Exit

For each bunch that is marked as needing update

Try complex solution on the bunch

If any changes were made

Don't waste any more time on complex processing ... Exit

The simple approach

Is really very simple. Initially all squares are either solved, in which case their value mask just has on bit set, or unsolved, in which case the mask has all its bits set. For each bunch a mask is made up containing all the solved squares in that bunch. These are the values that the unsolved squares cannot have so this is inverted and 'anded' into the existing row, column or box mask for all of the non solved squares.

Finally a second pass is made and for each square the row, column and box masks are 'anded' together to yield a mask of possible values. If this only has a single bit set then the square can be marked as solved.

The complex approach

This is where it starts to get interesting. The following assumption is made:-

Within any bunch if a set of n squares can be found that contain n or fewer of the possible values then we know that all of those values have been used (I , possibly inaccurately, call this a closed set). These values can thus be removed from all other squares in the bunch.

For example:-

If a pair squares can be found containing only 4 and 2 then no other square in the bunch can contain 4 or 2.

If three squares can be found containing only 2 and 4 and 5 then no other squares can contain these values.

... and now the difficult bit. If three squares can be found containing 2,4 4,5 and 5,2 by use of 'wildcards' this is the same as the above case so no other square can contain any of these values.

So the problem just comes down to identifying these closed sets. Unfortunately since there are 7! combinations this if a vast processing task. However it can be kept manageable by the following techniques:-

Use the 'simple' approach first. The dramatically reduces the number of possibilities.
It's easier to look for small closed sets than big ones. i.e. Look for pairs first then triples etc.
If you have any success bail out. If a change has been made chances are that the 'simple' approach may now be able to make some more progress.

This is still very much a work in progress. If you want to find out more about the current state of play please consult the source code.

The Guess and Check problem

All of the above is very good but I have found some puzzles where it does not work. A point is reached where some squares have more than one possible value and there appears to be no logical way of determining with is correct. An example of this problem can be seen by 'loading' the pre-defined 'Guess and Check' puzzle. For now the way of solving these seems to be:-

'Solve' as far as is possible.
Find a square with only two possible values.
Enter one of the values.
Hit 'solve' again.
If it worked great.
If it failed re-load, re-solve and enter the other possible value.

Some time soon I intend to automate the 'Guess and Check' process. However it would be nice to think that Suduko are pure logic puzzles. If anyone can tell me a way of logically determining which value is correct, for the example puzzle, it will be much appreciated.