The Lights Out Puzzle

A simple puzzle provides an interesting application of mathematical analysis and functional programming with Mathematica.

by Robert Cowen and
John W. Kennedy

A puzzle, called Lights Out, provides an excellent opportunity to use Mathematica's functional programming style to easily explore mathematically interesting questions.  A rectangular board is constructed from squares. (The original puzzle consists of a 5-by-5 board.) Squares can be in one of two states: light or dark. If a square is touched, its state reverses and so does the state of each of its neighboring squares (that is, those squares with which it shares an edge). The puzzle is to touch squares of a board, which are initially all lit, so that all squares become dark. If there is a solution to the puzzle, it is natural to ask if there is more than one solution and, if so, what is a minimal solution—one with fewest squares touched.  In fact it is convenient  to consider the problem on graphs (defined below), especially since Mathematica, in its DiscreteMath Combinatorica package, has many defined graph functions. The computational aspect of the problem of finding solutions, as the board size increases, may at first appear rather daunting; however, in the next section we show that it reduces to finding solutions of linear equations over the two element field {0,1}—a very tractable problem.

The Algebraic Connection

A casual examination of Lights Out puzzles leads to interesting observations on which a much better understanding of the nature of the problem depends. Changing the state of a square an even number of times is equivalent to not changing it at all; changing the state an odd number of times is equivalent to changing it only once (its state is reversed). Furthermore, the order in which we touch various squares is unimportant—it is only the number of times we touch a square that matters. These facts imply that, if the puzzle can be solved at all, it can be solved by touching some squares exactly once and the others not at all. Thus, a solution consists of indicating which squares to touch once.

We set up a local equation for each square on the board that must be satisfied by any solution. In any solution to the Lights Out puzzle, the total number of times each square and all its neighbors are touched must be odd if that square is ultimately to be darkened. For an m-by-n board, number the squares i = 1, 2, …, mn, and let (Subscript[x, i]) represent the number of times that square i is touched. As mentioned above, we can assume (Subscript[x, i]) is either 0 or 1. Then, the number of times a square i changes state is represented by summing (Subscript[x, i]) and the variables, (Subscript[x, j]), for the squares  j that are adjacent to i. This will result in a change of state for square i if and only if the sum is odd—that is, equal to 1 modulo 2. Consequently, the local equation for each square consists of setting this sum (over the square and its neighbors) equal to 1 mod 2.

For the 3-by-3 board, with numbered squares, depicted in the following figure, the set of local equations to be solved, mod 2, is  listed below.

({{1, 2, 3}, {4, 5, 6}, {7, 8, 9}})

(Subscript[x, 1 ])+ (Subscript[x, 2])+ (Subscript[x, 4  ])= 1
(Subscript[x, 2 ])+ (Subscript[x, 1])+ (Subscript[x, 3 ])+ (Subscript[x, 5 ])= 1
(Subscript[x, 3 ])+ (Subscript[x, 2 ])+ (Subscript[x, 6 ])= 1
(Subscript[x, 4 ])+ (Subscript[x, 1 ])+ (Subscript[x, 5 ])+ (Subscript[x, 7 ])= 1
(Subscript[x, 5]) + (Subscript[x, 2 ])+ (Subscript[x, 4 ])+ (Subscript[x, 6 ])+ (Subscript[x, 8 ])= 1
(Subscript[x, 6]) + (Subscript[x, 3 ])+ (Subscript[x, 5 ])+ (Subscript[x, 9 ])= 1
(Subscript[x, 7 ])+ (Subscript[x, 4 ])+ (Subscript[x, 8 ])= 1
(Subscript[x, 8 ])+ (Subscript[x, 5 ])+ (Subscript[x, 7 ])+ (Subscript[x, 9 ])= 1
(Subscript[x, 9 ])+ (Subscript[x, 6 ])+ (Subscript[x, 8 ])= 1

Since we require solutions to the system of equations modulo 2 we append the statement Modulus==2, to one of the equations.

