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

[Jon Harrop]

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