[Haskell-cafe] Code Review: Sudoku solver

[Chris Kuklewicz]

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
>