Find number of solutions to special "Lights Out!" puzzle scenarios

Question

My question is regarding the special cases of the Light's Out puzzle: http://mathworld.wolfram.com/LightsOutPuzzle.html

I'm considering special scenarios of the puzzle in which the puzzle can be solved by simply toggling all the switches that are 'ON' (indicated as 1 on a matrix) at the beginning.

For the 2x2 configuration, we have: $\begin{bmatrix}1 & 0\\0 & 1\end{bmatrix}$, $\begin{bmatrix}0 & 1\\1 & 0\end{bmatrix}$,$\begin{bmatrix}1 & 1\\1 & 1\end{bmatrix}$ and $\begin{bmatrix}0 & 0\\0 & 0\end{bmatrix}$.

For the 3x3 configuration, a simple script reveals 8 of such scenarios:

$\begin{bmatrix}1 & 0 &0\\0 & 1 &0 \\ 0&0&1\end{bmatrix}$,$\begin{bmatrix}0 & 0 &1\\0 & 1 &0 \\ 1&0&0\end{bmatrix}$,$\begin{bmatrix}0 & 0 &0\\0 & 0 &0 \\ 0&0&0\end{bmatrix}$,$\begin{bmatrix}0 & 1 &1\\1 & 1 &1 \\ 1&1&0\end{bmatrix}$,$\begin{bmatrix}1 & 0 &1\\0 & 0 &0 \\ 1&0&1\end{bmatrix}$,$\begin{bmatrix}0 & 1 &0\\1 & 0 &1 \\ 0&1&0\end{bmatrix}$,$\begin{bmatrix}1 & 1 &0\\1 & 1 &1 \\ 0&1&1\end{bmatrix}$ and

$\begin{bmatrix}1 & 1 &1\\1 & 0 &1 \\ 1&1&1\end{bmatrix}$

Is there a more efficent way of finding the number of such scenarios for 4x4 and higher configurations? My script takes forever.

Answer 1

Suppose $B$ is the matrix that satisfies your condition. For any entry in $B$, notice that it must have an even number of neighbors equal to 1:

• If the entry is a 1, it will be turned off when it is pressed (which it will be by your condition), and then the number of times it is toggled on/off depends solely on the number of its neighbors which are 1, which must be even.
• If the entry is a 0, it is already off and will not be pressed. Again, the number of times it is toggled by other switches depends solely on the number of neighbors that are 1.

It should not be hard to convince yourself that a matrix is is in your scenario if and only if for every entry in the matrix the number of neighbors equal to 1 is even. Equivalently, this is the same as saying that the sum of the neighbors of each entry is 0 mod 2.

As in the link in the OP, you can set up a system of linear equations over $GF(2)$ with this set of conditions and solve it. For example, when $n=3$ we get nine equations: $$\begin{eqnarray*} x_{12} + x_{21} & = & 0\\ x_{11} + x_{13} + x_{22} & = & 0\\ x_{12} + x_{23} & = & 0\\ x_{11} + x_{22} + x_{31} & = & 0\\ x_{12} + x_{21} + x_{23} + x_{32} & = & 0\\ x_{13} + x_{22} + x_{33} & = & 0\\ x_{21} + x_{32} & = & 0\\ x_{22} + x_{31} + x_{33} & = & 0\\ x_{23} + x_{32} & = & 0 \end{eqnarray*} $$

The set of solutions of this system of equations are generated by the matrices:

$\left(\begin{matrix} 1 & 0 & 0\\0 & 1 & 0\\0 & 0 & 1\end{matrix}\right)$ $\left(\begin{matrix} 0 & 1 & 0\\1 & 0 & 1\\0 & 1 & 0\end{matrix}\right)$ $\left(\begin{matrix} 0 & 0 & 1\\0 & 1 & 0\\1 & 0 & 0\end{matrix}\right)$

This is consistent with the observation of @krirkrirk above.

Using the same technique with $n=4$, we find all solutions are generated by:

$\left(\begin{matrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\end{matrix}\right)$ $\left(\begin{matrix}0&1&0&0\\1&0&1&0\\0&1&0&1\\0&0&1&0\end{matrix}\right)$ $\left(\begin{matrix}0&0&1&0\\0&1&0&1\\1&0&1&0\\0&1&0&0\end{matrix}\right)$ $\left(\begin{matrix}0&0&0&1\\0&0&1&0\\0&1&0&0\\1&0&0&0\end{matrix}\right)$

And with $n=5$ we obtain:

$\left(\begin{matrix}1&0&0&0&0\\0&1&0&0&0\\0&0&1&0&0\\0&0&0&1&0\\0&0&0&0&1\end{matrix}\right)$ $\left(\begin{matrix}0&1&0&0&0\\1&0&1&0&0\\0&1&0&1&0\\0&0&1&0&1\\0&0&0&1&0\end{matrix}\right)$ $\left(\begin{matrix}0&0&1&0&0\\0&1&0&1&0\\1&0&1&0&1\\0&1&0&1&0\\0&0&1&0&0\end{matrix}\right)$ $\left(\begin{matrix}0&0&0&1&0\\0&0&1&0&1\\0&1&0&1&0\\1&0&1&0&0\\0&1&0&0&0\end{matrix}\right)$ $\left(\begin{matrix}0&0&0&0&1\\0&0&0&1&0\\0&0&1&0&0\\0&1&0&0&0\\1&0&0&0&0\end{matrix}\right)$