The Lights Out Puzzle
Solution

Puzzle 1: Here is a solution for the 5 x 5 case. Press the indicated buttons once, in any order you like, and all the lights will be out when you are done!

        +---+---+---+---+---+
        |   |   |   | D | E |
        +---+---+---+---+---+
        | F | G |   | I | J |
        +---+---+---+---+---+
        | K | L | M |   |   |
        +---+---+---+---+---+
        |   | Q | R | S |   |
        +---+---+---+---+---+
        | U |   | W | X |   | 
        +---+---+---+---+---+

Obviously, there are three more solutions that can be obtained by rotating this figure 90, 180, or 270 degrees. We'll see why in a minute.

One interesting insight, from Anderson and Feil, is the following. Suppose we know which buttons to push in row 1. Then we can figure out the rest of the solution as follows. If any light is on in row 1, then the corresponding button in row 2 must be pushed to turn it off, and no other buttons in row 2 may be pushed. Then, we can move to row 3 and reason the same way. In fact, this is how I found the above solution. I started by guessing that the buttons to push in the first row were "----E" and worked out the rest of the pattern, only to find that the last row still had lights on. Then I tried "---D-", and then "---DE", which worked.

Shen claims that the problem can always be solved, if it is required to start with all lights on and transform it to all lights off. Anderson and Feil show that, for the 5 x 5 grid, if we start with an arbitrary pattern of lights on, then 75% of the time we will be unable to reach lights out. They use a linear algebra technique, and arithmetic mod 2, to show how any problem can be analyzed to determine if there is a solution, and what that solution would be.

By the way, one reason that not all puzzles are solvable is that there is a two dimensional null space associated with the problem. Essentially, this means that there are two distinct patterns of button pressing that result in no lights being on. The representative patterns chosen by Anderson and Feil are the "cross":

        +---+---+---+---+---+
        |   | B | C | D |   |
        +---+---+---+---+---+
        | F |   | H |   | J |
        +---+---+---+---+---+
        | K | L |   | N | O |
        +---+---+---+---+---+
        | P |   | R |   | T |
        +---+---+---+---+---+
        |   | V | W | X |   | 
        +---+---+---+---+---+

(the "X" is missing in the original paper), and the "comb":

        +---+---+---+---+---+
        | A |   | C |   | E |
        +---+---+---+---+---+
        | F |   | H |   | J |
        +---+---+---+---+---+
        |   |   |   |   |   |
        +---+---+---+---+---+
        | P |   | R |   | T |
        +---+---+---+---+---+
        | U |   | W |   | Y | 
        +---+---+---+---+---+

One way to verify that these patterns result in no lights on is to note that, for each pattern, every cell has an even number of "pushed" neighbors (considering itself, north, south, east and west).

The two patterns above form a basis for the null space. We can "add" either pattern to any pattern without changing the resulting light configuration, although we need to do this modulo 2, which accounts for the fact that pushing a button twice is the same as not pushing it at all. However, if we simply add our two basic null space patterns, we get a very revealing pattern:

        +---+---+---+---+---+
        | A | B |   | D | E |
        +---+---+---+---+---+
        |   |   |   |   |   |
        +---+---+---+---+---+
        | K | L |   | N | O |
        +---+---+---+---+---+
        |   |   |   |   |   |
        +---+---+---+---+---+
        | U | V |   | X | Y | 
        +---+---+---+---+---+

which is simply the "transpose" of the comb solution. In keeping with the symmetry of our problem, it seems more satisfactory to use the comb and the transposed comb as the basis for our null space. The cross can be regarded as the sum of the two combs.

Now let us look at the solution to the 5 x 5 puzzle that we gave above. We said there were obviously 3 more solutions, since we can rotate our given solution. This in fact can be represented by writing the set of solutions as

{ s, s+comb, s+comb', s+comb+comb' }

where the apostrophe is used to designate the transpose. Keeping in mind that we are working modulo 2, we are essentially using the mathematical technique of representing all solutions to a problem as the sum of one particular solution plus any combination of solutions of the homogeneous problem.

The null space solutions tell you many interesting things about the problem. In particular, for a particular grid size, if there are no null space solutions (or, as a mathematician would say, there is only the "trivial" null space solution), then every configuration is solvable. Secondly, the dimension of the null space tells you the chances that a randomly configured problem is solvable. And third, a basis for the null space allows you to display all variations of the solution.

Anderson and Feil worked out the dimension of the null space for problems on a square grid:
Dimension of the null space for an N by N grid.
N Dimension N Dimension N Dimension

