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

[Derek Elkins]

On Sun, 2007-08-26 at 14:50 +0200, manu wrote:
> Hello,
> 
> After reading Peter Norvig's take on writing a Sudoku solver (http:// 
> norvig.com/sudoku.html)
> 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:// 
> norvig.com/top95.txt),
> 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.