[Haskell-cafe] Norvig's Sudoku Solver in Haskell
Jon Harrop
jon at ffconsultancy.com
Mon Aug 27 08:40:17 EDT 2007
On Monday 27 August 2007 11:54:20 you wrote:
> Am Montag, 27. August 2007 11:24 schrieb Jon Harrop:
> > You shouldn't have any problem writing a purely functional solver that is
> > faster and much shorter than Norvig's Python without having to use
> > arrays.
>
> 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.
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.
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.
> > 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.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
OCaml for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists/?e
More information about the Haskell-Cafe
mailing list