Lights Out (video game)

"Lights Out" is an electronic puzzle game, released by Tiger Toys in 1995. (Tiger Toys was later bought by Hasbro in 1998.) [ [http://www.nytimes.com/2002/12/05/technology/circuits/05prof.html?ex=1192852800&en=d86461db6e751f2e&ei=5070 Building a Better Cat] , Saul Hansell. "New York Times", December 5, 2002. Accessed on line October 18, 2007.] The game consists of a 5 by 5 grid of lights; when the game starts, a set of these lights (random, or one of a set of stored puzzle patterns) are switched on. Pressing one of the lights will toggle it and the four lights adjacent to it on and off. (Diagonal neighbours are not affected.) The aim of the game is to switch all the lights off. [http://www.geocities.com/jaapsch/puzzles/lights.htm Lights Out] , Jaap's Puzzle Page. Accessed on line October 18, 2007.] [http://www.gamesetwatch.com/2007/01/column_beyond_tetris_lights_ou_1.php 'Beyond Tetris' - Lights Out] , Tony Delgado, "GameSetWatch", January 29, 2007. Accessed on line October 18, 2007.]

The Merlin electronic game which Parker Brothers released in the 1970s had a setting that played a game with similar rules on a 3x3 grid. A game similar to "Lights Out" was produced by Vulcan Electronics Ltd. in 1983 under the name "XL-25". Tiger Toys also produced a cartridge version of "Lights Out" for its Game.com handheld game console (1997), shipped free along with the console, and has released a number of new puzzles similar to "Lights Out", such as "Lights Out 2000", "Lights Out Cube", and "Lights Out Deluxe". Another similar puzzle available on the Internet is called "Fiver". [ [http://www.math.com/students/puzzles/fiver/fiver.html Fiver] , math.com. Accessed on line October 18, 2007.] [ [http://www.mazeworks.com/fiver/index.htm Fiver] , MazeWorks. Accessed on line October 18, 2007.]

Mathematics

The game involves toggling lights on and off. If a light is on, it must be toggled an odd number of times to be turned off. If a light is off, it must be toggled an even number of times (including not being toggled at all) for it to remain off. A successful solution is therefore a sequence of presses that toggles all the "on" lights an odd number of times and all the "off" lights an even number of times.

Two points may be noted:
*The order in which the lights are pressed does not matter. The end result of pressing a given set of lights is always that each light has been toggled a certain number of times. (For example, suppose the lights are numbered #1–#25 left to right from top to bottom. Pressing #3, #8 and #14 will toggle #2, #4, #7, #14, #15, #19 exactly once and #3, #8, #9, #13 exactly twice. No matter in what order you press #3, #8 and #14, all the affected lights will be toggled the same number of times in the end.)
*Each light needs to be pressed no more than once. Note that pressing a light twice is equivalent to not pressing it at all (indeed, pressing a light an even number of times is equivalent to not pressing it at all, and pressing it an odd number of times is equivalent to pressing it just once.) Since the order in which the lights are pressed does not matter, a sequence in which one light is pressed twice is equivalent to the same sequence with those two presses removed. Hence, the most efficient method of solving any puzzle (one that uses the minimum number of moves) is one in which no light is pressed more than once.

Despite these results, in practice, given a random board setup, it will not be obvious what sequence will toggle the "on" and "off" lights the required number of times.

Strategy

The most common method to solve this puzzle is to start by wiping all the lights except in the bottom, or last, row. This is done by pressing lights that are directly below lights that are turned on to cancel them out until only lights in the last row remain. Then, the following table must be memorized:

Top row produces Bottom row A -> -BC-E B -> ABC-- C -> AB-DE D -> --CDE E -> A-CD-

If we label the columns A through E, this table tells us that, if we press A in the top row and then follow the steps to bring down all the lights to the bottom row, that B, C, and E in the bottom row will end up being toggled. Some calculation must be done to figure out what combination of top row lights must be pressed in order to blank out the bottom row. (This is an example of the decomposition in linear algebra of a vector into basis vectors.) A strategy that works and does not require much thinking is the following:
#If A is the first light that is on in the bottom row, then press B in the top row and bring down the lights to the bottom row.
#If B is the first light that is on in the bottom row, then press A in the top row and bring down the lights.
#If C is the first light that is on in the bottom row, then press D in the top row and bring down the lights.Although this method will solve the puzzle if it is possible to do so, it will not do so in the minimum number of moves. If the puzzle is insoluble, D or E will remain on when all other lights have been turned off.

Beyond 5x5

The same general strategy could be used for a Lights Out game with any size grid. Here are the tables for other square grids:

2x2 =

A -> A- B -> -B

3x3 =

A -> -BC B -> ABC C -> AB-

4x4 =

A -> ---- B -> ---- C -> ---- D -> ----

5x5 =

A -> -BC-E B -> ABC-- C -> AB-DE D -> --CDE E -> A-CD-

6x6 =

A -> A---E- B -> -B-D-F C -> ----E- D -> -B---- E -> A-C-E- F -> -B---F

7x7 =

A -> A-CD-FG B -> --CD-FG C -> AB----- D -> AB-D-FG E -> -----FG F -> AB-DE-- G -> AB-DE-G

8x8 =

A -> ----E--- B -> ---D-F-- C -> --C-E-G- D -> -B-D-F-H E -> A-C-E-G- F -> -B-D-F-- G -> --C-E--- H -> ---D----

9x9 =

A -> A-C-E-G-I B -> --------- C -> A-C-E-G-I D -> --------- E -> A-C-E-G-I F -> --------- G -> A-C-E-G-I H -> --------- I -> A-C-E-G-I

10x10 =

A -> A-C---G-I- B -> ---D-F---J C -> A--------- D -> -B-D-F---J E -> ------G-I- F -> -B-D------ G -> A---E-G-I- H -> ---------J I -> A---E-G--- J -> -B-D---H-J

These tables are quite easy to generate. Starting with a blank board is best, but a board that only has lights in the bottom row will do. Just press a light at the top, bring the lights down and see which ones have changed.

Variations and generalizations

*Different goals (perhaps a certain shape)
*On a torus (top is connected to bottom, left to right)
*More dimensions
*Different shapes (not rectangular) [http://www.cwynn.com/Games/LightsOutHex.htm Play Example] with hexagons
*More states
*Changes surroundings differently (not necessarily up, down, left, and right)

ee also

*Group theory
*Not to be confused with the "Lights" game

References

External links

* [http://www.braingle.com/games/disco/index.php?play=1;ref=trillionaire Play Disco (spin-off of Lights Out)] at Braingle.com (Brain Teasers, Riddles, Puzzles, Trivia, etc.)
* [http://www.cwynn.com/Games/LightsOut3x3.htm Play Lights Out] at cWynn.com
* [http://www.geocities.com/jaapsch/puzzles/lights.htm Lights Out] at Jaap's Puzzle Page.
* [http://mathworld.wolfram.com/LightsOutPuzzle.html Lights Out Puzzle] at MathWorld.
* [http://www.anarkasis.com/rafa/indexuk.htm Lights Out Solutions & Maths]
* [http://fishbowllab.com/ Play a 9x9 grid lights out online] at the Fishbowl Lab