How to solve Lights Out puzzles

There are 225, or 33,554,432 different possible combinations of lights on the Lights Out board. By no coincidence, if you were to try and solve a puzzle through brute force, there are 33,554,432 different possible solutions you would need to try. If you were to try and solve each puzzle with brute force, hitting one button a second, it would take you 1 year, 120 days, and 5 hours of constant button pressing to test all of the solutions. Remember, you can't stop as soon as you find a solution, because we are usually looking for the shortest solution, so we have to check every possibility.

We can reduce this number in a couple of ways: first of all, there are no solutions of any puzzle that take any longer than 15 moves. There is probably a mathematical reason for this, but I haven't figured it out quite yet. Secondly, some of the solutions are going to be silly. It's obvious that a puzzle with almost all of the lights on isn't going to be solved by only 2 or 3 hits. But even with this, it's an awful lot of possiblities to try for a PalmPilot with limited memory and processor, let alone a human being.

Of course, there must be a way to do this much quicker. While I was playing around with my handheld version, this idea came to me. (I had already solved all 50 of the original puzzles through playing around, though.)

The starting puzzle

This is the sample puzzle we will be trying to solve. Notice the application tells us the shortest possible solution is 15 moves, the hardest possible.

Splitting the board

From now on, you should think of the board in two pieces: the top row of five (shown in red) and the bottom four rows of five (shown in four different shades of green). We will be treating the two sections differently.
The basic move and the second row

This is the move that composes most of this algorithm. Start on the second row, marked in purple (remember, we are going to treat the first row differently). For each of the five buttons, look to see if the button directly above it is lit. For example, the rightmost button of the second row has a lit button directly above it (marked in blue). So we press it.

Continuing the second row

After that first press, the board should look like this. Notice there are two more buttons on this row, still marked in purple, that have lights on above them. So we press both of them.

The third row

The board should look like this. Now, we do the same thing to the third row that we did to the second. There are three lights still lit on the second row, shown in blue, so we press the three lights directly below them on the third row, shown in purple.
 
Go on to the next page
Send comments to .