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

Donald Bruce Stewart dons at cse.unsw.edu.au
Tue Aug 28 21:49:43 EDT 2007

```chaddai.fouche:
> For the translation of the above OCaml code, there is not much to do,
> in fact it is mostly functional, and so easily translated in Haskell
> code, note that I add a code to handle input of the form
> "4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......",
> to resolve it and print a solution :

Spencer Janssen also wrote a rather elegant translation, which you can
find on hpaste.org

import Data.List
import Data.Ord

n = 3 :: Int

invalid (i, j) (i', j') = i == i' || j == j' ||
i `div` n == i' `div` n && j `div` n == j' `div` n

select p n p' ns | invalid p p' = filter (/= n) ns
| otherwise    = ns

add p n sols = sortBy (comparing (length . snd)) \$ map f sols
where f (p', ns) = (p', select p n p' ns)

search []             = [[]]
search ((p, ns):sols) = [(p, n):ss | n <- ns, ss <- search \$ add p n sols]

You can see the development here,

http://hpaste.org/2348

-- Don
```