0 10 0 20 0

1 0 11 6 21 0

2 0 12 0 22

3 0 13 0 23

4 4 14 4 24

5 2 15 0 25

6 0 16 8 26

7 0 17 2 27

8 0 18 0 28

9 8 19 16 29

Dimension of the null space for an N by N grid.
N	Dimension	N	Dimension	N	Dimension
0		10	0	20	0
1	0	11	6	21	0
2	0	12	0	22
3	0	13	0	23
4	4	14	4	24
5	2	15	0	25
6	0	16	8	26
7	0	17	2	27
8	0	18	0	28
9	8	19	16	29

It's an interesting task to work out the null solutions. It's much more pleasant if you copy the Visual Basic implementation mentioned below, and it's not too hard if you simply use the hint of Anderson and Feil, and proceed by guessing the pattern of lights for the first row, and then simply proceeding to determine what the pattern must be in the following rows. For instance, for the 4 x 4 case, if you guess that the first row has the form "1 0 0 0", then you are quickly led to the null solution:

        +---+---+---+---+
        | A |   |   |   |
        +---+---+---+---+
        | E | F |   |   |
        +---+---+---+---+
        | I |   | K |   |
        +---+---+---+---+
        |   | N | O | P |
        +---+---+---+---+

from which rotation gives you the other three null solutions.

While we're at it, here are solutions for square boards up to 8x8. Note that the 4x4 and 5x5 solutions are not unique. If a solution on a square board is unique, then it has to be invariant under reflection and 90 degree rotation.

        +---+
        | * |
        +---+

        +---+---+
        | * | * |
        +---+---+
        | * | * |
        +---+---+

        +---+---+---+
        | * |   | * |
        +---+---+---+
        |   | * |   |
        +---+---+---+
        | * |   | * |
        +---+---+---+

        +---+---+---+---+
        |   | * |   |   |
        +---+---+---+---+
        |   |   |   | * |
        +---+---+---+---+
        | * |   |   |   |
        +---+---+---+---+
        |   |   | * |   |
        +---+---+---+---+

        +---+---+---+---+---+
        |   |   |   | * | * |
        +---+---+---+---+---+
        | * | * |   | * | * |
        +---+---+---+---+---+
        | * | * | * |   |   |
        +---+---+---+---+---+
        |   | * | * | * |   |
        +---+---+---+---+---+
        | * |   | * | * |   | 
        +---+---+---+---+---+

        +---+---+---+---+---+---+
        | * |   | * | * |   | * |
        +---+---+---+---+---+---+
        |   | * | * | * | * |   |
        +---+---+---+---+---+---+
        | * | * | * | * | * | * |
        +---+---+---+---+---+---+
        | * | * | * | * | * | * |
        +---+---+---+---+---+---+
        |   | * | * | * | * |   |
        +---+---+---+---+---+---+
        | * |   | * | * |   | * |
        +---+---+---+---+---+---+

        +---+---+---+---+---+---+---+
        | * | * |   | * |   | * | * |
        +---+---+---+---+---+---+---+
        | * | * | * |   | * | * | * |
        +---+---+---+---+---+---+---+
        |   | * | * |   | * | * |   |
        +---+---+---+---+---+---+---+
        | * |   |   | * |   |   | * |
        +---+---+---+---+---+---+---+
        |   | * | * |   | * | * |   |
        +---+---+---+---+---+---+---+
        | * | * | * |   | * | * | * |
        +---+---+---+---+---+---+---+
        | * | * |   | * |   | * | * |
        +---+---+---+---+---+---+---+

        +---+---+---+---+---+---+---+---+
        | * | * |   |   |   |   | * | * |
        +---+---+---+---+---+---+---+---+
        | * | * |   | * | * |   | * | * |
        +---+---+---+---+---+---+---+---+
        |   |   | * | * | * | * |   |   |
        +---+---+---+---+---+---+---+---+
        |   | * | * | * | * | * | * |   |
        +---+---+---+---+---+---+---+---+
        |   | * | * | * | * | * | * |   |
        +---+---+---+---+---+---+---+---+
        |   |   | * | * | * | * |   |   |
        +---+---+---+---+---+---+---+---+
        | * | * |   | * | * |   | * | * |
        +---+---+---+---+---+---+---+---+
        | * | * |   |   |   |   | * | * |
        +---+---+---+---+---+---+---+---+

