🎮 How to Play
- Click any cell - it toggles itself plus its 4 orthogonal neighbors.
- Goal: turn ALL the lights off.
- Try to use the fewest moves possible.
About this tool
Lights Out is the 1995 handheld puzzle marketed by Tiger Electronics; the underlying mathematical structure is a system of linear equations over the finite field GF(2). Each press of a tile flips that tile plus its four orthogonal neighbours (the "plus-shape" stencil). The state space of a 5x5 board is 2^25 (33,554,432 patterns), but the solvable subset is a 23-dimensional subspace of dimension 2^23 (8,388,608 patterns), exactly one quarter of the total, because the 5x5 transition matrix over GF(2) has rank 23 with a 2-dimensional kernel. Anderson and Feil (1998) published the canonical parity invariants ("quiet patterns") that determine solvability. The minimum-press solver runs by Gaussian elimination on the 25x25 incidence matrix; the average optimal solution length across the solvable subset is roughly 9 to 10 presses, with the worst case being 15 (Sutner 1989). This implementation starts with 10 random toggles, guaranteeing a solvable puzzle by construction.
Common Lights Out pitfalls
- Random clicking. Pressing the same tile twice cancels (a + a = 0 over GF(2)), so any solution can be expressed as a unique 25-bit "press vector" where each tile is either pressed once or not at all. Order does not matter; commutativity is total.
- Ignoring the "light chasing" technique. The standard solving heuristic: solve the top row by pressing tiles in row 2 directly below any lit tile in row 1; repeat row by row until row 5; then a 32-entry lookup table dictates which row-1 presses fix any residual row-5 pattern.
- Assuming all patterns are solvable. Three of every four random 5x5 configurations are unreachable from the all-off state. This trainer pre-toggles from off, which keeps every puzzle solvable.
- Counting moves instead of unique tiles pressed. Because double-presses cancel, the optimum is always the smallest number of distinct tiles pressed once. Pressing 20 tiles where 10 cancel is no different from pressing the remaining 10.
- Solving on the diagonal. Diagonal neighbours are NOT toggled. Only the centre tile plus its four orthogonal neighbours flip. New players misread the stencil and lose moves debugging.
- Treating it as visual puzzle. Lights Out is pure linear algebra; intuition wins fewer than 15 moves but Gaussian elimination guarantees the optimum.
How to play this Lights Out
Click any of the 25 yellow / dark tiles. The clicked tile toggles state along with its top, bottom, left, and right neighbours. The goal is to drive every tile to OFF (dark). The move counter tracks total clicks; "New" generates a fresh puzzle with 10 random pre-presses (always solvable).
Worked example: the light-chasing pass
- Inspect row 1. For every lit tile in row 1, press the tile directly below it in row 2. Row 1 is now fully off (because the only press that toggles a row 1 tile without disturbing rows 3+ is the row 2 cell below).
- Repeat for row 2 down to row 4: each lit tile in row r is fixed by pressing the tile directly below in row r+1.
- Row 5 may now show any of 8 specific residual patterns (a 3-bit kernel). Cross-reference a precomputed lookup table to determine which 1 to 3 tiles in row 1 to press, then repeat the chase. After two passes the board is solved.
Solvability and optimum benchmarks
| Board | State space | Solvable fraction | Worst-case optimum |
|---|---|---|---|
| 3x3 | 512 | 1/1 | 9 presses |
| 4x4 | 65,536 | 1/1 | 4 presses |
| 5x5 (Tiger) | 33,554,432 | 1/4 | 15 presses |
| 6x6 | ~6.87 x 10^10 | 1/16 | 21 presses |
Why light chasing always works
Light chasing succeeds because once you have pressed every row except the first, the entire solution is determined by which tiles you press in row 1. There are only 32 possible row-1 press patterns, and each maps to exactly one residual pattern in row 5 after the chase. Building that 32-entry table once (or memorising the handful of useful entries) turns any solvable board into a two-pass procedure: press a specific subset of row 1, chase downward, and the board clears. If the chase leaves a row-5 pattern that no row-1 press can fix, the starting board was one of the three-in-four unsolvable configurations, which cannot happen here because this trainer always builds from the all-off state.
The same algebra scales to any size. A board of any dimension is solvable in polynomial time by Gaussian elimination over GF(2); only the rank of the press matrix, and therefore the fraction of solvable boards, changes with size. That is why a 4x4 board is always solvable while a 5x5 board is solvable only a quarter of the time.
Related puzzles
If linear algebra over GF(2) is fun, try Sudoku, Minesweeper (NP-complete), or Nonograms (also linear-equation solvable in special cases).
Frequently asked questions
Why are only one quarter of 5x5 patterns solvable?
The 25x25 incidence matrix that maps press-vectors to light-vectors over GF(2) has rank 23, leaving a 2-dimensional null space. Two parity invariants (the "quiet patterns" described by Sutner 1989) split the 2^25 state space into 4 equivalence classes; only the class containing the all-off state is reachable. The result: 2^23 = 8,388,608 of the 33,554,432 patterns are solvable.
What is the maximum number of presses ever needed?
On the standard 5x5 board, the worst-case optimum is 15 presses (verified by exhaustive enumeration). The average over all solvable patterns is around 9.7 presses. The all-on starting position is solvable in exactly 15 moves.
Does order of presses matter?
No. Each press is its own inverse over GF(2) and all presses commute. Any solution can be written as a 25-bit vector indicating which tiles are pressed an odd number of times; double-presses cancel.
Is solving Lights Out NP-hard?
No. Lights Out is in P; Gaussian elimination over GF(2) solves any instance in O(n^6) for an n x n board. Sutner (2000) showed that the broader "sigma-game" family is polynomial-time solvable on grids. The puzzle's difficulty for humans is psychological, not computational.
Why does this trainer use 10 random pre-presses?
Pre-pressing from the all-off state guarantees solvability (the result is in the reachable subspace). Using 10 presses creates puzzles that average 6 to 9 optimal moves, comfortable for casual solvers without trivialising the puzzle.