LightsOut is an electronic single player game manufactured by Tiger Toys in 1995. In the original version, 25 lights are arranged in a 5 by 5 lattice. Each of these lights can either be on or off and its state can be inverted with a button related to that light. Additionally, all four horizontally and vertically adjacent lights - forming a cross - get inverted as well when a single light gets pressed. The goal is to turn all lights out, starting with a random pattern of lights, although we will see that not every pattern has a solution.
A related problem consists of finding a solution when all lights are initially turned on, which is known as the "all-ones problem" and is possible for any square lattice, as shown by Sutner (1989). In this article the optimal solution in terms of the number of moves for LightsOut is derived using linear algebra and a demo is implemented in JavaScript.
Derivation
A given light configuration can be represented as a matrix \(\mathcal{C}\in\mathbb{Z}^{n\times m}_2\), a matrix of integers modulo 2 where a \(1\) represents a light turned on and \(0\) a light turned off. This makes sense, as any even number of presses of the same button will always restore the previous state, from which follows that we need to push every button no more than once. As an example, for a smaller \(3\times 3\) lattice the configuration will look as follows:
\[\mathcal{C} = \left(\begin{array}{ccc} 1 & 0 & 1\\ 0 & 0 & 1\\ 1 & 1 & 0\\ \end{array} \right)\]
Now each light can be pressed, forcing adjacent lights to be inverted as well. We will represent a button press in row \(i\) and column \(j\) as a matrix \(\mathcal{A}_{i, j}\), which changes the configuration \(\mathcal{C}\) with addition in \(\mathbb{Z}_2\) like for the new state \(\mathcal{C}'=\mathcal{C}+\mathcal{A}_{i, j}\). An example \(3\times 3\) modification matrix, which encodes the game rules is
\[\mathcal{A}_{22} = \left(\begin{array}{ccc} 0 & 1 & 0\\ 1 & 1 & 1\\ 0 & 1 & 0\\ \end{array} \right)\]
Every new state \(\mathcal{C}'\) depends only on the buttons pressed, no matter in what order. This means that if we start with an empty lattice and turn on lights at random, all we have to do is push the same buttons again to return to an empty lattice. This coincides with the commutative property of matrix addition. Mathematically, a winning combination can then be expressed as
\[\mathcal{C} + \sum\limits_{i, j}\beta_{i, j}\mathcal{A}_{i, j} = \mathbf{0}\]
where \(\mathbf{0}\) denotes a zero matrix, having all lights turned off, and the coefficients \(\beta_{i, j}\) indicates if the button \((i, j)\) must be pressed for a winning solution. Since we operate in \(\mathbb{Z}_2\), \(-1\equiv 1\pmod{2}\) and as such can be written:
\[\sum\limits_{i, j}\beta_{i, j}\mathcal{A}_{i, j} = \mathcal{C} \]
From now on we see the initial configuration \(\mathcal{C}\) and the winning solution \(\beta\) as a vector and the transformation matrix \(\mathcal{A}\) as a collection of all \(n\times m\) possible patterns \(\mathcal{A}_{i,j}\). That is, every row of \(\mathcal{A}\) is a vector representation of \(\mathcal{A}\) through all possible positions \((i, j\)). We finally end up at a linear equation like this:
\[\underbrace{\left(\begin{array}{c}\mathcal{A}_{1,1} \\ \mathcal{A}_{1,2} \\ ... \\ \mathcal{A}_{1,m} \\ ... \\ \mathcal{A}_{n, m}\end{array}\right)}_{\mathcal{A}} \cdot \underbrace{\left(\begin{array}{c}\beta_{1,1} \\ \beta_{1,2} \\ ... \\ \beta_{1,m} \\ ... \\ \beta_{n, m}\end{array}\right)}_{\beta} = \underbrace{\left(\begin{array}{c}\mathcal{C}_{1,1}\\ \mathcal{C}_{1,2}\\ ...\\ \mathcal{C}_{1,m}\\ ...\\ \mathcal{C}_{n, m}\end{array}\right)}_{\mathcal{C}}\]
\(\mathcal{A}\) is vacuously symmetrical and has at most 5 ones in a row. For the \(3\times 3\) example the resulting \(9\times 9\) matrix \(\mathcal{A}\) looks as follows, where a vectorized form of \(\mathcal{A}_{i,j}\) forms the rows of the matrix:
\[\mathcal{A}=\left(\begin{array}{ccccccccc} 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 1 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0\\ 1 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0\\ 0 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 0\\ 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1\\ 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1\\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 \end{array}\right) \]
Given the linear equation \(\mathcal{A}\beta = \mathcal{C}\), we can solve for \(\beta=\mathcal{A}^{-1}\mathcal{C}\) by multiplying both sites with the inverse of \(\mathcal{A}\) if and only if the matrix \(\mathcal{A}\) has full rank (which is the case for example for \(4\times 4, 9\times 9, 36\times 36\text{ or }49\times 49\)) and \(\mathcal{C}\) is winnable at all. Given an arbitrary configuration \(\mathcal{C}\), we say that \(\mathcal{C}\) is winnable if there exists a strategy \(\beta\) to turn out all lights in \(\mathcal{C}\), which is the case if and only if \(\beta\) belongs to the column space of matrix \(\mathcal{A}\), denoted as \(\text{col}(\mathcal{A})\).
More problematic is the standard Lights Out lattice with a matrix \(\mathcal{A}\) of size \(25\times 25\), where we have a rank of 23 and thus two freely parameterizable variables, resulting in four possible optimal solutions. In either case, we first use Gauss-Jordan elimination on the field \(\mathbb{Z}_2\) to calculate the rank of the matrix, analyze \(\text{col}(\mathcal{A})\) to determine if a solution exists at all and come up with the row echelon form \(E=R\mathcal{A}\) of the matrix, with \(R\) being the product of all Gauss-Jordan row operations on \(\mathcal{A}\).
Since \(\mathcal{A}\) is symmetric, the column space \(col(\mathcal{A})\) is identical to the row space \(row(\mathcal{A})\), which becomes obvious when looking at the eigenvector decomposition. From the definition of a row- and null-spaces we know that \(row(\mathcal{A})\) equals the orthogonal complement of the null space of \(\mathcal{A}\), denoted as \(null(\mathcal{A})\). Since the null space is not affected by Gauss-Jordan row operations it becomes clear that \(null(\mathcal{A})=null(E)\). It follows that \(\mathcal{C}\) is winnable if and only if \(\mathcal{C}\) belongs to the orthogonal complement of \(null(E)\). This means we need to find an orthogonal basis for \(null(E)\) and to do so, we interpret \(E\) as a system of equations and solve for the dependent variables:
\[ \begin{array}{rl} e_1 &=\\ e_2 &= \\ e_3 &= \\ \vdots &= e_{24}\\ e_{23} &= \\ e_{24} &= \\ e_{25} &= \\ \end{array} \left(\begin{array}{c} 0\\ 1\\ 1\\ \vdots\\ 1\\ 1\\ 0 \end{array}\right) +e_{25}\left(\begin{array}{c} 1\\ 0\\ 1\\ \vdots\\ 1\\ 0\\ 1 \end{array}\right) \]
For the \(25\times 25\) example follows that \(\mathcal{C}\) is winnable if and only if \(\mathcal{C}\) is orthogonal to the following two vectors, which form the basis for \(null(E)\):
\[\mathbf{v}_1 = (0,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,1,1,0)^T\]
\[\mathbf{v}_2 = (1,0,1,0,1,1,0,1,0,1,0,0,0,0,0,1,0,1,0,1,1,0,1,0,1)^T\]
To check if the two vectors really form an orthogonal basis, we must show the dot-product of the two vectors are equal to zero. We find that \(\mathbf{v}_1\cdot\mathbf{v}_2=0\), calculated in modulo 2. Since \(\mathcal{C}\) is winnable if and only if it belongs to the orthogonal complement of \(null(E)\), it follows that to see if a configuration is winnable, we compute the dot-product of that configuration \(\mathcal{C}\) with \(\mathbf{v}_1\) and \(\mathbf{v}_2\). Furthermore, if \(\mathcal{C}\) is a winning configuration with strategy \(\beta\), then \(\beta+\mathbf{v}_1\), \(\beta+\mathbf{v}_2\), \(\beta+\mathbf{v}_1+\mathbf{v}_2\) are also winning strategies.
Suppose now that \(\mathcal{C}\) is a winnable configuration. If we were to find just an arbitrary solution, we may set the two free variables \(\beta_{24}\) and \(\beta_{25}\) equal to zero. In this case \(\beta= E\beta\), whereby \(\beta= E\beta =R\mathcal{A}\beta=R\mathcal{C}\). This means we have an arbitrary solution with \(\beta=R\mathcal{C}\). Since we want to find the optimal solution, we need to check for the best strategy \(\beta\) among the four binary combinations of \(\beta_{24}\) and \(\beta_{25}\), which leads analogously to: \[ \begin{array}{rl} \beta^{(0)}&=R\mathcal{C}\\ \beta^{(1)}&=R\mathcal{C}+\mathbf{v}_1\\ \beta^{(2)}&=R\mathcal{C}+\mathbf{v}_2\\ \beta^{(3)}&=R\mathcal{C}+\mathbf{v}_1+\mathbf{v}_2 \end{array}\]
And finally the solution \(\beta = \min\limits_{\|\beta^{(k)}\|_1}\beta^{(k)}\), where \(\|\cdot\|_1\) is the \(\ell_1\) norm, or the Hamming-Distance to vector \(\mathbf{0}\).
References
- AndersonM. Anderson (2006) Turning Lights Out with Linear Algebra
- MinevichI. Minevich (2012) Symmetric Matrices over \(F_2\) and the Lights Out Problem
- ErikssonH. Eriksson, K. Eriksson, J. Sjöstrand (2001) Note on the lamp lighting problem