Solve[{(Subscript[x, 1])+(Subscript[x, 2])+(Subscript[x, 4])==1&&Modulus == 2,(Subscript[x, 2])+(Subscript[x, 1])+(Subscript[x, 3])+(Subscript[x, 5])==1,(Subscript[x, 3])+(Subscript[x, 2])+(Subscript[x, 6])==1,(Subscript[x, 4])+(Subscript[x, 1])+(Subscript[x, 5])+(Subscript[x, 7])==1,(Subscript[x, 5])+(Subscript[x, 2])+(Subscript[x, 4])+(Subscript[x, 6])+(Subscript[x, 8])==1,(Subscript[x, 6])+(Subscript[x, 3])+(Subscript[x, 5])+(Subscript[x, 9])==1,(Subscript[x, 7])+(Subscript[x, 4])+(Subscript[x, 8])==1,(Subscript[x, 8])+(Subscript[x, 5])+(Subscript[x, 7])+(Subscript[x, 9])==1,(Subscript[x, 9])+(Subscript[x, 6])+(Subscript[x, 8])==1}]

The solution tells us that to darken all squares on the 3-by-3 board we need only touch squares 1, 3, 5, 7, and 9. Of course, the difficulty with this method is having to type all the local equations. In the next section we show how this can be avoided by using Mathematica's facility in handling graph structures.

The Graph Connection

A graph is a non-empty set of "point" objects, called vertices, together with a set of "line" objects, called edges, each of which joins some pair of the vertices. If two vertices are joined by an edge they are said to be adjacent and are called neighbors. The puzzle can be played on any graphical "board" with vertices in one of two states, light or dark, and the rule is that when any vertex is touched, that vertex and all of its neighbors change their states. The rectangular boards for the Lights Out puzzle can be viewed as graphs, with a vertex representing each square of the board, and each edge indicating that the vertices it connects belong to adjacent squares on  the board. Graphs of this type are often called grid graphs. We can use the Mathematica command GridGraph[m,n] to enter the m-by-n grid graph; however, it is first necessary to load the standard package DiscreteMath`Combinatorica`.

Needs["DiscreteMath`Combinatorica`"]

The 5-by-5 grid graph corresponds to the original board in the Lights Out problem; to display it we enter

ShowGraph[GridGraph[5, 5]]

Note that the squares in the picture do not correspond to squares on the board; the board squares are represented by the vertices (dots).

One convient way to represent a graph is by means of a matrix called the adjacency matrix of the graph. If there are n vertices, numbered 1 to n, the adjacency matrix is an n- by-n matrix with the entry in the i-th row,  j-th column equal to 1 if the i-th vertex is adjacent to the j-th vertex; if not this entry is 0. Mathematica gives the adjacency matrix as the first of two entries in its representation of a graph when a graph is entered; the second entry describes an embedding of the vertices in the plane. It is the first entry, the adjacency matrix, that is of interest to us here. Thus, the adjacency matrix for the 3-by-3 puzzle is obtained by

ToAdjacencyMatrix[GridGraph[3, 3]] // MatrixForm

Now this is almost the same as the coefficient matrix of the set of equations we used to solve the 3-by-3 board Lights Out puzzle. It lacks only the 1s on the main diagonal, to indicate that touching a square also contributes to its own change of state. Thus to get the coefficient matrix we enter,

ToAdjacencyMatrix[GridGraph[3, 3]] + IdentityMatrix[3*3] // 
      MatrixForm

This is the coefficient matrix for the left side of the set of equations; the right side consists of a vector of 1s. Mathematica can solve the system with just this information, using the built function LinearSolve, and indicating that we are solving it mod 2. We further partition the solution into three rows corresponding to the rows of the puzzle.

mat = 
        ToAdjacencyMatrix[GridGraph[3, 3]] + IdentityMatrix[3*3];
Partition[LinearSolve[mat, Table[1, {9}], Modulus -> 2], 
      3]

Again, the entries indicate how many times to touch the corresponding square in order to solve this Lights Out puzzle.

More generally, we can now search for a solution for the m-by-n board as follows.

\(LightsOut[m_, n_] := 
      Module[{mat}, 
        mat = \((ToAdjacencyMatrix[GridGraph[m, n]] + IdentityMatrix[m*n])\); 
        Partition[LinearSolve[mat, Table[1, {m*n}], Modulus -> 2], 
          m]
	]\)

We next look for solutions on a 6-by-5 board.

LightsOut[6, 5]

We can get a little fancier and actually have Mathematica draw the board and put an X on each square that should be touched. The resulting patterns are really quite nice.

drawsol[m_, n_] := 
      GridBox[LightsOut[m, n] /. {1 -> "X", 0 -> ""}, 
          RowLines -> True, ColumnLines -> True, 
          GridFrame -> True] // DisplayForm

drawsol[6, 5]

