## Lights off

Looking for another puzzle i found the lights off problem at codechef. Wolfram math world suggests a novel approach for solving it. At the core is a linear equations solver. The LinearEqSolver at hackage provides this functionallity for haskell.

The package LinearEqSolver is actually a wrapper that uses external libraries;

`Z3`

,`CVC4`

, and`MathSAT`

. I used CVC4 which I downloaded here and installed.

Equipped with a fine solver like this, all we need to do is to construct the matrix in the equation . Each row in M is a binary matrix Aij which represents the positions of the board that are flipped if the position i,j is pressed. This is the code that constructs Aij:

indices n = [(i,j) | i <- [0..n-1], j <- [0..n-1]] makeA n i j = map f (indices n) where f (i',j') = case (abs(i'-i),abs(j'-j)) of (0,0) -> 1 (1,0) -> 1 (0,1) -> 1 _ -> 0

Using this code we can then construct M:

makeM n = map (-2:) (makeM' n) where makeM' n = map (uncurry (makeA n)) (indices n)

Note that this code adds an extra column filled with -2. The reason for this is that we are solving a system of linear equations modulo 2. The transformation from modulo to an ordinary lineary equation problem is given here.

Now we can wrap everything up into a solver function.

solve n b = do s <- solve' n b case s of Just x -> return $ map (\x -> mod x 2) $ tail $ x _ -> return [] where solve' n b = solveIntegerLinearEqs CVC4 (makeM n) b

Testing the problem give at wolfram math world

test = solve 3 board where board = [0,1,0,1,1,0,0,1,1]

yields [1,1,1,0,0,0,0,0,1] which is also the solution presented at wolfram.