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

[Yitzchak Gale]

Hi Manu,

You wrote:
> 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 !

Welcome to the Haskell Sudoku club!

http://haskell.org/haskellwiki/Sudoku

Please add your solver there.

I enjoyed reading your solver, and comparing
it to the Python version. It was a nice idea
to port the imperitive parts of this algorithm using
the Maybe monad.

The algorithm of your solver is essentially identical
to the solver I posted on the wiki page; even the data
structures are more or less the same. But mine is
written in a more native Haskell style (happens to
be based on a State monad).

> When I run my program against the test data
> provided (http://norvig.com/top95.txt),
> I find it takes around 1m20 s to complete

I just ran mine against that file,
also on a MacBook like yours, but only
2Ghz. It took about 28s, only about double
Norvig's claim. There are other solvers on
the wiki page that claim to be considerably faster.

> (compiled with -fvia-C

The GHC gurus can correct me, but I understand
that there isn't likely to be any advantage to -fvia-C
nowadays.

> My program is also longer than the Python version.

Yes, but for porting foreign code I think you did great.

The use of strings, copied from the Python, looks
a bit arcane in Haskell, but it shouldn't hurt anything.
Perhaps you would gain something if you used Data.Map.!
instead of your "lookup". Other than that, I'm not
sure why your code runs slower than mine.

Regards,
Yitz