The mathematics of Lights Out

JaneFairfax · 2007-05-10 22:06:20

You have a square or rectangular grid of lights, some of which are on and some off. If you press any light, you toggle its state and that of any adjacent light to its left, right, top and bottom. (Diagonal neighbours are not affected.) The idea of the puzzle is to turn off all the lights. So?

Well, if a light is on, it must be toggled an odd number of times to be turned off. If a light is off, it must be toggled an even number of times (including not being toggled at all) for it to remain off. A successful operation is therefore a sequence of presses that toggles all the on lights an odd number of times and all the off lights an even number of times.

Two points may be noted:

The order in which the lights are pressed does not matter. The end result of pressing a given set of lights is always that each light has been toggled a certain number of times. (For example, suppose the lights are numbered #1#25 left to right from top to bottom. Pressing #3, #8 and #14 will toggle #2, #4, #7, #14, #15, #19 exactly once and #3, #8, #9, #13 exactly twice. No matter in what order you press #3, #8 and #14, all the affected lights will be toggled the same way in the end.)

Each light needs to be pressed no more than once. Note that pressing a light twice is equivalent to not pressing it at all (indeed pressing a light an even number of times is equivalent to not touching it while pressing it an odd number of times is equivalent to doing so just once). Since the order in which the lights are pressed does not matter, a sequence in which one light is pressed twice is equivalent to the same sequence with those two presses removed. Hence, the most efficient method of solving any puzzle (one that uses the minimum number of moves) is one in which no light is pressed more than once.

Well, thats my theory. I hope its correct, as Ive actually edited the two Wikipedia articles on Lights Out to contribute this insight of mine!

http://en.wikipedia.org/wiki/Lights_Out_%28game%29
http://en.wikipedia.org/wiki/Lights_Out_%28puzzle%29

Then again, since anyone can edit wiki pages, it wouldnt really be a disaster if I am wrong. If my theory is incorrect, someone can always edit it out, and no harm will be done except to my pride and vanity.

Last edited by JaneFairfax (2007-05-11 11:04:32)

Ricky · 2007-05-11 04:13:22

Note that pressing a light twice is equivalent to not pressing it at all (indeed pressing a light an even number of times is equivalent to not touching it while pressing it an odd number of times is equivalent to doing so just once).

I don't think this is so. Pressing a light, then an adjacent light, then that light again will change the puzzle. So it is not the equivalent of just pressing it twice in a row.

JaneFairfax · 2007-05-11 05:43:20

Okay, lets see. Suppose we press the light with co-ordinates (m,n). Then we press an adjacent light, say (m+1,n), and then the light (m,n) again.

Pressing (m,n) toggles the following lights: (m,n), (m+1,n), (m,n+1), (m−1,n), (m,n−1)

Pressing (m+1,n) toggles the following lights: (m,n), (m+1,n), (m+2,n), (m+1,n+1), (m+1,n−1)

Finally pressing (m,n) again toggles the same first five lights.

The upshot of all this is that 8 different lights have been toggled. Of these, (m,n+1), (m−1,n) and (m,n−1) have been toggled exactly twice, so there is no change in their state. Of the others, (m,n) and (m+1,n) have been toggled exactly three times while the rest have been toggled exactly once so these have changed state.

In other words, the lights that have changed state are (m,n), (m+1,n), (m+2,n), (m+1,n+1), (m+1,n−1) which are precisely those lights that would be toggled by pressing just the adjacent light (m+1,n) alone.

Last edited by JaneFairfax (2007-05-11 05:48:41)

mathsyperson · 2007-05-11 06:53:48

I would agree with both of those statements. With that in mind, it's possible to easily optimise some solutions.

The wikipedia page gives a very sloppy way of solving a board.
Basically, eliminate all rows except the bottom one by pressing all lights directly below 'on' lights and working your way downwards. Then look at a table and press buttons according to what lights are left on in that row.

The worst part is that even then you may not be done, and you'd have to repeat the process until you finished. It's very possible that you might take a far higher number of moves that you need to. But to improve it, you'd just write down all the moves of the 'bad' solution, cross out repeating squares in pairs, and there you have a better solution. Possibly still not the best one, but certainly an improvement.

That's an interesting point actually. Can Lights Out boards have more than one solution that doesn't involve pressing a light twice?

luca-deltodesco · 2007-05-11 07:21:26

my intution says yes, treating it as a long list of simultaenous equations that have to be satisfied, there are probably most deffinately not a single unique solution

JaneFairfax · 2007-05-11 11:54:47

mathsyperson wrote:

That's an interesting point actually. Can Lights Out boards have more than one solution that doesn't involve pressing a light twice?

Yes indeedy, they can. Consider the following setup:

You can do it the short way by pressing the four corner lights. Or you can do it the long way by pressing all the lights on the edge plus the second-from-left, second-from-right, second-from-top and second-from-bottom middle lights. Neither solution involves pressing a light more than once. If you dont believe it, you can try it yourself here: http://www.guzer.com/games/switchit.php

PS: There is a very interesting corollary to the above. Notice that the short solution is actually contained in the long solution. This means that if the lights are numbered #1#25 left to right from top to bottom, then pressing the following lights (in any order) will leave the entire board unchanged: #2 #3 #4 #6 #8 #10 #11 #12 #14 #15 #16 #18 #20 #22 #23 #24. (Thats all the even-numbered lights plus the midpoints of the four edges of the grid.)

Last edited by JaneFairfax (2007-05-11 20:47:22)

JaneFairfax · 2007-05-11 20:21:34

And after a good nights sleep, Ive found another example:

Short solution: Press #3 #11 #15 #23 (i.e. the midpoints of the edges of the grid)
Long solution: Press all the even-numbered lights

Again neither solution involves pressing a light more than once. This time, however, neither solution is contained in the other! This makes the example wholly non-trivial.

Heres the proof of why the long solution works. Since the even-numbered lights are all either at least two lights apart or diagonally separated, pressing an even-numbered light has no effect on any even-numbered light other than itself. Of the odd-numbered lights, only the ones at the midpoints of the grid edges are adjacent to an odd number of even-numbered lights. All the other odd-numbered lights are adjacent to an even number of even-numbered lights. Hence pressing all the even-numbered lights will change the state all the even-numbered lights plus #3, #11, #15 and #23, and leave the state of all the other lights unchanged in other words, it should turn off all the lights above.

mathsyperson · 2007-05-11 23:30:06

Excellent work! So, as well as crossing out pairs, it's also possible to improve solutions by making a list of sets of buttons that don't affect the board overall and then crossing out any of those that appear. You might not get to use that method as often, but when you do it would improve the solution by a *lot*.

So now that we know that it's possible to have solutions that aren't contained in each other, the next logical question would be whether or not you can have more than one optimal solution.

JaneFairfax · 2007-05-12 00:20:05

Yes, lets work on it. Meanwhile. I believe we can use some mathematical tools to help us in our analysis.

Thus, using this simpler notation, my first board above can be represented by the matrix

and the second board above by

The two statements in my first post can thus be formally stated as theorems.

Theorem 1:

(NB: Ive stated the theorem for only two multipliers; mathematical induction should see to it that it works for any finite number of multipliers.)

Theorem 2:

JaneFairfax · 2007-05-12 00:50:05

Theorem 3:

where + is matrix addition. And Theorem 3 proves the other two theorems! Theorem 1 is proved by the fact that matrix addition is commutative and associative, while Theorem 2 is proved by the fact that since the matrices in

are over a two-element field, L + L = 0 for all L ∈ .

JaneFairfax · 2007-05-12 01:17:07

Conjecture:
Let us call the matrix P[sup](m,n)[/sup] in Theorem 3 a pressing matrix (as it represents the pressing of a light). Then this conjecture claims that every board setup L is the sum of finitely many pressing matrices.

Pressing matrices would then thus the fundamental building blocks of the game of Lights Out. It would mean that starting with the zero matrix (the board with all lights off), we could arrive at any arbitrary board configuration by executing a finite series of presses which would mean (working in reverse) that every board setup in Lights Out can be solved.

PS: In the 5×5 case, there are only 25 pressing matrices. Therefore the number of finite combinations of distinct pressing matrices is only finite. It should thus be straightforward to check if between them they yield all the 2[sup]25[/sup] possible board configurations you just need a good program, or a lot of time on your hand.

Last edited by JaneFairfax (2007-05-12 02:06:00)

mathsyperson · 2007-05-12 03:27:26

Wait a minute. There are 2[sup]25[/sup] board configurations, and there are also 2[sup]25[/sup] non-repeating combinations of buttons.

But in your 2nd example above, you showed that there are distinct non-repeating combinations that change the board in the same way. So then, because the number of configurations is the same as the number of combinations, that must mean that there are some boards that can't be solved. I'd always assumed the opposite.

JaneFairfax · 2007-05-12 04:31:00

Oops, I didnt spot that.

mathsyperson · 2007-05-12 12:33:31

I investigated this a bit further. From the Wikipedia article, every board can be reduced to just one lit line, and then from there you try to do stuff to make the last line go out.

Labelling the last line ABCDE, there are 5 different operations that you can do that affect nothing but the last line. These are BCE, ABC, ABDE, CDE and ACD.

Clearly, all of the board combinations can be reduced to one of the 32 boards that only involve the last line, and from there it's a question of which of those can be solved. Perhaps surprisingly, the only solvable boards other than the ones that are solved by just one of those operations are AE and BD (and of course, the one without any lights).

From there, a bit more poking around reveals that there are 3 sets of unsolvable boards such that each element can be transformed into another element in the set but no other.

Set 1:
{A, ABCE, ABD, ACDE, BC, BDE, CD, E}

Set 2:
{ABCD, ABE, AC, ADE, B, BCDE, CE, D}

Set 3:
{AB, ABCDE, ACE, AD, BCD, BE, C, DE}

Interestingly, each of those sets is just the solvable set but with A, B and C respectively added to each element.

A useful consequence of this is that if you get a randomly generated Lights Out board, then reducing it to one light on the edge of the board is proof that it can't be solved.

mathsyperson · 2007-09-21 03:38:16

Bump.

Can some very clever person extend on what we already know and apply it to Lights Out 3D?

I tried briefly, but it seems a lot more complicated.

JaneFairfax · 2007-09-21 07:30:56

I think the basic concepts are the same, only you work with 3D matrices instead of 2D matrices.

Math Is Fun Forum

#1 2007-05-10 22:06:20

The mathematics of Lights Out

#2 2007-05-11 04:13:22

Re: The mathematics of Lights Out

#3 2007-05-11 05:43:20

Re: The mathematics of Lights Out

#4 2007-05-11 06:53:48

Re: The mathematics of Lights Out

#5 2007-05-11 07:21:26

Re: The mathematics of Lights Out

#6 2007-05-11 11:54:47

Re: The mathematics of Lights Out

#7 2007-05-11 20:21:34

Re: The mathematics of Lights Out

#8 2007-05-11 23:30:06

Re: The mathematics of Lights Out

#9 2007-05-12 00:20:05

Re: The mathematics of Lights Out

#10 2007-05-12 00:50:05

Re: The mathematics of Lights Out

#11 2007-05-12 01:17:07

Re: The mathematics of Lights Out

#12 2007-05-12 03:27:26

Re: The mathematics of Lights Out

#13 2007-05-12 04:31:00

Re: The mathematics of Lights Out

#14 2007-05-12 12:33:31

Re: The mathematics of Lights Out

#15 2007-09-21 03:38:16

Re: The mathematics of Lights Out

#16 2007-09-21 07:30:56

Re: The mathematics of Lights Out

Board footer