Why does the algorithm work?

Any solution to a lights out puzzle will involve pressing some buttons in the first row, some in the second, some in the third etc. We start by pressing all the necessary buttons in the first row. Now we know that we only need to press buttons in the bottom four rows. Next we check to see if there are any lights still on in the top row. If there are, then the only way to turn them off without pressing any more buttons in the top row, is to press the buttons in the second row that are directly beneath the lit lights. We can't press any further buttons in the second row, since that would turn on lights in the top row. So now we can only use the bottom three rows.

If we carry on in this way we will eventually reach the bottom row. If our solution was correct, that is if we pressed the correct buttons on the first row, then after we have pressed the appropriate buttons in the fifth and final row, the puzzle must be solved. So we see that, once we know how to chase the lights to the bottom row, finding a solution amounts to finding the correct combination of lights to press on the top row. This is exactly what the "Light Chasing" algorithm presented above does. It tells us which buttons on the first row we need to press.

When we run through the algorithm for the first time, we end up with one of 7 possible configurations for the last row (or else we've solved the puzzle!). It may seem surprising at first that there are not more possible configurations, but this arises because only 1/4 of all possible lights out puzzles are solvable. The table above then shows you the first row in the solution of this new puzzle. After that, as we've shown above, you only have to chase the lights again to win. Simple.

But why can you press the buttons on the first row at the beginning (as suggested under "Reducing the number of turns" above)? Essentially, this works because the order in which you press the buttons doesn't matter, and because pressing a button twice is the same as not pressing it all. Basically, you may as well press the buttons on the first row first, since order is unimportant. And you might as well combine all the moves from the first and second runs through the algorithm. So there will be some buttons to press on the second row (some from the first run through and some from the second), some on the third, and so on. Any that occur in both runs can be ignored (since pressing a button twice is the same as not pressing it at all) If you think about it for a while, you'll see that this will amount to the same as chasing the lights after the buttons on the first row have been pressed - exactly as we said! The puzzle will then be solved. This is a bit confusing, so I've got another example to show you what I mean.

So how do I find the minimal solution?

The reason that the above approach does not always find the minimal solution is that there are certain combinations of button press that leave the lights unchanged. Click here to see these combinations. This means that if we find a solution, we can always find another one by pressing the buttons in one of the above combinations. Remembering that the order in which we press the buttons is irrelevant, and that pressing a button twice has the same effect as not pressing it all, we can see that we may end up with a shorter solution this way.

We only need to worry about the top row however, so here is how to go about finding the minimal solution to a puzzle in at most 5 attempts.

• Run through the Light Chasing algorithm once to find out which buttons to press in the first row. If you solve the puzzle this first time through you don't need to press any buttons! If this is the minimal solution then that was lucky! If not, skip to the third step
• Press the appropriate buttons in the first row, and run through the Light Chasing algorithm as normal. This may well give you the minimum solution. If not, go on to the next step.
• You now need to try the other combinations of first row button press that will solve your puzzle. These consist of the buttons you already know combined with the top rows of the patterns shown here , always remebering that pressing a button twice has the same effect as not pressing it at all. For example, if you originally needed to press button 1 in the first row, then you would try 3 and 5, then 2,4 and 5, and finally, 1,2,3 and 4. One of these will be the minimal solution when you chase the lights!