Puzzle 2: for this problem, we are giving up the detailed information about how the lights are connected. We are left knowing only that the connections are reflexive and symmetric, and that our task is to go from all lights ON to all lights OFF. Lossers gives a short explanation of how to see that this is so. First, we define the obvious matrix A with 1's indicating which switches control which lights. The matrix is symmetric and has 1's on its diagonal.

Now it's equivalent to show that there is some strategy x of button pushing that can go from all lights OFF to all lights ON. But that's just asking if there is a vector x such that

A * x = d,

where d is the vector of all 1's. That is equivalent to asking if d is in the column space of A. And that is equivalent to asking if the "perpendicular space" of A' is contained in the "perpendicular space" of d. In other words, it is enough to show that A'*x=0 implies d'*x=0.

So let x be any vector in the perpendicular space of A'. Then

Sum (1 <= i <= N) x_i * A_i,j = 0

for all j. This implies

Sum ( 1 <= j <= N ) Sum (1 <= i <= N) x_i * A_i,j * x_j = 0,

Now we know that A is symmetric (assumption 2). Therefore, in the preceding sum, let us consider, for distinct i and j every pair of terms

x_i * A_i,j * x_j + x_j * A_j,i * x_i =
( A_i,j + A_j,i ) * x_i * x_j =
2 * A_i,j * x_i * x_j = 0

because we are working in arithmetic module 2! Therefore, all the offdiagonal terms pair up and drop out.

Our sum now only involves the diagonal terms:

Sum (1 <= i <= N) x_i² * A_i,i = 0

Now A_i,i = 1, because the light-switch relationship is reflexive (assumption 1), and d_i = 1 too, so in the sum, we can replace A_i,i by d_i. Moreover, we know that x_i²=x_i, because x_i is either 0 or 1. Therefore, we now have

Sum (1 <= i <= N) x_i * d_i = 0

Hence x is in the perpendicular space of d. This means d is in the column space of A, so a button strategy exists that turns a set of "off" lights all "on", and the same strategy will turn a set of "on" lights all "off".

References:

Alexander Shen,
Mathematical Entertainments: Lights Out,
Mathematical Intelligencer,
Volume 22, Number 13, Summer 2000, pages 20-21.
(a cryptic and hurried discussion)
Marlow Anderson and Todd Feil,
Turning Lights Out with Linear Algebra,
Mathematics Magazine,
Volume 71, Number 4, October 1998, pages 300-303.
(discusses general initial configuration, larger boards, and problems on a torus)
Oscar Martin-Sanches and Cristobal Pareja-Flores have a web site containing a very nice Visual Basic implementation of the puzzle.
(Although they supply a standalone executable, I could not get it to work until I went out and bought my own copy of Visual Basic. Happy Birthday, Bill!)
Uri Peled,
Problem 10197,
American Mathematical Monthly,
Volume 99, Number 2, February 1992, page 162.
O P Lossers,
An All-Ones Problem
A Solution to Problem 10197,
American Mathematical Monthly,
Volume 100, Number 8, October 1993, pages 806-807.
F Galvin,
Solution to Problem 88-8,
Mathematical Intelligencer,
Volume 11, Number 2, 1989, pages 31-32.
K Sutner,
Linear Cellular Automata and the Garden-of-Eden,
Mathematical Intelligencer,
Volume 11, Number 2, 1989, pages 49-53,
(a "Garden of Eden" state is one which can be shown to have no possible predecessor - hence, if it exists, it must have been created ex nihilo!)

Last revised on 23 October 2003.

N	Dimension	N	Dimension	N	Dimension
0		10	0	20	0
1	0	11	6	21	0
2	0	12	0	22
3	0	13	0	23
4	4	14	4	24
5	2	15	0	25
6	0	16	8	26
7	0	17	2	27
8	0	18	0	28
9	8	19	16	29

N	Dimension	N	Dimension	N	Dimension
0		10	0	20	0
1	0	11	6	21	0
2	0	12	0	22
3	0	13	0	23
4	4	14	4	24
5	2	15	0	25
6	0	16	8	26
7	0	17	2	27
8	0	18	0	28
9	8	19	16	29

The Lights Out Puzzle Solution

The Lights Out Puzzle
Solution

N	Dimension	N	Dimension	N	Dimension
0		10	0	20	0
1	0	11	6	21	0
2	0	12	0	22
3	0	13	0	23
4	4	14	4	24
5	2	15	0	25
6	0	16	8	26
7	0	17	2	27
8	0	18	0	28
9	8	19	16	29