[Haskell-cafe] Norvig's Sudoku Solver in Haskell
malte at gmx-topmail.de
Sun Aug 26 13:30:43 EDT 2007
manu <emmanuel.delaborde at citycampus.com>:
> After reading Peter Norvig's take on writing a Sudoku solver (http://
> 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
Where the array's bound are (0,0), (8,8) or (1,1), (9,9), according to
> 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.
More information about the Haskell-Cafe