Implementing Papers: Turning Lights Out with Linear Algebra

I recently became fascinated with the idea of implementing papers. The idea is simple: find a technical paper that seems interesting, and implement it in your programming language of choice. I’ve been collecting papers for a while, and I finally got around to implementing one of them: Turning Lights Out with Linear Algebra by Marlow Anderson and Todd Feil. It demonstrates how to use linear algebra to calculate winning strategies for Lights Out, an electronic game released in 1995. The rules of the game are described as follows:

The game Lights Out, commercially available from Tiger Electronics, consists of a \(5 \times 5\) array of 25 lighted buttons; each light may be on or off. A move consists of pushing a single button. Doing so changes the on/off state of the light on the button pushed, and of all its vertical and horizontal neighbors. Given an initial configuration of lights which are turned on, the object is to turn out all the lights. Turning Lights Out with Linear Algebra

I thought it might be fun to implement a playable version of the game in JavaScript. That way, I can easily verify each solution by actually playing the game. Here it is (the source code is available at the end of this page):

In order to understand how it works, we need to dive into a few mathematical details.

The matrix \(A\)

The paper defines a \(25 \times 25\) matrix \(A\). Everything we need to solve any game of Lights Out can be derived from this matrix:

At first glance, it’s not clear what the matrix actually means within the context of the game. What exactly are we representing here?

To answer that question, take the first row:

and arrange it into a \(5 \times 5\) square:

Essentially, this is the result of starting with an empty board and pressing the first button.

Is that true for the other rows as well? Let’s take a look at the 13th row:

Arranging it into a \(5 \times 5\) square gives us:

So the 13th row represents the effect of pressing the 13th button in isolation:

In general, each row of the matrix \(A\) represents the effect of pressing the corresponding button. There’s one major benefit to representing the game this way. We can express the outcome of any sequence of moves as a linear combination of rows of the matrix \(A\). So the row space of \(A\) is the set of game states that result from pressing any sequence of buttons. As it turns out, this is equivalent to the space of winnable games.

Winnable games

Every move in Lights Out is reversible by pressing the same button again. Therefore, every sequence of moves is also reversible by pressing the same sequence of buttons again. If it’s possible to go from an empty game board to a given configuration of lights, then it’s also possible to undo all of those moves and end up with an empty board, thus winning the game.

The paper presents a theorem for determining if a configuration of lights is winnable:

Theorem 1: A configuration \(\vec{b}\) is winnable if and only if \(\vec{b}\) is perpendicular to the two vectors \(\vec{n}_1\) and \(\vec{n}_2\). Turning Lights Out with Linear Algebra

Let’s unpack this, to make sure it’s compatible with the more informal explanation above.

As described in the paper, the vectors \(\vec{n}_1\) and \(\vec{n}_2\) are basis vectors for the null space of \(A\). In linear algebra, the row space is the orthogonal complement of the null space. So this theorem is a roundabout way of saying that a game is winnable if its vector is in the row space of \(A\).

I’m not entirely sure why the theorem is formulated this way. I suspect that it’s easier to calculate whether a vector is not in the null space than it is to determine whether it is in the row space. That would explain why the isWinnable function in my implementation turned out to be a one-liner:

function isWinnable(b) {
  return b.dot(n1) % 2 == 0 && b.dot(n2) % 2 == 0;
}

“Light” and “strategy” spaces

As I was working through the paper, I found it useful to distinguish between the two different vector spaces that are used implicitly throughout the paper:

• One vector space contains 25-element vectors representing the state of the game board. In each vector, a value of 1 means the corresponding light is on, and a value of 0 means the light is off. Let’s call this the “light space.”

• The other vector space contains 25-element vectors that represent a sequence of buttons to be pressed. A value of 1 means the corresponding button should be pressed, and a value of 0 means it should not. Let’s call this the “strategy space.”

The distinction between the two spaces is subtle, as both can be easily visualized on the \(5 \times 5\) game board. In the playable version of the game, the “light space” is the green squares, and the “strategy space” is the characters that appear when solutions are enabled.

The matrix \(A\) represents a linear transformation from the “strategy space” to the “light space.” Given a vector representing a sequence of moves, applying the matrix \(A\) will produce a vector of the resulting configuration of lights.

How the winning strategy is calculated

