Sudoku solver: reduction + brute force
xivulon at gmail.com
Thu Jan 19 13:31:29 CET 2006
>Your reduction-first approach makes short work of
> them, though. On the other hand, my version probably didn't take as long
> to write!
Well, I started from the reduction-only algorithm so by the time I
implemented the brute force solver I already had the code. Anyway the
full code is just above 100 lines, it could be shorter (and it was in
its first incarnation) but I strived to make it clean and more object
oriented following the LinuxJournal article and by avoiding index
operations (only contained in the __init__ methods).
I like the idea of estimating difficulty... But for a subjective mesure
from the point of view of the solver you probably need to give weights
to the reduction techniques required to eliminatre cells, since those
are the ones used by human beings. Some puzzles might be easy to solve
by reduction but difficult to solve by brute force only. In this
context for instance, a weight of 1 could be used every time one or
more cells are eliminated thanks to Cell.Solve (the easiest approach),
a weight of 2 when Cell.Skim was used to eliminate cells (more
complex), and a weight of 3 every time BruteForce needs to be invoked
(i.e. solutions must be guessed).
One thing that my solver lacks is the ability to recognize multiple
solutions. It will simply stop at the first admissible one whether it
is unique or not. I am not sure what is an efficient way to detect it.
More information about the Python-list