Daniel Fischer wrote: > My IDE is kate/kwrite + ghci + hugs, if you know a better one (which doesn't > involve loading down a 99MB thing like eclipse), I'd be interested to try it > out.
(I already knew emacs, so using haskell-mode is my choice) >> I changed the output format to a line per puzzle (solution/number >> and list of guesses - I still like that metric as each guess means that >> we've run out of ideas, which suggests that we want to get the number >> of guesses down to zero), using the same format for both solvers to > > and if we get down to zero, all's fine, but I think we shouldn't ignore the > false guesses. As a metric, you need to include all the blind alleys. >> as for guessing strategies, you're sorting the non-fixed positions by size >> of range before extracting candidates for guesses, whereas I simply take >> them in the order they appear in the puzzle (which may have been >> somewhat hard to see thanks to another one of those overcomplicated >> pieces of code that has now disappeared..). I had thought about that, but > > I have also tried guessing on the first blank, increased time about 12%, so > until I find a better criterion, I'll stay with fewest possibilities. > The (simple) idea behind that choice is, if I have only two possibilities, I > have a 50% chance of being right on the first attempt - that reasoning of > course was based on the 'find one solution and stop' target, for determining > all solutions, i.e. following all branches, I'm not so sure I could justify > it. > However, I've also tried the opposite (just to compare), guess at a position > with maximum number of choices: MUCH slower. The *only* "optimization" in Knuth's dancing-links binary-code-problem-solver is that it always chooses the constraint with the minimum number of possibilities. (Sometimes there is only one possibility). >> if I eliminate the sorting from your solver, both solvers deliver the same >> results, so that's nice!-) but it also means that we have room for further >> improvement. >> >> one reason why I got interested in this problem in the first place was >> that I had been reading about constraint propagation, and wanted to >> get some hands-on experience. in particular, there is a technique >> called "generalized propagation": >> >> Generalised Constraint Propagation Over the CLP Scheme, >> by Thierry Le Provost and Mark Wallace. Journal of Logic >> Programming 16, July 1993. Also [ECRC-92-1] >> http://eclipse.crosscoreop.com:8080/eclipse/reports/ecrc_genprop.ps.gz >> >> if I may oversimplify things a bit: >> >> 1 split inferences into branching (search) and non-branching (propagation) >> 2 distribute common information from non-branching inferences >> out of branches >> 3 to enhance applicability of step 2, add approximation of information >> >> applied to our sudoku problem, we have deterministic propagation >> and branching search, and what we do if we run out of propagation >> opportunities is to select a non-fixed position, then branch on each >> of the numbers in its range. adding generalised propagation (as I >> understand it) amounts to a form of lookahead: we take each of >> those branches, but look only at the deterministic information we >> can extract in each (ignoring further search). then we check whether >> the branches have any of that information in common, and apply any >> such common information to our matrix. rinse and repeat. an obvious >> way to refine this process by approximation is to build the union of >> the ranges on each position for the matrices resulting from all the >> branches. >> >> using this idea with a single level of branch lookahead, and selecting >> a position with the widest range for inspection, reduces the number >> of puzzles requiring guesses to 373, with a maximum depth of 3 >> guesses. 373 out of the list of 36628 ? Impressive. > But this method, if I'm not grossly mistaken, does involve guessing - > refined, > educated guessing, but guessing still. On the other hand, one might correctly > state that even the wildest guess and check is logic (proof by contradiction; > if I put values v_1 to v_n at positions p_1 to p_n respectively and then > value v_(n+1) at position p_(n+1), I finally can't satisfy the constraints, > hence, given v_1 ... v_n at p_1 ... p_n, at p_(n+1), v_(n+1) cannot be ...) There is no clear definition that separates logic and guessing, because the algorithm does not understand your semantics. I would say the semantics of "lookahead 1 step" are different from guessing because the amount of computation involved is predictable ahead of time: you can look at the current possibilities and know how much work goes into "lookahead 1 step" but you can't look at the current state and know how much work a brute force search will take. > >> it doesn't reduce runtime much, yet (7min50s), but I haven't >> even started profiling, either. I guess I have to look into >> representations now, if I ever want my solver to catch up with >> your's in terms of runtime;-) >> >> cheers, >> claus > > Cheers, > Daniel > _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe