The "odometer" function, tries to solve the puzzle, by using each square of the puzzle, like a wheel on your
* Welcome to the Details Pages *
I began coding this program the same day I began playing Sudoku for
the first time. I've rewritten the first couple of functions which
were somewhat unclear. This was a program of discovery for me, not
a carfully designed algorithm I was already familiar with. I wanted
to include two things - an odometer function, and a very fast function
to solve the puzzle, when desired.
Three arrays of possibles are built up, for every square - row, column,
and box. These three array elements are then compared. Only numbers
that are in all three arrays, are kept. The rest are deleted, since
they can't be a valid number for that square.
Now the second phase begins. Squares with just a single possible
(solo's), are elevated to permanent status. Every other square in
that square's unit (row, column or box), is checked to see if it's
possibles need to be changed as a result.
Next, each unit is checked for 'must be's'. These exist when a unit
has only * one * three (for example), in all it's squares' possibles.
That means that square must be a three, regardless of other possibles.
In the MustBe functions, these are found, and elevated. Each affected
unit squares' possibles, are updated as well.
The outside rule of pairs is used next, to look for matching pairs
of possibles, which may be shared by other squares' possible values.
In a unit like this row:
1 2 3 4 5 6 7 8 9 <== Column #'s
25 13 478 389 16 256 89 25 49 <== Possibles
The outside rule of pairs function finds #1 and #8 to have the same
pair of values. Knowing this, #1 must be either a 2 or a 5 and #8 must
be the other number. So * no * other valid possibles can be a 2 or a
5! Which means #6 is changed to just a 6, which makes it a solo, and gets
#6 elevated. Which means also that #5 can't have a 6 in it's possibles.
It becomes just a solo 1, which in turn means that #2 becomes just
a solo 3.
* Welcome to More Details *
In Sudoku, everything you change, can change many other things. Which is
why it's important to loop back through stage two and later functions,
after you've made changes. In this program, looping back through stage two
and above, twice, is required. Three times is never helpful, however.
Each new puzzle grid that you want checked for a solution, will require all
these functions to be called, from stage one, right on up. This sounds
like a rude waste of time, but it's the only way, using my algorithm. These
functions run very fast!
Easy puzzles are solved outright by stage two. Most puzzles need a bit
of trial and error, however. This is the last stage of the program.
I solve this with two functions, each uses a different approach to the
problem. The first one is a virtual odometer function. The squares
with no known value, are 'strung' virtually, next to each other, like
the wheels of an odometer. The possibles for each square, are the numbers
on each wheel. Now we turn the wheels, just like an odometer, and test each
resulting puzzle, to see if it's the solution. To make this work, the
lowest possible original values are assigned to the squares, by Odometer.
The actual incrementing is done by the Increment function, which is called
by Odometer, at the first square it can't assign a good number to. If
Increment can find a good value, it's assigned, and the program returns
to Odometer, for further assignments. It's a back and forth dance, by two
functions working together.
Odometer can solve puzzles which have their solutions in the lower part of
the puzzles search space, with adequate speed. Puzzles which have their
solution in the upper part of their search space, and particularly if that
search should require 'driving' the odometer from the 8th or 9th row -
are a sheer horror!
The second function is MagicTouch, an efficient speed-burner at solving.
It scans the board and id's some squares with only two possibles left. That
squares's array subscript is put into a small array called least(n). Now
MagicDat is called to prepare the dat file templates MagicTouch will use
to set the values of each of the least squares possible value. For example,
* Welcome to Still More Details *
the first template will be:
1 1 1
1 1 2 is next, all the way to:
2 2 2.
These template numbers tell MagicTouch which square should be assigned
to it's first possible value, and which square should be assigned it's
second possible number.
Ironically, MagicDat uses an odometer logic, to create these templates.
MagicTouch now makes the assignments of possibles to each paired square,
according to the next template in the dat file. The resulting puzzle values
are all then given a preliminary test; by row, column, and box. Only
puzzles which have passed the previous test(s), are tested further.
At this point, many of the squares still have no known value! This is
designed to remove obvious conflicts * only *, in the assignments made.
Proposed solutions which pass all three of these preliminary tests, are
passed to the stage one, stage two, and stage three functions, to see if
they really will succeed in solving the entire puzzle.
In early testing, MagicTouch solves every puzzle in less than half a second,
on my P3 laptop, using just interpreted BASIC. No particular optimizations
have been made. Compiled versions of Magic Sudoku are up to 10 times faster,
solving puzzles in limited testing.
An empty Sudoku puzzle, is not a Sudoku puzzle. It is an empty puzzle,
waiting for it's initial values to be given. I had never heard of that
being presented as a puzzle to solve, and this program does not have code
that will support that concept.