LightsOut@Home
At one time I really enjoyed Lights Out. Now I don't, because this program took all the fun out of it. This is an old program I wrote a long time ago (it's DOS based) in order to solve Lights Out.
For those unfamiliar with the game, it is played on a five by five grid of lights that double as push buttons. You are presented with an initial pattern of lights, and you must turn them all off. When you push a light, it toggles. If it was on, you've turned it off. If it was off, it turns on. The same happens to the lights above, below, left and right of the light you pushed. If you see five lights in the shape of a "plus sign" on the board, press the middle button and all go out. And so forth. Notice that if you push the same button twice, the toggle is toggled. In fact, pushing a button 2, 4, 6, etc, times is the same as not pushing it at all. Any odd number is the same as pushing a button once. The game knows this, too. Even if you solve the puzzle, the game does not allow you to pass if you pushed a spot more than once. There is some flexibility on the lower levels, but the rule is rigorously enforced on the higher levels.
Warning! This is a DOS program.
It may crash or cause damages for which I am not liable.
LightsOut@home uses a random annealing algorithm to find a solution. Basically, it pushes buttons at random. If a certain button decreases (or doesn't change) the number of errors, it is saved. If it increases the errors the attempt is discarded. If this locks up for ten cycles, two buttons are pushed at random (regardless of the number of errors generated). Eventually it settles down to a solution with zero errors.
Use the arrow keys to move the cursor and the Enter key to toggle buttons. The "Initial" board is where you enter the puzzle. The solver begins the very moment you enter a puzzle, and you can change the puzzle at any time. The "Final" board is the answer to the puzzle. Usually this is left blank, unless you're really curious. "Lights On" shows the computer's progress as it works. The "Solution" is a record of which buttons must be pressed. When "Lights On" is the same as "Final", then the errors equal zero and the "solution" is correct. After a few minutes of idling, it will attempt to find a new solution to the same puzzle.
Some basic statistics are presented for no reason at all. "Recent history" logs the number of errors over the last 50 cycles. You can see minor lock-ups and the resulting random pokes. "Full history" is an autoscaling histogram of error frequency.
Random feature: Pressing F2 through F9 sets the X size of the grid. Pressing 2 through 9 sets the Y size of the grid. The algorithm is optimized for 5x5, so don't expect it to do anything amazing with odd sizes.
Random math: A 5x5 grid of binary values implies that there are 33,554,432 different possible puzzles and 33,554,432 different solutions. Each solution can only correspond to exactly one puzzle. However, not all puzzles have solutions. Examine the above screenshot of a completed puzzle. The solution has one diagonal (north east) line of symmetry. If you rotate the solution, so the line points north west, it will still solve the original puzzle. Thus the same puzzle can have more then one solution. This one has four. But there is a finite (and equal) number of puzzles and solutions. If some puzzles have more than their fair share of solutions, other puzzles will be shortchanged. Therefor, some puzzles have no solution.
Linkback: http://www.pages.drexel.edu/~kmk592/software/lightsout/ Printer friendly links: http://en.wikipedia.org/wiki/Lights_Out_%28game%29 http://www.pages.drexel.edu/~kmk592/software/lightsout/lights3.zip History: 2005/12/31 uploaded