I didn't
do a full complexity analysis on mine, because it uses
heuristics that mean any human-solvable puzzle is solved in so close
to zero time that it's not worth improving it.
But, if somebody else's
Sudoku CREATION system can produce x
thousands of puzzles per hour, you wouldn't want to start falling
behind, would you?
If and when that becomes a concern, I may do a complexity analysis and
possibly rewrite the solver. :-)
If I had one system for generating puzzles, and
another for solving
them, then I wouldn't need to spend any more of MY time on them!
Heh.
There are several obvious algorithms for solving the
puzzles. But, I
can't quite figure out how to generate them.
My generator works by starting with a completely blank grid. Then it
runs the solver, slightly tweaked so that it bails as soon as it finds
a second solution (rather than continuing to search for more). This
can produce any of three results: `no solutions', `exactly one
solution', or `multiple solutions'. If it returns `multiple
solutions', then it drops in one, two, or four randomly-chosen numbers
(how many depends on the symmetry setting, which can be set to produce
no, 180-degree, or 90-degree symmetry, and, for odd sizes, on whether
it picks the centre cell). If the solver then returns `no solutions',
it removes them and tries again; if `multiple solutions', it leaves
them there and loops, putting down more numbers. This is kept up until
the solver returns `exactly one solution'.
That's the basic generator. There are two flags: prune/noprune and
fork/nofork. If the forking flag is set to nofork, then if the solver
finds it has to do tree search, then `exactly one solution' gets is
counted as if it were `multiple solutions'; if it's set to fork, then
the code doesn't care whether the solver had to do tree search. If the
prune flag is set to noprune, then the result is printed as soon as the
above loop gets `exactly one solution'. If the prune flag is set to
prune, then a postprocessing pass is performed: each number, pair of
numbers, or quartet of numbers is tentatively removed and the solver
run. This can return `multiple solutions' or `exactly one solution'
(if it returns `no solution', the generator bugchecks, since, in the
abstract, that can't happen). If it returns `multiple solutions', the
tentatively removed number(s) go(es) back; if `exactly one solution',
the removed number(s) stay(s) removed. This is repeated until every
number, pair, or quartet has been tried, meaning that every number pair
(or quarter or singleton) is necessary in the sense that removing it
leads to a puzzle with multiple solutions. During this postprocessing
pass, if the forking flag is set to nofork, then, again, one solution
that required tree search is counted as if it were multiple solutions.
This is computationally expensive. It turns out to be usably fast in
practice; my program can crank out order-3 sudoku at some 20 to 25 per
second on an 860MHz P-III, which is pretty modest hardware by today's
standards. It gets much more expensive very fast as the size rises,
though; generating a single order-4 on the same hardware rarely takes
less than 5 seconds and can take multiple minutes if your luck is bad.
(If it gets into a state where there are multiple solutions but it has
to put down just the right number in just the right place to reduce it
to only one solution, then it can sit there generating random numbers
for a long time until it happens on the right ones. If I cared enough
I might try to add code to improve performance in such cases - feeding
back partial solution information from the solver to the number
placement code would be one way to do this.)
/~\ The ASCII Mouse
\ / Ribbon Campaign
X Against HTML mouse at
rodents-montreal.org
/ \ Email! 7D C8 61 52 5D E7 2D 39 4E F1 31 3E E8 B3 27 4B