Lights Out
Click cells to toggle their cross of lights. Turn them all off.
Overview
Lights Out is a logic puzzle played on a 5x5 grid of cells, each of which is either lit or unlit. Clicking a cell toggles that cell and its four orthogonal neighbours, and the goal is to turn every cell off starting from a randomised initial configuration. Every randomly generated puzzle is guaranteed solvable.
The game looks simple but has surprisingly deep structure: there's a unique minimal-move solution for every solvable board, and the set of solvable configurations forms a vector space over GF(2). This implementation gives you fresh random puzzles and tracks the number of clicks you've taken, so you can compete against yourself for shorter solutions.
How it works
Each cell has a binary state (on/off), and each click is an XOR on the cell and its neighbours. Because XOR is its own inverse and commutative, the order of clicks doesn't matter — only which cells you've clicked an odd number of times. This reduces solving Lights Out to solving a linear system over GF(2), where the 25-bit state vector equals the matrix-vector product of the click-pattern times the toggle matrix.
The "chase the lights" technique solves any 5x5 board: for each row from top to bottom, press whichever cells in the row immediately below are needed to turn off the current row, then move down. After processing rows 1-4, the final row may still have lights on — if so, the bottom-row pattern needed to fix it is one of a small fixed set of starting clicks in row 1, which a quick lookup table resolves.
Examples
- Click the centre cell: cells at (2,2), (1,2), (3,2), (2,1), (2,3) all toggle.
- A single-light puzzle with just (2,2) lit cannot be solved by clicking the centre alone — you need a 5-click cross pattern centred elsewhere.
- The "all lights on" puzzle has a known 15-click solution.
- Trying random clicks usually doesn't converge; the chase-the-lights algorithm finishes in at most 25 clicks.
FAQ
Are all random boards solvable?
This implementation generates puzzles by clicking a random pattern on the empty board, guaranteeing solvability.
What's the minimum click count for a given puzzle?
It varies. Some puzzles can be cleared in two clicks; others require 15 or more.
Why doesn't clicking the same cell twice help?
Because toggle is its own inverse — two clicks return the cell and its neighbours to their original state.
Is there a known formula for the minimum solution?
Yes — Gaussian elimination over GF(2) finds the minimum-weight solution in microseconds.
Does the size of the board matter?
Solvability depends on board dimensions. 5x5 has rank 23 (two free parameters), so most configurations are solvable.