From: Carsten Haese Newsgroups: sci.math Subject: Mathematical Puzzle: Turn all the lights out Date: Thu, 12 Feb 1998 11:34:51 +0100 Abstract -------- This paper is concerned with a mathematical solution of an electronic puzzle game called "Lights Out". "Lights Out" is a commercially available product, so to protect myself I expressly state that this paper is not intended to influence you in any way to buy or not to buy "Lights Out". My only intention is to present a result of entertaining mathematical research and to share it with anyone who is interested in it. This paper is dedicated to Tracy, who had introduced me to "Lights Out". The Puzzle ---------- The game is a grid of 5 by 5 buttons that can light up. Pressing a button will switch its light around, but it will also switch 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 little moves (pressing a button is one move) as possible. My 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? If you want to think about these questions on your own, stop reading here. Further below you will find my solution of the problem (which needn't be the only or most elegant one). I'll be happy about any feedback, comments or corrections by eMail to chaese@physik.tu-berlin.de The solution ------------ My 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 0s and 1s, i.e. by an element of {0, 1}^25. To represent the way how pressing a button affects the pattern of lights, I define an addition operator on the set {0, 1} =: Z2 by 0+0 := 0 =: 1+1 and 0+1 := 1 =: 1+0. 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 Z2^25 in a natural way. Of course, to take advantage of this addition in Z2^25, I will want to represent the effect of pressing a button as an element of Z2^25. 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 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 Z2^25. Let a_i in Z2^25 (i=1,..,25) be the button action that is caused by pressing the i-th button. For example, (1,1,1,0,0, (0,0,0,0,0, 0,1,0,0,0, 0,0,0,0,0, a_2 = 0,0,0,0,0, and a_19 = 0,0,0,1,0, . 0,0,0,0,0, 0,0,1,1,1, 0,0,0,0,0) 0,0,0,1,0) For clarity I write these 25-tuples over 5 lines so that you can see where they are coming from, but there is no mathematical meaning in writing them like that. I can now start the first attempt at writing down an equation that will solve a lights out puzzle. Let y in Z2^25 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_21 + y. Then I might press the 15th button, resulting in a_15 + (a_21 + 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 Z2^25 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 Z2^25), 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*(v_1,..,v_25) := (s*v1,..,s*v_25), (Z2^25,+,*) is a vector space over the field Z2. Now, the above equation can be equivalently rewritten as x_1*a_1 + ... + x_25*a_25 + y = (0,0,...,0) with some x=(x_1,...,x_25) in Z2^25. By adding y to both sides of this equation I get x_1*a_1 + ... + x_25*a_25 = 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 [A I O O O] [1 1 0 0 0] [I A I O O] [1 1 1 0 0] M = [O I A I O] with A = [0 1 1 1 0] , I = identity matrix, [O O I A I] [0 0 1 1 1] [O O O I A] [0 0 0 1 1] and O = zero matrix. 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 in Z2^25 will make the light pattern y in Z2^25 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 Z2^25) 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. If you are interested in it, I can send it to you, as well as the source code of the solver program. The main results are: * dim range M = 23, dim kern M = 2. Therefore there are puzzles that can't be solved. Those that can be solved have 4 different solutions because (x_24, x_25) can be chosen arbitrarily from Z2^2. * Examining the last two lines in the final matrix yields a criterion for the existence of a solution. With the vectors (1,0,1,0,1, (1,1,0,1,1, 1,0,1,0,1, 0,0,0,0,0, k_1 = 0,0,0,0,0, and k_2 = 1,1,0,1,1, 1,0,1,0,1, 0,0,0,0,0, 1,0,1,0,1) 1,1,0,1,1) the criterion can be written as 0 = = , where < . , . > denotes the canonical scalar product in Z2^25. It turns out that {k_1, k_2} is a basis of kern 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 kern 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. The main questions have been answered, so this concludes the paper. Thank you for reading this far and I hope you enjoyed it. Like I said before, I'll appreciate any comments on this paper. Please email them to chaese@physik.tu-berlin.de - Carsten Haese ============================================================================== From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: Mathematical Puzzle: Turn all the lights out Date: 14 Feb 1998 05:11:17 GMT Carsten Haese wrote: >The game is a grid of 5 by 5 buttons that can light up. Pressing a button >will switch its light around, but it will also switch 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 little moves (pressing a >button is one move) as possible. You could play the same game on an m x n grid. The same analysis applies: you are testing to see whether a given element of (Z/2)^(m*n) lies in the subgroup generated by a certain collection of m*n generators. Rather than simply ask whether or not that subgroup is the whole of the matrix group (Z/2)^(m*n), one can ask for the codimension of that subgroup (it's actually a sub-vectorspace over Z/2). It's trivial to compute that codimension for specific (m,n) (e.g. when m=n the codimension is 0,0,0,2,2,0,0,0 for the first few m=n=1,2,3,...8). Question: Can one predict this codimension as a function of m and n? Even better: I was recently asked nearly the same question in email by someone who wanted to work integrally. What are the invariants of the finitely-generated abelian group G/H, where G is the free group Z^(m*n) and H is the subgroup generated by the m*n generators M(i,j) ? (Here M(i,j)_{k,l} = 0 unless |i-k|<=1 and j=l, or i=k and |j-l| <=1; M(i,j)_{k,l} = 1 in those cases.) I can calculated the invariants for many specific m and n, but I don't see the pattern (in particular, there are unexpectedly large primes in the torsion). I did not find rank > 2 in the cases I tried, and I suppose I could conjecture the rank in general, but I wouldn't have much confidence in the conjectures. dave ============================================================================== From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: Mathematical Puzzle: Turn all the lights out Date: 14 Feb 1998 06:34:16 GMT Dave Rusin wrote: >You could play the same game on an m x n grid. The same analysis applies: ... >It's trivial to compute that codimension for specific (m,n) (e.g. when >m=n the codimension is 0,0,0,2,2,0,0,0 for the first few m=n=1,2,3,...8). Oopsie. That's the free rank. Here are the free ranks for all one-digit (m,n): 0,1,0,0,1,0,0,1,0 1,0,1,0,1,0,1,0,1 0,1,0,0,1,0,0,1,0 0,0,0,2,0,0,0,0,2 1,1,1,0,2,0,1,1,1 0,0,0,0,0,0,0,0,0 <- this row of zeros continues for several more terms (m=6) 0,1,0,0,1,0,0,1,0 1,0,1,0,1,0,1,0,1 0,1,0,2,1,0,0,1,2 The codimension of the corresponding Z/2 - vectorspace is larger by the 2-rank of G/H; these codimensions are 0, 1, 0, 0, 1, 0, 0, 1, 0 0, 2, 0, 1, 0, 2, 0, 1 0, 0, 3, 0, 0, 2, 0 4, 0, 0, 0, 0, 4 2, 0, 4, 1, 1 0, 0, 6, 0 0, 2, 0 0, 1 8 when m <= n <= 9, and of course the table is symmetric for n < m. Patterns? Proofs? Are we ready for torsion? dave