[Haskell-cafe] Code Review: Sudoku solver

[Claus Reinke]

>> Mine's even faster now (at least on my computer, would you care to test it
>> on your's? If you don't want to get EnumSet, just change DiffArray to
>> Array, worked wonders for me), I'll dig into yours tomorrow to see what I
>> can get out of it to improve my algorithm.
> 
> Unforunately, no new inference rules :-(

indeed, the crucial difference between our versions was that I'd avoided
group inference; I thought it would be expensive to implement and, based 
on my own limited experience, rarely used - boy, was I wrong on both 
accounts: it is easily implemented, with a little care for the inner loop, not 
too inefficient, either, and the examples I mentioned (on which my solver 
needed guesswork) simply fall apart once grouping is added (it was quite 
impressive to take the output of my old propagation code and apply 
grouping by hand!).

now my solver takes slightly fewer guesses than your's, though your's
is still significantly faster (same factor of about 3 between them, both 
having improved by a factor of 2 or so..).

> Two things I don't like about your code:
> 1. no type declarations

that's what type inference is for!-) I tend to add them only as debugging
assertions, when language limitations require them, or when I'm fairly
certain that the code is stable (ie., dead;-). it is useful to think about types,
but engraving them into the code is overrated (any good ide should be
able to show them as if they'd been written in anyway..; lacking such ide,
:browse Main will do the trick, though ghci's current formatting is ugly!).

> 2. too much name shadowing, that makes following the code difficult

depends on which parts you mean - I don't like overusing primed or
numbered variables, and using the same variable name through a
sequence of steps is usually the last step before factoring that variable
out into some monad anyway (I did mention that the code was still
ad-hoc, not cleaned up).

> apart from that: clever

as in: you'd prefer it if I'd express myself more clearly?-) agreed.
I've been working on cleaning up the code (also trying to remove
stupidities as they become exposed in the process..).

>> lists and adhoc code tend to be performance killers, I doubled the speed of
>> mine by de-adhoccing the code (and that although I introduced the
>> speed-killer DiffArray)

there's nothing wrong with lists, just as arrays are not synonymous with
good performance - it all depends on the usage patterns. there are several
interesting examples in this problem:

1 when I first tried EnumSet for the ranges, there was no substantial 
    performance difference to a list-based representation.

    in theory, the change sounds like a clear win (constant vs linear time 
    membership test), but (a) the ranges are small (they start at size 9, 
    and we do our best to shrink them rapidly, so even if they were at
    average size 6 or 7, the test would take an average of 3 or 4 steps);
    (b) membership is not the only operation - for the inner loops in my 
    code, singleton testing and extraction of the single element from a
    singleton were equally important, and here the relation was reversed: 
    lists give us those operations in constant time while they were linear 
    in the old EnumSet.

    Bulat's tabling suggestion (which I interpreted rather more extremely
    by tabling the actual calls to size and range2list:-) solves this issue 
    beautifully, making EnumSet starting to look competitive in spite of
    the particular usage pattern in this problem, and when the grouping 
    inference asked for more calls to size, as well as intersection and 
    union, the choice flipped completely, now in favour of EnumSet
    (has agreement been reached about an updated version of EnumSet?).
 
    [if I might make a suggestion for EnumSet: it is not just that the
     implementation of the standard API can be more efficient for these
     small sets, but there are additional operations that ought to be
     included (unless the EnumSet.Set constructor gets exported),
     such as lifting the Ix instance from Word to Set a]

2 DiffArrays: they are neither a speed killer nor a universal cure.

    they were intended to enable functional arrays with inplace
    update for sequential access, but without the complex analyses
    needed to ensure such sequential access, and with the reverse
    diff to old versions preserving the persistence of copies.

    using them, we'll get inplace update plus a long trail recording 
    the diffs needed to reconstruct the old versions, and if we use 
    them single-threadedly, that trail will just be ignored and the
    garbage collector will neglect to copy it at some point. but if
    we combine them with backtracking, those trails are likely to
    kill much of the performance gains, and it is not so much the 
    width of branching as the depth of each branch: we iterate on 
    that array to narrow ranges and to update positions, and each 
    tiny update extends that trail of reverse diffs (they are not even
    collapsed, so they can be longer than the array range) - so 
    when we finally abandon a branch and need to return to any 
    of the older versions of that array, we are going through that 
    trail, linearly, to reconstruct that old version from the new one 
    (doing an identity update before entering a branch should give 
    us two independent copies, though we'd need to make that 
    update not on the current version of the array..).

