Integer program for Lights Out game

Question

In Tiger Electronic's handheld electronic solitaire game Lights Out, the player strives to turn out all 25 lights that make up a $5 \times 5$ grid of cells. On each turn the player is allowed to clock on any one cell. Clicking on a cell activates a switch that causes the states of the cell and its neighbors to change from on to off or from off to on. Corner cells are considered to have two neighbors, edge cells to have three, and interior cells to have four. The diagram demonstrates what happens when the player clocks on cell (1,1) and (1,2).

Formulate an integer program for finding a way to turn out all the lights in as few turns as possible. Hints: (1) The order in which the cells are clicked doesn't matter. (2) A cell shouldn't be clicked more than once.

Answer 1

To formulate a MIP model, you can keep track of the number times a light has been switched on or off. We then say the final state should be even ($0,2,4,..$ means off and $1,3,5,...$ means on). So the main equation becomes:

$$ 2 y(i,j) = 1 + s_{i,j} + \sum_{(i',j') \in N(i,j)} s_{i',j'} $$

We have:

• $s_{i,j} \in \{0,1\}$ indicates which lights we switch
• $N(i,j)$ are the neighbors of $(i,j)$
• $y_{i,j}$ is an integer variable forcing the final state to be even
• The constant 1 indicates the initial state.

To find the minimum number of lights we switch, we minimize $\sum_{i,j} s_{i,j}$. The optimal objective is 15.

Answer 2

Let $x_{ij}$ be the number of times the cell $(i,j)$ is clicked. This is a $\mathbb{Z}_2$ field problem: $x_{ij}=\mbox{odd}$ is equivalent to $x_{ij}=1$ and $x_{ij}=\mbox{even}$ is equivalent to $x_{ij}=0$. That's why you never need to hit a cell more than once. To turn off all the lights, we require

$$\left\{\, \begin{array}{ll} x_{11}+x_{12}+x_{21}\equiv 1\,(\mbox{mod }2),&\mbox{to turn off cell }(1,1)\\ x_{11}+x_{12}+x_{13}+x_{22}\equiv 1\,(\mbox{mod }2),&\mbox{to turn off cell }(1,2)\\ \cdots\,\cdots\;\cdots\,\cdots\;\cdots\,\cdots\;\cdots\,\cdots & \ \\ x_{12}+x_{21}+x_{22}+x_{23}+x_{32}\equiv 1\,(\mbox{mod }2), &\mbox{to turn off cell }(2,2)\\ \cdots\,\cdots\;\cdots\,\cdots\;\cdots\,\cdots\;\cdots\,\cdots & \ \\ x_{45}+x_{54}+x_{55}\equiv 1\,(\mbox{mod }2), &\mbox{to turn off cell }(5,5). \end{array}\right.$$

Altogether $25$ equations for $25$ unknowns to turn off all the $25$ lights. One can solve them using Gaussian elimination to upper-triangularize the matrix. At the end of the calculation, $2$ equations get eliminated into $0\equiv 0\,(\mbox{mod }2)$. So there are $4$ solutions with free choices of $x_{54},x_{55}\in\mathbb{Z}_2$. Once they are given, the other $23$ variables are determined by the linear equations. The $4$ solutions turn out to be rotationally equivalent. They are given by $$\begin{array}{l} 0\;1\;1\;0\;1\\ 0\;1\;1\;1\;0\\ 0\;0\;1\;1\;1\\ 1\;1\;0\;1\;1\\ 1\;1\;0\;0\;0 \end{array}\quad \begin{array}{l} 1\;1\;0\;0\;0\\ 1\;1\;0\;1\;1\\ 0\;0\;1\;1\;1\\ 0\;1\;1\;1\;0\\ 0\;1\;1\;0\;1 \end{array}\quad \begin{array}{l} 0\;0\;0\;1\;1\\ 1\;1\;0\;1\;1\\ 1\;1\;1\;0\;0\\ 0\;1\;1\;1\;0\\ 1\;0\;1\;1\;0 \end{array}\quad \begin{array}{l} 1\;0\;1\;1\;0\\ 0\;1\;1\;1\;0\\ 1\;1\;1\;0\;0\\ 1\;1\;0\;1\;1\\ 0\;0\;0\;1\;1 \end{array}$$ So either solution requires hitting $15$ cells to turn off all the lights.