[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


More information about the Haskell-Cafe mailing list