3 Arrays: again, they are no universal performance cure, and 
    their advantages depend on the usage patterns.

    tabling calls to size is an ideal example in favour: a single array
    construction vs frequent reads. in contrast, a sequence of 
    frequent small updates, as in constraint propagation, seems to 
    be rather disadvantageous: every time we narrow a range or
    fix a position, the whole array gets copied! on the other hand,
    those arrays are small, and the cost of copying may be lost in
    other costs. but if we have to go through many elements, 
    the cost can be reduced by doing updates in bulk: a _list_ of
    updates, with only one new copy being created, incrementally.

    there is, however, one part of the problem where I'd expect
    arrays to be advantageous, and that is in generating those lists
    of updates: here we only inspect the sudoku matrix, reading
    its elements according to various more or less complex views.
    this part should be efficiently handled over an array, and as
    your code shows, doing so may even result in fairly readable
    code (although the clarity of my own code has improved as
    well since the time when it used to be very concerned with 
    constructing those several views in rather complex ways;-).

> I believe if you change the representation of puzzles from [(pos,range)]
> to an Array, you'll get a significant speedup

since my solver's logic now seems to be on par, I might try that
for the generation of constraints, but I still doubt it is ideal for the
actual updating of the matrix - perhaps bulk updates might be
sufficient to remedy that.

but the important lesson is that one can leave non-algorithmic
performance concerns to the very end (where they need to be
guided by profiling, and limited to the actual "inner loops") - I
got my solver fairly fast without ever worrying about specialised
representations, or strictness, etc.; focussing on algorithmic
aspects was sufficient and necessary, however: 

the naive generate-and-test is impractical, and while simple
constraint propagation will lead to drastic speedups, those are
not sufficient (they still left me in the 10000puzzles/hour stage), 
so more careful propagation is needed.

my first narrowing propagation sped up the difficult puzzles, but 
slowed down the simple ones (and there are a lot of those in this 
set); I had already started on complex heuristics to apply that
propagation selectively before I recalled my own good principles
and looked at the algorithm again, as that slowdown should not
have happened in the first place. 

and in fact, it turned out to be related to one of those optimizations 
we are all too likely to throw in automatically, without much thought: 
to avoid stumbling over the fixed positions as singletons ranges 
again and again, I had disabled that propagation, and had instead 
left it to each of the other propagation steps to note the appearance 
of new singletons, while ignoring the old ones.

so, when my new narrowing step narrowed the range on some
position to a singleton, without notifying anyone, that singleton
got duly ignored by everyone else, assuming that it had already
been taken care of. result: longer searches, in spite of more
information!-( rectifying that, and simplifying some structures,
got the time for the whole set down to the 17min I reported.

on the other hand, one cannot always ignore performance completely, 
relying only on the algorithm: but usage patterns and profiling of actual 
code are the key here. when I finally added my group inference, it did 
slice down the number of guesses for the previously difficult puzzles, 
but the actual runtime for the whole set of puzzles increased by a few 
minutes! profiling showed some rather extravagantly complex code 
("clever" in the worst sense!-) in the innermost loop, cured by 
simplifying (and clarifying) the code in question. the next step was
moving to EnumSet, followed by the size/foldBits issue, cured by 
Bulat's tabling suggestion. now we're down to 8min20s or so, still 
with lists for backtracking and for the main matrix. (compared to 
2min40s or so for your's)

> Rot! Typo in _my_ previous message, 5319 is correct.

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 
allow for easy grep/diff.
 
>> > puzzles involving guesses: 8165
>> > largest number of guesses:
>> >     10 (#9175), 10 (#17200), 10 (#29823), 10 (#30811)

down to 5319 and 0/0/3/0 now.

> We use different guessing strategies (plus, I also have group-inference).

yep, that convinced me that group inference is a must (now added).

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
couldn't make up my mind about preferring any order, and while the
numbers of guesses for our two solvers vary wildly between puzzles,
the total of guesses shows no advantage of sorting (the total looks 
slightly smaller for my solver, it has no two-digit guesses, and fewer
puzzles with more than 6 guesses, so if anything, the evidence is against
sorting, but I'd rather focus on reducing the guesses than try to attach
any significance to these variations..).

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.

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