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