Home > Uncategorized > Lights off

## 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 $M x = b$. 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.

Categories: Uncategorized
1. No comments yet.
1. No trackbacks yet.