Samuel Tardieu @ rfc1149.net

,

Today, a friend of mine told me that he was writing a Sudoku solver in Haskell. I could not resist and also wrote a brute-force one. The code is ugly (I was trying to generate as short a program as possible), but it led me to interesting thoughts.

First, here is the code. Beware, you are supposed to know Haskell and monads to understand the comments following the code:

``````import Control.Monad (msum, mzero, MonadPlus)
import List (elemIndex, (\\), intersperse)
import Maybe (fromJust)

get s (l, ln, c, cn) = [s!!(ll*9+cc) | ll <- [l..l+ln], cc <- [c..c+cn]]
getall n s = [(f 0 9 1, 0, 0, 8), (0, 8, f 9 1 1, 0),
(f 0 27 3, 2, f 9 3 3, 2)] >>= get s
where f m d t = ((if m == 0 then n else n `mod` m) `div` d) * t

solve :: (Eq a, MonadPlus m) => [a] -> a -> [a] -> m [a]
solve g n s = case elemIndex n s of
Nothing  -> return s
Just idx -> msum \$ (g \\ getall idx s) >>= \x ->
return \$ solve g n \$ take idx s ++ [x] ++ drop (idx+1) s

showSudoku s = unlines \$ "Solution:" : (flip map [0..8] \$ \n -> sline n s)
where sline n s = concat \$ intersperse " " \$
map show \$ get s (n, 0, 0, 8)

main = do
s <- getContents
let display = do
choice <- solve [1..9] 0 \$ map read \$ words s
return \$ showSudoku choice
putStr \$ fromJust display``````

The interesting piece here is not the code itself, which is indeed pretty boring and unclear, it is the type declaration of the `solve` function: its return type is `m [a]`, where `[a]` represents a completed Sudoku grid and `m` is a `MonadPlus` instance. What is the point of choosing a `MonadPlus` type when, in the `main` function, the result is coerced to a `Maybe` (which is a `MonadPlus` instance) before being printed by the usage of `fromJust`?

The `Maybe` type can contain zero or one result. It means that the code, when executed, will either find no solution or return exactly one solution which will then be printed. But what can we change if we want to print all the solutions? (if we start from the empty grid for example)

We are using Haskell after all. Instead of using a `Maybe` type, we might as well use a list. All right, the list type is also an instance of the `MonadPlus` class. It can contain nothing (empty list), one result, or more. Let’s change the line containing `fromJust` in `main` by:

``mapM_ putStr display``

The use of `mapM_` coerces the use of `solve` to a list type. Now, all the solutions will be printed, not only one of them.

If you want to try it, create a file called `empty` containing 9 lines of 9 space-separated zeroes:

``````0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0``````

and compile the program (either variant). Then you can feed it the `empty` sudoku grid:

``````% ghc -o sudoku sudoku.hs
./sudoku < empty``````