Am Mittwoch, 5. April 2006 15:09 schrieb Chris Kuklewicz:
Henning Thielemann wrote:
On Mon, 3 Apr 2006, Jared Updike wrote:
or ambiguously) with your Sudoku solver? A rough mesaure of the difficulty of the unsolved puzzle could be how long the solver took to solve it (number of steps) (and the number of possible solutions)? Are puzzles with multiple solutions usually considered harder or easier? Are these considered proper puzzles?
It's an interesting test to run a Sudoku solver on an empty array. :-)
I am cleaning up my old (aka inexperienced) solver based on Knuth's dancing links to put on the wiki. The code is very different than most Haskell solutions, since it revolves around a mutable data structure (which is not an MArray).
It "solves" an empty array in 81 steps with no backtracking. It will produce a list of all the solutions of an empty board quite efficiently.
Cleaning up my "logic" based solver will take longer.
I've cleaned up my solver, removed a lot of redundant inference steps and made the board a DiffArray (is that really faster?). Now it completely solves (following all guesses) the 36,628 17-hint puzzles in about 32 minutes (1909 secs). It "solves" an empty board in 81 steps without false guesses, but still takes over four seconds (that's the price for excessive inference). I've also written a version using David F. Place's EnumSet instead of [Int], that takes less MUT time, but more GC time, so is slower on the 36,628 test, but faster for a single puzzle. If anybody feels like improving the code (especially finding better names for the functions) and/or placing it on the wiki, I'll be honoured. Just out of curiosity, speed was not the objective when I wrote my solver, I wanted to avoid guesswork (as much as possible), but in comparison with Cale Gibbard's and Alson Kemp's solvers (which are much more beautifully coded), it turned out that mine is blazingly fast, so are there faster solvers around (in Haskell, in other languages)? Cheers, Daniel -- "In My Egotistical Opinion, most people's C programs should be indented six feet downward and covered with dirt." -- Blair P. Houghton