Am Montag, 3. April 2006 18:52 schrieb Chris Kuklewicz: > Claus Reinke wrote: > >>> > It solves sudoku puzzles. (What pleasure do people get by doing > > >>> > >>> these in their heads?!?) > > > > probably the same you get from writing programs?-) figuring out the > > rules, not getting lost in complexity, making something difficult work..
Exactly, and I wrote a solver with a relatively elaborate strategy last year (it was written incrementally, so the code is horrible, I always wanted to rewrite it properly but never got to do it, hence I will not post it unless asked to), to have both kinds of pleasure, figure out a strategy and teach it to my computer. > > From a human standpoint, there are some puzzles that are much harder than > others. This also applies to the few programs that I have seen. It is > this variety of complexity that makes it interesting. > > >>> They are probably asking the same question: why take hours to write a > >>> program to do it when with my mad sudoku solving skills I can solve it > >>> in X seconds? My roommate is like this. > > > > if we just throw raw computing power at the problem (in-place array > > updates, bitvectors, multiprocessors, ..), wouldn't they be justified? > > but as soon as we try to take their skills and encode them in our > > programs, things become more interesting (do computers really "play" > > chess?-). > > You can go get the 36,628 distict minimal puzzles from > http://www.csse.uwa.edu.au/~gordon/sudokumin.php that have only 17 clues. > Then you can run all of them through your program to locate the most evil > ones, and use them on your associates. :) Well, I loaded them down and let my solver determine whether all of them have a unique solution (they do), took 76 min 14.260 sec user time, hence roughly 0.125 secs per puzzle, so I dare say there are no evil ones among them (However, Alson Kemp's solver from the HaWiki-page -- which, I don't know why, is much faster than Cale Gibbard's -- took over 20 minutes to solve the second 0 0 0 0 0 0 0 1 0 4 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 5 0 6 0 4 0 0 8 0 0 0 3 0 0 0 0 1 0 9 0 0 0 0 3 0 0 4 0 0 2 0 0 0 5 0 1 0 0 0 0 0 0 0 0 8 0 7 0 0 0, so these puzzles may be evil after all). My solver needed to guess on 5,309 of the 36,628 17-hint puzzles, which I find a bit disappointing -- the big disappointment was when neither I nor my solver were able to solve the example from the hawiki-page without guessing :-( -- does anybody know whether in a uniquly solvable sudoku-puzzle guessing is never necessary, i.e. by proper reasoning ('if I put 6 here, then there must be a 3 and thus the 4 must go there...' is what I call guessing) there is always at least one entry determined? > > This also gave me a way to statistically measure if a new deductive step > made much of a difference (or if it made no difference). Histograms and > gnuplot helped. > > > [snip Curry language example] > > > > my own Sudoku solver (yes, me too - see attached, but only after > > you've written your own!-) uses simple hand-coded constraint propagation > > to limit the space for exhaustive search - some puzzles are solved by > > constraint propagation only, and even where guesses are used, each guess > > is immediately followed by propagation, to weed out useless branches > > early, and to deduce consequences of each guess before asking for the > > next one. the good old game, start with generate&test, then move the > > tests forward, into the > > generator. > > > > I've only coded the two most useful groups of constraints (when > > there's only a single number left for a position, or when there is > > only a single position left for a number). there are other deductions > > one does in by-hand solving, and I'm not an experienced sudoku solver > > myself, so I don't even know more than a few such rules yet, but these > > particular two seem sufficient to get acceptable performance even under > > ghci/hugs, so why do more?-) (*) > > I have two versions of a solver. The first is a re-write of GDANCE bu > Knuth to solve Sudoku efficiently as a binary cover problem. (see > http://www-cs-faculty.stanford.edu/~knuth/programs.html ) This uses the > "Dancing Links algorithm" implemented with STRef's and is very fast. > > The second uses a different encoding to look for clever deductions. This > alone solves some easy problems and comes very close before getting stuck > on most. There are few though that start with 17 hints and only discover > one or two more by logic before getting stuck. These are the most evil of > all. > > You might be interested in the deductions described at > http://www.sudokusolver.co.uk/ > > > [by acceptable, I mean that my sequence of 5 test puzzles is solved in > > less than 20 seconds on a 2GHz Pentium M; no idea how that compares to > > the most efficient solvers] > > I could run ~20,000 puzzles in a couple of hours. (The collection was > smaller then). As stated above, I ran the 36,628 in 76 minutes on a 1200MHz Duron. But I must confess that my solver takes about 25 secs for the empty puzzle, guessing is baaaaaad. > > > perhaps Haskell should have Control.Constraint.* libraries for > > generalized constraint propagation (and presumably for constraint > > handling rules as well, as they are so popular nowadays for specifying > > Haskell's type classes)? > > Did you see the monad at http://haskell.org/hawiki/SudokuSolver ? Perhaps > you could generalize that. > > > cheers, > > claus > > > > (*) actually, that was a bit disappointing!-( I was hoping for some > > fun while trying to encode more and more > > "clever" rules, but not much of that seems to be required. > > You need more than 5 examples. The truly evil puzzles are rarer than that. > Go get the set of minimal puzzles and see how far your logic takes you. Cheers, Daniel -- "In My Egotistical Opinion, most people's C programs should be indented six feet downward and covered with dirt." -- Blair P. Houghton _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe