C[omp]ute

From: andrew cooke <andrew@...>

Date: Fri, 30 Mar 2012 23:27:34 -0300

I just finished (before midnight!) a solution to
http://stackoverflow.com/questions/9689436 using Choco
http://www.emn.fr/z-info/choco-solver/

And it's pretty neat.

Previously, I had written a simple depth-first search and a "smart" search
with constraint propagation (along the same lines as
http://norvig.com/sudoku.html).  My DFS was fast when there were few
constraints while my "smart" routine was fast when there were lots of
constraints.  But both were disappointing when not well-matched to the
problem.

In contrast, Choco combines the best of both worlds (although the initial
startup cost is higher).  It's as fast as a simple DFS when it needs to be,
but can also exploit constraints to find quick results when possible.

Which I guess is what you'd expect.

The downside is that it's a big system, and the API docs aren't so great.
There's a manual, which is a good introduction, but when you start to explore
it can become a little opaque.  For example: it turns out that (as far as I
can tell) if you specify a set of values for a variable, they need to be
ordered.  That's not in the API docs, but without it, the system crashes.

Even so, the speed is impressive.

Andrew

PS Choco is Java, but I called it from Clojure.  I really like Clojure - it
seems to hit the sweet spot of functional, untyped and, surprisingly
important, good control over evaluation strategies (lazy and eager).  It's
like a Haskell for dumb people :o)