The solution to the lights game

Consider the following game:

The game is a grid of 5 by 5 buttons that can light up. Pressing a button will toggle its light (on/off or off/on), but it will also toggle the lights of the (4, 3, or 2) adjacent buttons around. Each problem presents you with a certain pattern of lit buttons and to solve the puzzle you have to turn all the lights out (which is not easy because if you're not careful you will turn more lights on than off). This is the primary goal; the secondary goal is to accomplish this with as few moves (pressing a button is one move) as possible.

The solution presented here uses the algebraic notion of "fields". A field is a set with two operations, addition and multiplication that satisfies the following axioms:

2.  Closure under multiplication.

4.  Associative Law of Multiplication.

5.  Distributive Law.

6.  Existence of 0.

7.  Existence of 1.

8.  Existence of additive inverses (negatives).

9.  Existence of multiplicative inverses (reciprocals), except for 0.

11. Commutative Law of Multiplication.

Examples of fields are Q (rational numbers), R (real numbers), C (complex numbers), and Z/pZ (integers modulo a prime p).

In particular, Z/2Z (denoted usually by Z2) is a field consisting of only two elements 0 and 1. The addition and multiplication on Z2 will be explained later. One can talk about a vector space over a field k. One example of such a space is kn where n is a positive integer.

Let us return to our game now. Carsten Haese gives the solution presented below.

The goal here is to find a universal solution to this puzzle, i.e. to find a general algorithm that will tell you which buttons you have to press given a certain initial pattern. The central questions concerning this universal solution are

a) Is there a solution for any initial pattern? If yes, why? If not, describe the set of initial patterns that have a solution.

b) Assuming a solution exists for a given initial pattern, how can this solution be derived from the pattern?

This approach to the puzzle is to find an equation that describes how pressing the buttons will affect the lights. First, I need to represent the lights numerically. One obvious representation that incidentally will also prove to be algebraically very useful is to represent an unlit button with 0 and a lit button with 1. I enumerate the 25 buttons/lights from left to right, top to bottom and thus each pattern of lights is represented by a

25-tuple of 0’s and 1’s, i.e. by an element of the set .

To represent the way in which pressing a button affects the pattern of lights, I define an addition operator on the set by This describes accurately the switching mechanism when one summand represents the state of a light and the other summand represents whether or not that light is switched. (Not switching an unlit button results in an unlit button, as well as switching a lit button; not switching a lit button results in a lit button, as well as switching an unlit button.) By componentwise application, the addition on Z2 yields an addition on Z225 in a natural way.

Of course, to take advantage of this addition in Z225 I will want to represent the effect of pressing a button as an element of Z225 . I do this the obvious way. Each button has its own pattern of which lights it will switch and which lights it will leave. By writing 0 for leaving the button unchanged and 1 for switching, each of the buttons (or rather the "button action", i.e. the effect of pressing that button) is described by an element in Z225. Let ai in Z225 (i=1,..,25) be the button action that is caused by pressing the i-th button. For example,

a2 = (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),

a19 = (0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,1,1,0,0,0,1,0).

I can now start the first attempt at writing down an equation that will solve a lights out puzzle. Let y in Z225 be the initial light pattern of the puzzle. Now I might play around with the buttons, for example by pressing the 21st button I would transform the light pattern y into a21 + y. Then I might press the 15th button, resulting in a15 + (a21 + y). And so on. The addition is associative, so I can spare the parentheses without ambiguity. The goal is to find a (finite!) sequence (n(1),n(2),...,n(N)) such that

an(N) + an(N-1) + ... + an(1) + y = (0,0,...,0).

This approach is awkward, though. The addition in Z225 is commutative, so without loss of generality the sequence n(1)...n(N) can be chosen to be non-decreasing. Furthermore, since ai + ai = 0 for all i=1,..,25 (in fact, v + v = 0 for all v in Z225 ), the sequence can even be chosen to be strictly increasing since no button action needs to be performed more than once. Evidently this means that N≤25. To achieve an elegant form of the equation with exactly 25 summands, I define a multiplication operator on Z2 that will allow me to skip those button actions that are not needed in the solution sequence. I define 0*0 := 0*1 := 1*0 := 0 and 1*1 := 1. It is known that (Z2, + ,*) is a field, and with the natural multiplication s*(v1,..,v25) := (s*v1,..,s*v25), (Z225,+,*)  is a vector space over the field Z2.

Now, the above equation can be equivalently rewritten as

x1*a1 + ... + x25*a25 + y = (0,0,...,0)

with some x=(x1,...,x25) in Z225. By adding y to both sides of this equation I get

x1*a1 + ... + x25*a25 = y.

Now I want to write the left hand side as a matrix product. I should mention at this point that all vectors are supposed to be columns, even if I write them as rows for convenience.

If I let M be the matrix whose i-th row is ai  (transposed), my equation becomes

Mx = y.

It is easy to verify that M is the block matrix with ,

I is the identity matrix 5x5 and 0 is the zero matrix 5x5.

Now I have completed the task of finding an equation that describes the solution of a lights out puzzle. A sequence of button actions that is described by x=(x1,...,x25) in Z225 will make the light pattern y in Z225 vanish if and only if Mx = y. This is a linear equation in a vector space, so even though the equation does not deal with real numbers, I can apply standard solving methods.

The above questions can now be answered by studying the properties of M.

I have written a small computer program that simultaneously solves the 25 equations

Mx = bi

(where { bi | i=1,...,25} is the Cartesian basis of Z225) using Gauss elimination. If you want to solve the equation by hand, feel free to do so)

I won't flood this paper with the result matrix, even though the following main results can't really be verified without it.

The main results are:

* dim range M = 23, dim ker M = 2.

Therefore there are puzzles that can't be solved. Those that can be solved have 4 different solutions because (x24, x25) can be chosen arbitrarily from Z22

* Examining the last two lines in the final matrix yields a criterion for the existence of a solution. With the vectors

k1=(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),

k2=(1,1,0,1,1,0,0,0,0,0,1,1,0,1,1,0,0,0,0,0,1,1,0,1,1).

The criterion can be written as 0 = <y, k1> = <y, k2>, where < .  ,  . > denotes the canonical scalar product in Z225. It turns out that {k1, k2} is a basis of ker M, which is not really surprising because the solvability of Mx=y is equivalent to y being in range M which (since M is symmetric) is equivalent to y being orthogonal to ker M.

* A general solving algorithm (i.e. a formula that expresses x in terms of y) can also be found easily by evaluating the result matrix. Such an algorithm would only be suitable for a computer, though. If you are interested in a solution that a human can easily perform, I suggest the following exercises:

1) Show that for any initial pattern there is a sequence of moves that reduces the pattern to the first line.

2) Assuming solvability, show that there are 7 nontrivial patterns that have lights only in the first line.

3) Derive the solutions of these seven patterns from the final matrix.

4) Memorize them and impress your friends.

This approach never yields a minimal solution because you will most likely press buttons twice, but it is a solution nevertheless.