# The Mathematics of Lights Out

## The "Lights Out" Game

Lights Out is a puzzle game that was originally produced by Tiger Electronics in 1995. The game consists of a 5-by-5 grid of squares. Each level in the game consists of some collection of squares in the grid that are either in the "on" or "off" state. For instance, we may consider the following level

where the red colored squares represent an "on" state and the white colored squares represent an "off" state. When one presses a square, this toggles the pressed square as well as the neighboring squares to flip to their opposite state. For instance, if we press the center square in the above example this toggles the square itself as well as the top, bottom, left, and right squares to toggle off.

In this case, all squares are toggled in the "off" position. When all squares are in the "off" state, we refer to this as the winning condition of the game. Let's consider board setup from Figure-1 again. If instead of pressing the center square we press the top left square, what we end up with is a configuration that looks like the following.

Note that since there is no top or left square with respect to the square that we pressed, the only squares that are toggled are the square that was pressed along with the bottom and right squares. That is to say, the toggling behavior does not wrap around the board.

Now that we know the rules of the game and the winning condition, feel free to play through some of the levels in the following Javascript demo I coded up. The Javascript source for a simplified implementation may be found on my GitHub page here. Try seeing if you can beat the first three levels:

## An unbeatable configuration

After playing through the above game, perhaps you have a better understanding of the mechanics. Maybe you'd like to code up an implementation yourself and impress your friends (probably not ideal if you like your friends). Anyway, if you wanted to make a function for generating levels, you couldn't necessarily just go willy-nilly and randomly toggle the squares in either an "on" or "off" position. To see why, consider the following configuration that may be activated in the example below.

Come on now. What's taking you so long? Well, as it turns out, no matter how determined you are, the initial configuration in the above example is unsolvable. Your friends (if we can call them that at this point) are probably already at the end of their rope.

So if we want to avoid this scenario where you're unable to win the game, we need to determine whether or not a given configuration is actually solvable. As it turns out, we can use math of all things to help us out here.

## Solving "Lights Out"

First, let's right out of the gate observe that the board can be thought of as a matrix with entries that correspond to whether or not the particular square on the board is toggled "on" or "off". For instance, consider the following configuration that correspond to Level 3 in the interactive Javascript example.

The configuration from Figure-4 corresponds directly to the following matrix

$$ \begin{equation} L = \begin{pmatrix} 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 \end{pmatrix}, \end{equation} $$where the "1" entries indicate a light that is in the "on" state and the "0" entries indicate a light that is in the "off" state. More specifically, we can describe any Lights Out board as a binary-valued matrix.

Now, let's just consider an empty board, just like the one from Figure-2. Note that with respect to matrices, the empty board corresponds to the zero matrix. Given an empty board, if we just toggle the top left square (or equivalently the square at the (1,1) position ), then we can represent the corresponding matrix as

$$ \begin{equation} A_{1,1} = \begin{pmatrix} 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{pmatrix}. \end{equation} $$Likewise, starting with an empty board again, if we toggle the (1,2) position, then the resulting matrix is

$$ \begin{equation} A_{1,2} = \begin{pmatrix} 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{pmatrix}. \end{equation} $$If we were to continue in this manner for every single square on the board, we would obtain a collection of matrices given as

$$ \begin{equation} A_{1,1} = \begin{pmatrix} 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{pmatrix}, \quad A_{1,2} = \begin{pmatrix} 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{pmatrix}, \quad \ldots, \quad A_{5,5} = \begin{pmatrix} 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 \end{pmatrix}. \end{equation} $$These matrices represent the resulting board if the player presses the square at position (i,j). So at this point, we have the matrix L that corresponds to some level configuration and the collection of A_{i,j} matrices that represent the result of every move on an empty board. Let's take a step back and remind ourselves of what our goal is: we want a method to determine whether or not a given configuration is solvable. With respect to matrices, we may phrase this goal as: given some matrix L, what are the moves that must be carried out to obtain the zero matrix. As it turns out, we can frame this problem as solving a system of linear equations mod 2, that is we want to solve the following equation

$$ Ax = b. $$ Let's first take a look at how we construct the A matrix. For any 5-by-5 board, this matrix will take the form $$ A = \begin{pmatrix} A_{1,1} + L & \ldots & A_{1,5} + L \\ \vdots & \ddots & \vdots \\ A_{5,1} + L & \ldots & A_{5,5} + L \end{pmatrix}. $$ The vector b corresponds to the vectorization of matrix L, that is, we simply stack the rows of the matrix L on top of one another. For example, the vector b corresponding to Figure-4 looks like this $$ b = vec(L) = \begin{pmatrix} 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \end{pmatrix}^{T}, $$where the "T" denotes the transpose operation. Finally the solution vector x corresponds to how many times we need to press the square in order to obtain the zero matrix, or equivalently, a winning condition. If we solve for x from Figure-4, we obtain a solution vector that corresponds to $$ x = \begin{pmatrix} 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \end{pmatrix}^{T}. $$ Interpreting the solution vector, it tells us if we press the (1,5), (3,3), and (5,1) squares we will solve the puzzle. Indeed, if you follow this prescription for Level 3 in the Javascript example, you will solve the puzzle. If there is no valid solution vector, then we may conclude that the configuration is unsolvable, a condition that one surely would desire to check before providing the game to the user.