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.