Johannes Waldmann waldmann at imn.htwk-leipzig.de
Sun Aug 22 18:26:45 EDT 2010

```Ah, whenever I see "div/mod 3" in a Sudoku solver,
I feel that's not using the right model.
It's not a square, it's a hypercube, folks!

type Index = ( Int,Int,Int,Int )

neighbours :: Index -> [ Index ]
neighbours (a,b,c,d) = do
i <- [ 0 .. 2 ] ; j <- [ 0 .. 2 ]
[ (i,j,c,d), (a,b,i,j), (a,i,c,j) ]

Here is a solver that branches on the position
with the least number of possible values.
It is backtracking (in the List monad,
could probably be rewritten in Control.Monad.Logic)

type Matrix = Array Index (Either [Int] Int)

solutions :: Matrix -> [ Matrix ]
solutions m =
case sort \$ do
( i, Left xs ) <- assocs m
return ( length xs, i, xs )
of
[] -> return m
(_,i,xs) : _ -> do
x <- xs
solutions \$ set (i,x) m

set :: (Index, Int) -> Matrix -> Matrix
set (i, x) m = accum ( \ e _ -> case e of
Left ys -> Left \$ filter ( /= x ) ys
Right y -> Right y
)
( m // [ (i, Right x ) ] )
( zip ( neighbours i ) \$ repeat () )

```