Being able to determine whether or not a game is winnable is useful, but it doesn’t get us any closer to actually solving it. Another theorem from the paper reveals how to actually compute a winning strategy.

Theorem 2: Suppose that \(\vec{b}\) is a winnable configuration. Then the four winning strategies for \(\vec{b}\) are

• \(R\vec{b}\)
• \(R\vec{b} + \vec{n}_1\)
• \(R\vec{b} + \vec{n}_2\)
• \(R\vec{b} + \vec{n}_1 + \vec{n}_2\) Turning Lights Out with Linear Algebra

\(R\) represents a linear transformation from the “light space” to the “strategy space.” Given a vector representing a configuration of lights, applying the matrix \(R\) will produce the sequence of moves required to turn them all off.

To keep things simple, I only implemented the first of the four strategies, so the vectors \(\vec{n}_1\) and \(\vec{n}_2\) are not needed to calculate a winning strategy. However, we still need \(R\). Since the paper doesn’t give us this matrix, it’s necessary to calculate it by transforming \(A\) into reduced row echelon form, as described in the paper. JavaScript isn’t the best programming language for doing linear algebra over arbitrary fields, so I implemented this part in Python.

from sympy import BlockMatrix, GF, Matrix, eye, zeros
from sympy.polys.matrices import DomainMatrix

I = eye(5)
O = zeros(5, 5)

B = Matrix([
    [1, 1, 0, 0, 0],
    [1, 1, 1, 0, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 1, 1, 1],
    [0, 0, 0, 1, 1],
])

A = BlockMatrix([
    [B, I, O, O, O],
    [I, B, I, O, O],
    [O, I, B, I, O],
    [O, O, I, B, I],
    [O, O, O, I, B],
]).as_explicit()

def rref_over_field(matrix, field):
    """Transform the given matrix to reduced row echelon form over the
    given field.
    """
    domain_matrix = DomainMatrix.from_Matrix(matrix).convert_to(field)
    domain_matrix_rref = domain_matrix.rref()[0]
    return domain_matrix_rref.to_Matrix()

def solve(matrix):
    """Given a matrix with dimensions 25x25. Augment the input matrix
    with the 25x25 identity matrix, then transform it into reduced row
    echelon form.
    """
    augmented_matrix = BlockMatrix([matrix, eye(25)]).as_explicit()
    ER = rref_over_field(augmented_matrix, GF(2))
    E = ER[:, 0:25]
    R = ER[:, 25:50]
    return E, R

E, R = solve(A)

This is what we get for \(R\):

The paper describes this matrix as “rather formidable, and not particularly illuminating.” I’m inclined to agree, and I also appreciate the pun.

At this point, calcuating the winning strategy is straightforward. By applying \(R\) to the game board vector, we get a vector representing the moves required to turn off all the lights. Since the matrix \(R\) only needs to be calculated once, I was able to hard-code it in the JavaScript implementation.

Ignoring irrelevant details

I think the key insight of the paper is its clever choice of representation. Modeling a \(5 \times 5\) game as a \(25 \times 25\) matrix did not seem like the obvious choice to me, but that’s what enables us to apply linear algebra in such a natural way.

In a sense, the matrix \(A\) ignores the two-dimensional nature of Lights Out. It does not capture the concept of “above” or “below.” Even “left” and “right” don’t mean quite the same thing as on the \(5 \times 5\) game board. The distinctive plus sign shape is not recognizable in the rows of \(A\). It’s easy to think of those things as defining characteristics of the game, but we’re able to calculate a winning strategy without them, so maybe they’re not so important after all. If the paper had insisted on a representation that preserves the two-dimensional nature of the game, the math would look a lot more complicated.

Perhaps there’s a general problem-solving lesson here. Some details can be ignored in order to simplify a problem. And some details must be ignored in order to make progress on solving it.

Implementing papers is fun

I had a lot of fun implementing this paper. Eventually, I’d like to start reading and implementing more advanced research papers in math and computer science. But I’m glad I started with a paper that’s short, self-contained, and not too difficult.

I spend a lot of time reading and writing specifications at work. Implementing papers as a side project seems like a pretty good way to practice the skill of turning formal specifications into working code.

Source code

• Playable Lights Out game in JavaScript: singerworks-lights-out-0.1.js

• Python code to calculate the matrix \(R\): lights_out-1.0.py