[Haskell-cafe] Norvig's Sudoku Solver in Haskell

[Daniel Fischer]

Am Montag, 27. August 2007 14:40 schrieb Jon Harrop:

> > Probably not, but what's wrong with using arrays (here and in general)?
> > Here I find arrays very natural, after all a grid has a fixed set of
> > indices. And as they have a much faster lookup than maps (not to mention
> > lists), what do you gain by avoiding them?
>
> Elegance, brevity and (for short implementations) performance. Although
> this algorithm certainly involves getting and setting puzzle entries from a
> square array, there is little benefit in constraining your solver to
> reflect that explicitly in its concrete data structures.

I'm not convinced (yet).
Elegance: well, yes in general; if you don't know the size of the problem in 
advance certainly. But here?

Brevity: okay, "Map.fromList" is shorter than "array ((0,0),(8,8))", but not 
awfully much so, and you write "grid!s" regardless of whether grid is a Map 
or an array. So without further elaboration I remain unconvinced of that 
point.

Performance: in my experience arrays are usually much faster (if the algorithm 
is suited to using them, if not, it's a different story, of course).
>
> Compilers like GHC will be extremely good at performing low-level
> optimizations on list-intensive algorithms. So the performance overhead of
> using lists rather than arrays in a functional language will be small.

That VERY MUCH depends.
I usually use lists for the Project Euler problems first (1. I love lists, 2. 
list code is often far more natural - and hence more elegant) and sometimes 
afterwards re-code it using arrays (boxed arrays or ST(U)Arrays).
More often than not that reduces run time by orders of magnitude(factors 
between 10 and 100 are common, larger or smaller factors occur).
I doubt it's just that my array code is better suited for GHC's optimiser than 
my list code.
Maps I found to perform in between and they are rather memory-hungry.

>
> Externally, using lists makes it easier to pluck out one choice and the
> remaining choices when searching. That is, after all, the core of this
> algorithm.

Just to make it clear, you are here talking about the list of possibilities 
for some square? Or are you talking about using a list of 
(square, list of possibilites) pairs?

If the former: I represent the grid as an Array (Char,Char) [Char], replacing 
the original representation as a Map String [Char], so I keep that.
Although, in my own solver I keep the set of possibilities for each square as 
an EnumSet (now Data.Set.Enum in the collections package, maybe I should 
update my code), that gains a factor of 2 over lists for the good old 9x9 
grids, more than 10 for 16x16 grids, I fear trying 25x25 grids.
However, I use deduction strategies that involve forming unions and 
differences of several sets of possibilities, operations which are weak spots 
of lists.

>
> > > The following purely functional OCaml solver is faster than Norvig's,
> > > for example, and uses lists, tuples and maps:
> >
> > <snip>
> > Since I don't speak OCaml, could you translate it to haskell?
>
> I don't speak Haskell yet but I can translate it into English:
>
> A puzzle is represented by an association list that maps each coordinate
> onto its possible solutions. Initially, coordinates set in the puzzle map
> onto singleton lists (e.g. ((3, 4), [7]) means position 3,4 in the solution
> must contain 7) and unset coordinates map onto [1..9].
>
> To search for a solution, you accumulate the solution in another
> association list (e.g. ((3, 4), 7) means that 3,4 contains 7 in the
> solution). You take the coordinate with the shortest list of possibilities
> first and the list of remaining coordinates. You try each of the
> possibilities listed in turn, pushing that choice onto the current solution
> and filtering out all invalidated solutions from the remaining list before
> recursing.
>
> That's it. Choosing the shortest list first corresponds to constraint
> propagation.

Thought it was something like that.
Must check whether that beats Norvig's constraint propagation.

Cheers,
Daniel