14 August 2007

The "lights out" puzzle

Remember the puzzle Lights Out? You have a five by five array of buttons with lights under them. When you push one of the buttons, that button and its neighbors to the north, south, east, and west are toggled -- they turn on if they were off, and off if they were on. You start with some random configuration of lights, and the object is to turn them all off.

I remember being very frustrated by the physical version of this puzzle when I first encountered it, because I could never get it to work. It's easy to get most of the lights out, not surprisingly, but hard to get all of them.

It turns out there's a solution, but it's kind of frustrating in that it involves a lookup table. Basically, you look at the first row; whichever lights are on, you press the corresponding lights in the second row. Now, whichever lights are on in the second row, you press the corresponding lights in the third row, and so on. (This is known as "chasing the lights".) Now some lights in the bottom row are on. You then press some apparently randomly selected lights in the top row, according to the table, and repeat; when you get to the bottom this time, all the lights will be off.

This is very inefficient. For one thing, you can see that the order in which the lights are pressed doesn't matter (unlike, say, the Rubik's cube) -- what determines whether a light is on is just its starting position, and the parity of the number of times it and its neighbors have been pressed. Furthermore, if you press a light twice that's the same as not pressing it at all, and this solution in general leads to pressing a lot of lights twice.

In a 9-by-9 version of the puzzle, it turns out that there are only two possibilities for the final row if you do the analogous thing; either all the lights are off (and then you win) or the first, third, fifth, seventh, and ninth lights are on. Then you press the square in the upper right corner and repeat the whole procedure. It looks to me (although I don't have that many 9-by-9 examples of the puzzle, and so can't be sure) that pressing the upper left square toggles the puzzle between these two things, so there ought to be a solution of this form:
- press, or don't press, the top left square.
- proceed by the "chasing the light" method.

In either of these cases one can find a better (although not quite minimal) solution for any starting configuration, by doing the two-pass chasing-the-lights algorithm, noting which buttons one pressed, and then starting from the same original configuration, not pressing those buttons which were pressed twice the first time. For example, today's 9-by-9 lights out at logicgamesonline.com is solved in 58 moves by the crude two-pass method; it turns out that there are ten lights which are pushed on each pass, so eliminating the corresponding 20 presses, one can solve it in 38 moves. (The web site claims there's a 28-move solution, but I'm not bored enough to look for it.)
In the 5-by-5 case there are certain nice-looking patterns which don't do anything. This page describes them as being in the "null space of the adjacency matrix of Lights Out", which kind of makes sense. For more on this, see Mathworld's description of the puzzle; it turns out that the puzzle can be described as the solution of a system of 25 equations with mod 2 coefficients. What I wonder is if there is some way to find the minimal solution, or at least a solution that doesn't involve pressing the same button twice (we might call this an "efficient" solution), that doesn't require actually solving the system of equations, but can be done "by inspection". I suspect there isn't, but I may be wrong.

5 comments:

John Armstrong said...

What I wonder is if there is some way to find the minimal solution, or at least a solution that doesn't involve pressing the same button twice that doesn't require actually solving the system of equations

Not really. The two problems (the puzzle and the linear algebra) are equivalent. Besides, there's really nothing to "solve". Once you find the projector onto the null-space for a given board it's just a matrix multiplication to solve the puzzle.

Isabel said...

John,

I realize why they're equivalent. But I'm wondering, basically, if there's some way to tell someone how to find the minimal solution that doesn't require that they know linea algebra.

John Armstrong said...

I think we've got a semantic mismatch here. I'd say that even if they don't "know linear algebra", if they can solve the puzzle they can solve the equations.

Incidentally, what's your take on the Chinese Room?

Isabel said...

John,

I guess it's a bit hard for me to think of what they're doing here as "solving the system of equations" because this technique allows the solver to solve only the very specialized type of system that arises in the Lights Out puzzle, and no other system. I think I would need the apparatus to be capable of solving some more general class of systems before I would say that the person using it is really solving the equations.

As for the Chinese room, I don't think the person inside the Chinese room knows Chinese, but I think the combination of the room plus the person inside knows Chinese. (Similarly, I would be willing to say that the combination of the person holding the Lights Out puzzle and the puzzle itself knows how to solve a certain class of systems of equations.)

Grantis Mantis said...

My linear programming teacher presented us with a similar problem, except with each button press, all the lights in the row and the column of the button press are toggled. In order to solve this problem, each cell was given its own constraint depending on whether or not it was pre-lit, after which, as you mention, you can simply select the cells in any order.

However, I also wonder if there is a simple visual cue that doesn't require integer programming?