History of Toggle
Lights Out™ is a commercial one-player game that consists of sequentially turning lights on or off on a 5 × 5 array. The game can be represented as a 5 × 5 lattice with vertex labels 1 (on) and 0 (off). A move involves toggling the 0/1 status of a vertex as well as the 0/1 status of all its orthogonal neighbors. A complete strategy for this game is detailed by Anderson and Feil in Turning Lights Out with Linear Algebra.
Fiorint Et. Al
Toggle Information
Abstract
In the commercial one-player game Lights Out™ a grid of lights is randomly generated with some lights on and some lights off. The player can press a light to flip its on/off state as well as the state of its neighbors. Toggle seeks to transform Lights OutTM into a variety of impartial two-player games. Two players take turns toggling the on/off state of lights in an attempt to leave the other player with no available legal moves. We analyze Toggle on various finite simple graphs and use impartial game theory to determine which player has a winning strategy given an initial Toggle configuration. Finally, we prove that determining the winning player given an arbitrary Toggle configuration is PSpace-complete.