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

Monad matters. For real.