Lights Out

The handheld game is a five-by-five grid of lights. Press one and it toggles, on to off or off to on, and so do its orthogonal neighbours, the press spreading in a small plus. The board starts lit and the goal is to leave it dark, every light out, ideally in as few presses as possible. The lights interact so freely that the game looks like it needs trial and error. It does not. The whole puzzle is one fact about even and odd numbers, and once that is seen the press list falls out of a short program.

Parity, not search

Two observations strip the game to its bones. Pressing a cell twice returns the board to where it was, so no cell is ever worth pressing more than once, and the order of presses makes no difference, since each press toggles its plus regardless of what came before. A solution is therefore just a set of cells to press, and a cell’s final state depends on one number alone: how many of the presses in its neighbourhood were made. Press that neighbourhood an odd number of times and the cell flips; an even number and it stays. Everything reduces to parity.

Let $x_c = 1$ mean cell $c$ is pressed. A cell $c$ that should change state, from lit to dark, must be toggled an odd number of times, so the presses falling in its neighbourhood $\mathcal{N}(c)$, the cell itself and its orthogonal neighbours, must sum to an odd number; a cell that should keep its state must be toggled an even number of times. Writing $t_c = 0$ for a cell that must stay and $t_c = 1$ for one that must flip, the condition is $$\sum_{b \,\in\, \mathcal{N}(c)} x_b \;\equiv\; t_c \pmod{2} \qquad \forall c.$$ This is a system of linear equations over the two-element field, one per cell, and it is the entire puzzle. To put it to a solver that thinks in ordinary integers, replace each congruence with an equation carrying a spare non-negative integer $d_c$ to absorb the multiple of two, $$\sum_{b \,\in\, \mathcal{N}(c)} x_b \;=\; 2 d_c + t_c \qquad \forall c,$$ which says the same thing: the neighbourhood press count equals $t_c$ plus some even number. Among all assignments that satisfy every parity equation, the one to want is the lightest, the fewest presses, so the press count is what we minimise.

A solver

Nothing in the model mentions five, or two dimensions. A cell is a tuple of coordinates, its neighbourhood is the cell and the coordinates one step away along each axis, and the same handful of lines solves a line, a grid, a cube, or a grid of any number of dimensions at all.

from ortools.sat.python import cp_model
from itertools import product

def neighbours(c, shape):  # the cell and its orthogonal neighbours
    yield c
    for axis, s in enumerate(shape):
        for step in (-1, 1):
            d = list(c)
            d[axis] += step
            if 0 <= d[axis] < s:
                yield tuple(d)

def solve(shape, lit=None):
    cells = list(product(*(range(s) for s in shape)))
    lit = set() if lit is None else set(lit)
    m = cp_model.CpModel()
    x = {c: m.NewBoolVar("") for c in cells}
    for c in cells:
        presses = sum(x[b] for b in neighbours(c, shape))
        d = m.NewIntVar(0, len(cells), "")
        flip = 0 if c in lit else 1          # lit cells stay, dark cells flip
        m.Add(presses == 2 * d + flip)
    m.Minimize(sum(x.values()))              # fewest presses
    s = cp_model.CpSolver()
    if s.Solve(m) not in (cp_model.OPTIMAL, cp_model.FEASIBLE):
        return None
    return {c for c in cells if s.Value(x[c])}

Here lit holds the cells already on, and a dark board, the classic start, is the default. The board is lit when every cell flips, so each equation reads $2 d_c + 1$; solving for a fully lit start instead, to switch the board off, is the mirror image and the same press set.

Into higher dimensions

On the five-by-five board the program prints fifteen cells, drawn in Figure 38.1, and fifteen is provably the fewest: the solver minimises the count and proves no smaller set obeys every parity equation. That the answer is small and rigid is no accident. Anderson and Feil showed by exactly this linear algebra that a solvable five-by-five board has precisely four solutions, the affine coset of a two-dimensional null space, and the program simply picks the lightest of the four.

The model’s indifference to dimension is the point the puzzle is named for. A four-dimensional board of side three is eighty-one cells, each with up to eight neighbours, and clicking ripples through the fourth dimension as readily as the first. The same solve lights it from dark in forty-one presses, again the proven minimum, and returns in moments; when the puzzle’s source first posed it, a general-purpose integer-programming package ran for two hours on the four-dimensional case without an answer, and only a switch to a satisfiability solver brought it down to seconds. The parity system was always small. What has changed is how quickly the machinery now reads it.

Sources. Lights Out was released by Tiger Electronics in $1995$, a five-by-five grid in which each press toggles a cell and its orthogonal neighbours and the aim is to darken the board; it has an ancestor in Parker Brothers’ Merlin of $1978$. The linear-algebra reading, that solvability and the count of solutions follow from the rank of the toggle matrix over the two-element field, is due to Marlow Anderson and Todd Feil, “Turning Lights Out with Linear Algebra,” Mathematics Magazine volume $71$ ($1998$), pages $300$–$303$; the four-solution count for a solvable five-by-five board is theirs. The integer-programming formulation, the dimension-agnostic treatment, and the four-dimensional hypercube instance follow Martin J. Chlond, Puzzle—Shedding Light on Higher Dimensions, INFORMS Transactions on Education volume $15$, number $2$ ($2015$), pages $197$–$199$, which credits Jaap Scherphuis’s puzzle pages for the graph and hypercube boards. The fifteen-press solution drawn here and the forty-one-press hypercube solution are produced by the model above and re-checked by replaying the presses to confirm the board ends lit.