[Haskell-cafe] Norvig's Sudoku Solver in Haskell
Daniel Fischer
daniel.is.fischer at web.de
Mon Aug 27 10:27:54 EDT 2007
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
More information about the Haskell-Cafe
mailing list