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:

1. Closure under addition.

2. Closure under multiplication.

3. Associative Law of Addition.

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.

10. Commutative Law of Addition.

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 Z₂) is a field consisting of only two elements 0 and 1. The addition and multiplication on Z₂ will be explained later. One can talk about a vector space over a field k. One example of such a space is kⁿ 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 Z₂ yields an addition on Z₂²⁵ in a natural way.

Of course, to take advantage of this addition in Z₂²⁵ I will want to represent the effect of pressing a button as an element of Z₂²⁵ . 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 Z₂²⁵. Let a_i in Z₂²⁵ (i=1,..,25) be the button action that is caused by pressing the i-th button. For example,

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

a₁₉ = (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 Z₂²⁵ 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 a₂₁ + y. Then I might press the 15th button, resulting in a₁₅ + (a₂₁ + 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

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

This approach is awkward, though. The addition in Z₂²⁵ is commutative, so without loss of generality the sequence n(1)...n(N) can be chosen to be non-decreasing. Furthermore, since a_i + a_i = 0 for all i=1,..,25 (in fact, v + v = 0 for all v in Z₂²⁵ ), 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 Z₂ 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 (Z₂, + ,*) is a field, and with the natural multiplication s*(v₁,..,v₂₅) := (s*v₁,..,s*v₂₅), (Z₂²⁵,+,*) is a vector space over the field Z₂.

Now, the above equation can be equivalently rewritten as

x₁*a₁ + ... + x₂₅*a₂₅ + y = (0,0,...,0)

with some x=(x₁,...,x₂₅) in Z₂²⁵. By adding y to both sides of this equation I get

x₁*a₁ + ... + x₂₅*a₂₅ = 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 a_i (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=(x₁,...,x₂₅) in Z₂²⁵ will make the light pattern y in Z₂²⁵ 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 = b_i

(where { b_i | i=1,...,25} is the Cartesian basis of Z₂²⁵) 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 (x₂₄, x₂₅) can be chosen arbitrarily from Z₂²

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

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

k₂=(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, k₁> = <y, k₂>, where < . , . > denotes the canonical scalar product in Z₂²⁵. It turns out that {k₁, k₂} 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.