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

[manu]

Daniel Fischer's modifications to my original program lead to a 400 %  
speed boost !!!
(It now runs in 22 seconds on my machine)
He avoided unecessary calls to 'length', uses Array instead of Map,  
refactored 'search' function (details below)

I've put up his version on hpaste : http://hpaste.org/2452#a1

Manu



On Aug 26, 2007, at 10:56 PM, Daniel Fischer wrote:

> Without much thinking I can spped it up by a factor of 4 (from 280s  
> to 60s).
> The most important things are:
> - don't use length unless you need it
> instead of
> newV2 <- case length newCell of
> 		0 -> Nothing
> ...
> and
> case length dPlaces of
> 	0 -> ...
> use
> case newCell of
> 	[] -> Nothing
> 	[d'] -> ...
> and
> case dPlaces of
> 	[] -> Nothing
> 	[s'] -> ...
>
> - let dPlaces = [ s' | u <- lookup s units, s' <- u, elem d (lookup  
> s' newV2)]
> is bad
> let dPlaces = [s' | s' <- lookup s peers, elem d (lookup s' newV2)]
> scans each peer only once
>
> - search is really bad, you lookup all squares several times,  
> potentially
> compute all lengths multiple times...
> much better is
>
> search :: Grid -> Maybe Grid
> search g = case [(l,a) | a@(_,xs) <- M.assocs g, let l = length xs,  
> l /= 1] of
>             [] -> return g
>             ls -> do let (_,(s,ds)) = minimum ls
>                      msum [assign g (s,d) >>= search | d <- ds]
>
> (I also changed the type, and instead of foldl' you should use  
> foldr, since
> "some" is lazy in the second argument, further, since Maybe is a  
> MonadPlus,
> it's "mplus" and 'foldr mplus Nothing' is msum)
>
> - Maps aren't good here, too slow lookup and you know the keys, so  
> use arrays
>