## How to solve Lights Out puzzlesThere are 2^{25}, 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.)
| |||||||||||||||||||||

Send comments to
. |