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