Lights Out

Lights Out is a commercially marketed (by Tiger Electronics) product whose analysis admits a linear algebra framework analogous to that of Merlin's Magic Square puzzle. It consists of a 5×5 array of buttons that may be in one of two positions: on or off. Pressing a button changes its state and that of its vertical and horizontal neighbors. For a given configuration, the task is to turn all the buttons off (out.)

The Theory

Copyright © 1996-2008 Alexander Bogomolny

Like the games of Merlin's Magic Square and Mini Lights Out, this one admits a theory based on linear algebra. It can be shown that a solution does not always exists and, for this reason, when it does, it is not unique. Here we deal with vectors with 25 components and 25×25 matrices. There are notational shortcuts that make the description manageable, but for the sake of variety I shall present a more intuitive approach [see the referenced article].

The most important observation in this puzzle is that with the given geometry of the neighborhoods it is always possible to reach a state in which all the buttons in the first 4 rows are off. In other words, every 5×5 configuration of buttons is reducible to a 1×5 configuration of the last row. Furthermore, since double clicking a button leaves a configuration unchanged, every 5×5 configuration can be obtained from the bottom 1×5 configuration by clicking exactly same buttons.

For the sake of reference, the procedure that leads to switching off all the buttons in the first four rows is called gathering. You start in the second row and press the buttons which are just below the lit buttons in the first row. Then press those buttons in the third row that are beneath the lit buttons in the second. And so on.

Solving the puzzle then can be done in three steps:

1. Gathering.
2. Selecting and pressing a few buttons in the first row.
3. Gathering.

We concentrate in the second step. What we need to learn is the effect of pressing the buttons in the first row, on the state of the buttons at the bottom after gathering. Let's summarize the facts that can be found experimentally:

On the left we press one button at a time. On the right we see the bottom row after gathering. Observe some equivalences:

This tells us that it should never be necessary on the second step to press the last two buttons in the first row. We similarly have the following combinations

Which make finding buttons in the second step a trivial matter. For example, to put out buttons 3, 4, 5 in the bottom row, we should choose buttons 2 and 3 in the first. To put out buttons 1 and 2 in the bottom row, we should press button 3 in the first and proceed with gathering.

The three step procedure either leads to a solution of the puzzle or shows that no solution is available. Note that the procedure guarantees that at the end only buttons 4 and 5 in the bottom row may remain on. We can detect whether if any will immediately after the first gathering.

The equivalencies above show that there are "neutral sets", i.e. collections of buttons in the first row pressing which (with subsequent gathering) does not affect the bottom row. For example, there are two

Since gathering a neutral set on an unlit board leaves the entire board turned out, it must be that the procedure of gathering a neutral set causes every button to be toggled an even number of times (0 or more); and since the state of a button may be only affected by toggling its neighbors, any gathering of a neutral set toggles an even number of neighbors in every button's neighborhood. By symmetry, pressing any button toggles an even number of buttons in N, a set of all button pressed in gathering starting with a neutral set. This is in particular true of buttons in N from the bottom row. One can easily verify that for the two neutral sets above the buttons from N in the bottom row are exactly the same as in the first. (There are two other neutral sets: the empty set and the combination of the first two in which all, but #3, buttons are on.) Thus a configuration is solvable if and only if it has an even number of lit buttons among two sets, {1, 3, 5} and {2, 3, 4}.

Since there are four neutral sets, there are four solutions for any solvable configuration.

References

1. Ó. Martín-Sánchez, C. Pareja-Flores, Two Reflected Analyses of Lights Out, Mathematics Magazine, Vol. 74, No. 4. (Oct., 2001), pp. 295-304.

Copyright © 1996-2008 Alexander Bogomolny