Lights Out

This is an implementation of the semi-famous Lights Out! game. The goal is to turn off all of the lights on the board. When any cell is clicked, it and its neighbouring cells will toggle their state. Exactly which pattern of neighbours toggle can be controlled using the small board below.

Dimension of solvable space: . Dimension of whole space: . The probability of a totally random board being solvable is 2.

How does it work?

A lights out board can be thought of as a vector over $\mathbb{F}_2$ , the {field}(https://en.wikipedia.org/wiki/GF(2)) containing only the elements $0$ and $1$ , with multiplication as usual and the extra rule that $1 + 1 = 0$ . Adding vectors has the effect of “toggling” the numbers in the original vector on and off, for example

\begin{bmatrix}0 \\ 1 \\ 1 \\ 0\end{bmatrix} + \begin{bmatrix}0 \\ 1 \\ 0 \\ 1\end{bmatrix} = \begin{bmatrix}0 \\ 0 \\ 1 \\ 1\end{bmatrix}

So each possible board position is a vector over

\mathbb{F}_2

, and each possible move is a vector over

\mathbb{F}_2

. For example, on a

2 \times 2

square board, if we label the top left, top right, bottom left, and bottom right moves as

m_{11}, m_{12}, m_{21}, m_{22}

respectively, we have that

m_{11} = \begin{bmatrix}1 \\ 1 \\ 1 \\ 0\end{bmatrix}, \quad m_{12} = \begin{bmatrix}1 \\ 1 \\ 0 \\ 1\end{bmatrix}, \quad m_{21} = \begin{bmatrix}1 \\ 0 \\ 1 \\ 1\end{bmatrix}, \quad m_{22} = \begin{bmatrix}0 \\ 1 \\ 1 \\ 1\end{bmatrix}

where the numbers are read off row-by-row. We then want to find some combination of these vectors which adds up to give the current board, since that will cancel with the board, turning all of the lights off. In this small case, it’s fairly easy to do this via inspection or trial-and-error, but for larger cases there is a systematic way of solving this kind of vector problem called ◊wikipedia{Gaussian Elimination}.

Try the interactive demo below, which will express the solution to any puzzle in terms of the $m_{ij}$ vectors above.

Generating and solving boards efficiently

Take some board configuration with $n$ cells. By querying each cell about what it toggles on and off, form a vector corresponding to each possible move. These vectors are then assembled into an $n \times n$ matrix $M$ , called the move matrix. Gauss-Jordan Elimination is then performed to put $M$ into reduced row-echelon form: this takes $O(n^3)$ time, and is only done when the size or shape of the board, or thepattern of neighbours changes.

The column space of $M$ is the subspace corresponding to all solvable boards. Using the row-reduction information for $M$ , a basis $B$ is extracted for this subspace in $O(n^2)$ time. To choose a random solvable board uniformly from the space, a random $0,1$ -vector is chosen and multiplied onto $B$ , which takes $O(n^2)$ time.

Solutions to any board position can be found in $O(n^2)$ time using the row-reduction information. What remains to be done here is to try to find a solution using the minimum number of moves, instead of just using any old solution.