[Haskell-cafe] Norvig's Sudoku Solver in Haskell
derek.a.elkins at gmail.com
Sun Aug 26 13:26:39 EDT 2007
On Sun, 2007-08-26 at 14:50 +0200, manu wrote:
> After reading Peter Norvig's take on writing a Sudoku solver (http://
> I decided that I would port his program to Haskell, without changing
> the algorithm, that'll make a nice exercise I thought
> and should be fairly easy... Boy, was I wrong !
> Anyway, I eventually managed to tiptoe around for loops, mutable
> state, etc...
> However, when I run my program against the test data provided (http://
> I find it takes around 1m20 s to complete (compiled with -fvia-C and -
> O2, on a MacBook Pro 2.33GHz Intel Core 2 Duo).
> That's roughly 8 times longer than Norvig's Python script. That's not
> what I expected !
> My program is also longer than the Python version.
> Being a beginner, I am convinced my implementation is super naive and
> non idiomatic. A seasonned Haskeller would do much shorter and much
> faster. I don't know how to improve it though !
> Should I introduce more strictness ? replace lists with more
> efficient data structures (ByteStrings, Arrays) ?
Yes. Treating lists like arrays is always a recipe for heartbreak. If
you did want to try to match the python code exactly there are mutable
arrays and such.
http://www.haskell.org/haskellwiki/Sudoku has a bunch of different
implementations going for different things.
More information about the Haskell-Cafe