Lights Out (game)
When the game starts, a random number or a stored pattern of these lights is switched on.
The goal of the puzzle is to switch all the lights off, preferably with as few button presses as possible.
Tiger Toys also produced a cartridge version of Lights Out for its Game com handheld game console in 1997, shipped free with the console.
[1][2] Lights Out was created by a group of people including Avi Olti, Gyora Benedek, Zvi Herman, Revital Bloomberg, Avi Weiner and Michael Ganor.
The members of the group together and individually also invented several other games, such as Hidato, NimX, iTop and many more.
When the game starts, a random number or a stored pattern of these lights is switched on.
The goal of the puzzle is to switch all the lights off, preferably in as few button presses as possible.
[1][4] 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 none at all) for it to remain off.
Firstly, the order in which the lights are pressed does not matter, as the result will be the same.
[5] In 1998, Marlow Anderson and Todd Feil used linear algebra to prove that not all configurations are solvable and also to prove that there are exactly four winning scenarios, not including redundant moves, for any solvable 5×5 problem.
Anderson and Feil found that in order for a configuration to be solvable (deriving the null vector from the original configuration) it must be orthogonal to the two vectors N1 and N2 below (pictured as a 5×5 array but not to be confused with matrices).
[7] "Light chasing" is a method similar to Gaussian elimination which always solves the puzzle (if a solution exists), although with the possibility of many redundant steps.
The last row is solved separately, depending on its active lights.
Corresponding lights (see table below) in the top row are toggled and the initial algorithm is run again, resulting in a solution.
[8] Tables and strategies for other board sizes are generated by playing Lights Out with a blank board and observing the result of bringing a particular light from the top row down to the bottom row.
Once a single solution is found, a solution with the minimum number of moves can be determined through elimination of redundant sets of button presses that have no cumulative effect.
[6][8] Existence of solutions has been proved for a wide variety of board configurations, such as hexagonal,[9] while solutions to n-by-n boards for n≤200 have been explicitly constructed.
It is solvable on any undirected graph, where clicking on one vertex flips its value and its neighbours.
More generally if the action matrix is symmetric then its diagonal is always solvable.
