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

[Malte Milatz]

manu <emmanuel.delaborde at citycampus.com>:
> 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

Your program was wrapped by your mail client, so you may want to hpaste
your program for easier digestion.

> 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 !

Disclaimer: I'm not an experienced Haskeller either, and I haven't had
a real look at your code at all. The following is only what stroke me
by a quick look. Gurus may eventually reduce your code into a
thirty-line version that also runs quickly.

> -- Types
> type Digit  = Char
> type Square = String
> type Unit   = [Square]
> 
> -- We represent our grid as a Map
> type Grid = M.Map Square [Digit]

Your profiling output suggests that much time is consumed by the lookup
function. Since you're using (fromJust . lookup) everywhere anyway, a
data structure not envolving the Maybe type is probably a more succint
choice. And why bother with characters and strings? So I propose

type Square = (Int,Int)
type Grid   = Array Square Int -- or [Int], if the algorithm requires
that

Where the array's bound are (0,0), (8,8) or (1,1), (9,9), according to
your taste.

>  newV2 <- case length newCell of
>              0 -> Nothing
>              1 -> do let peersOfS =  [ s' | s' <- lookup s peers ]
>                      res <- foldM  eliminate newV (zip peersOfS (cycle newCell))
>                      return res 
>               _ -> return newV

The use of “length” here is not an actual performance problem, but
unnecessary. Simply write: case newCell of []  -> ...
                              [_] -> ...
                              _   -> ...

The same is valid for your other use of length.

Malte