Larger puzzles are also easily solved; for example,

drawsol[14, 11]

The reader can easily display more solutions; we find them rather attractive and think that they would make admirable quilting patterns. 

LinearSolve only gives one solution. There may be more. We show how to find all solutions later. First, in the next section, we describe how to tell if the solution is unique.

Unique Solutions

LinearSolve finds one solution if there is one; otherwise it reports that no solution exists. One way to decide if there is a unique solution is to use Mathematica's determinant function, Det. It is a theorem of linear algebra that a system of linear equations has a unique solution if and only if the determinant of the coefficient matrix is not zero. Since we are solving the system mod 2 we need to compute the determinant mod 2. For example, for the 3-by-3 board considered above,

mat = 
        ToAdjacencyMatrix[GridGraph[3, 3]] + 
          IdentityMatrix[3*3];

Det[mat, Modulus -> 2]

Thus we are assured that the solution to the 3-by-3 board is unique. In the same way, we tested the square boards, n-by-n,  up to n = 20, for solution uniqueness and found that there are unique solutions for n = 2, 3, 6, 7, 8, 10, 12, 13, 15, 18, and 20. Unfortunately there seems to be no way  to determine which boards have unique solutions without such lengthy computations. In particular, we have not found any patterns relating to uniquenss of solution; however, we encourage interested readers to investigate this further.

All Solutions

It has been proved by several authors that there always is at least one solution for any graphical board (see for example References [1], [3], and [5]). We began to believe that this rather remarkable result was true through our investigation of the problem with Mathematica. LinearSolve only finds one solution.  To find all solutions, we recall from linear algebra that if you take a particular solution (obtained, say, from LinearSolve) and add any linear combination of basis vectors for the nullspace, you still have a solution, and, in fact, all solutions are obtainable in this way. We must of course perform all the calculations Modulo 2. To replace ordinary addition by addition, mod 2, we introduce boolesum.

\(\(\(boolesum[x_, y_] := 
        If[\((x == 0 && y == 0)\) || \((x == 1 && y == 1)\), 0, 1];\)\(
\)
    \)\)

To apply boolesum to more arguments, we use the operator Fold. For example if we want to apply it to {1,1,0,1}, we do the following.

Fold[boolesum, 1, {1, 0, 1}]

In order to enable boolesum to work "properly" with lists (that is, operate "coordinatewise")  we inform Mathematica that the function is Listable.

SetAttributes[boolesum, Listable];

We use LinearSolve to obtain a particular solution. To generate the nullspace basis, we use Mathematica's NullSpace  (adding Modulus->2  to its arguments).  To form linear combinations of these basis vectors, since the coefficients are either 1 (include the vector) or 0 (exclude the vector),  we simply add (mod 2) each subset of basis vectors to the particular solution obtained with LinearSolve. We use Subsets to form the subsets, and boolesum together with Fold to add them up. Also we partition the solutions into rows.

\(LightsOutAll[m_, n_] := 
      Module[{x, mat, l}, 
        mat = \((ToAdjacencyMatrix[GridGraph[m, n]] + IdentityMatrix[m*n])\); 
        x = LinearSolve[mat, Table[1, {m*n}], Modulus -> 2]; 
		l = 
          Subsets[NullSpace[mat, Modulus -> 2]]; 
		Table[
          Partition[Fold[boolesum, x, l[\([i]\)]], m], {i, 
            Length[l]}]
	]\)

This allows us to construct the unique 3-by-3 solution.

LightsOutAll[3, 3]

Similarly, we get all 16 of the 4-by-4 solutions.

LightsOutAll[4, 4]

We can even define an operator that draws the k-th solution for the m-by-n board; we then use it to give the sixth solution of the 11-by-11 board.

solveboard[m_, n_, k_] := 
      GridBox[LightsOutAll[m, n][[k]] /. {1 -> "X", 
              0 -> ""}, RowLines -> True, 
          ColumnLines -> True, GridFrame -> True] // 
        DisplayForm

solveboard[11, 11, 3]

Of special interest are "minimal" solutions—those with the least number of "touched" squares. To pick out minimal solutions we first flatten each solution so that it consists of a single sequence of 0s and 1s and add the terms in order to count the number of 1s; those solutions with the smallest total are minimal solutions. The following sequence of defined functions leads to the function MinSol, which will pick out a minimal solution. We use the 4-by-4 board to illustrate. We then add a function, DrawMinSol, that draws minimal solutions for rectangular boards; and we use it to draw a minimal solution for the 4-by-4,  5-by-5 (since this was the original Lights Out board), 6-by-6 (for comparison with a variant of the problem given at the end of this paper), and 9-by-9 (for a larger example) boards.

total[x_] := Plus @@ Flatten[x];
SmallestTotal[x_] := 
        Min[Table[total[x[[k]]], {k, Length[x]}]];

SmallestTotal[LightsOutAll[4, 4]]

MinSol[x_] := 
        Select[x, total[#] == SmallestTotal[x] &, 1];

MinSol[LightsOutAll[4, 4]]

DrawMinSol[x_] := 
      GridBox[Flatten[MinSol[LightsOutAll[x, x]], 1] /. {1 -> "X", 
              0 -> ""}, RowLines -> True, 
          ColumnLines -> True, GridFrame -> True] // 
        DisplayForm

DrawMinSol[4]

DrawMinSol[5]

DrawMinSol[6]

DrawMinSol[9]

Open Problems

Many open questions remain concerning the Lights Out problem on boards (grid graphs) and graphs in general. Here are a few that we feel are espeicially worthy of investigation with  Mathematica. 

Write a Mathematica program to find all minimal solutions and use it to investigate which graphs have unique minimal solutions. 

Can formulas for the number of touched squares in a minimal solution be obtained for grid graphs or various classes of grid graphs?  If complete accuracy is not obtainable, can informative upper and lower bounds be provided? (The same questions can be asked for classes of graphs that are not grid graphs.) See Reference [2] for some partial results.

If we vary the starting condition so that some vertices start in the light state and some in the dark state, but still want to extinguish all squares, it is not always possible to find a solution. Which starting configurations have solutions for particular graphs or classes of graphs? A 5-by-5 version of Lights Out, which allows the player to select any starting configuration, can be played online (see Reference [6]); in addition, a solution, if one exists, will be provided if desired. If there is no solution, what is the maximum number of squares that can be extinguished? This maximization problem is studied in Reference [4]. 

Finally, suppose we modify the Lights Out rule so that touching a vertex on a graphical board changes only the state of the neighbors of that vertex—but not the state of the vertex itself. Then, the only change needed in the treatment we presented is that no longer do we add the identity matrix in setting up the coefficient matrix for the system of linear equations to be solved. With this modification, all the functions above can be employed. In the modified problem, not every rectangular board (or every graph for that matter) has a solution. For example, the 5-by-5 board lacks a solution.  However, the 6-by-6 board has solutions. We show a minimal solution for the 6-by-6 board in this variant of the puzzle for comparison with the "regular" Lights Out minimal solution that we gave above for this grid graph.

Notice how many fewer squares need to be "touched" in the 6-by-6 case for this variant of the problem.
Exactly which grid graphs do have solutions for this modification is not known. Again, the reader is encouraged to investigate using Mathematica.

References

[1] Y. Caro; Simple proofs to three parity theorems. Ars Combinatorica, 42, 175–180 (1996). 

[2] M.M. Conlon, M. Falidas, M.J. Forde, J.W. Kennedy, S. McIlwaine, and J. Stern; Inversion numbers of graphs. Graph Theory Notes of New York, XXXVII, 42–48 (1999). 

[3] R. Cowen, S.H. Hechler, J.W. Kennedy, and A. Ryba; Inversion and neighborhood inversion in graphs. Graph Theory Notes of New York, XXXVII, 37–41 (1999). 

[4] J. Goldwasser and W. Klostermeyer; Maximization versions of "Lights Out" games in grids and graphs, Congressus Numerantium, 126, 99-111.

[5] K. Sutter; Linear cellular automata and the Garden-of-Eden, The Mathematical Intelligencer, 11, 49–53 (1989).

[6] http://www.whitman.edu/offices_departments/mathematics/lights_out/

ABOUT THE AUTHORS

Robert Cowen and John W. Kennedy teach mathematics at Queens College of The City University of New York where they give a course in mathematical algorithms that meets in the Department’s Mathematica lab. They are writing a book, Discovering Mathematics with Mathematica, based on the course. This article is adapted from a chapter in the book. 

cowen@forbin.qc.edu;     

jkennedy@nyas.org

ELECTRONIC SUBSCRIPTIONS

Included in the distribution for each electronic subscription is the file lightsOut.nb, containing Mathematica code for the material described in this article.