Solving Lights Out with GF(2) Linear Algebra — the Whole Puzzle Is One Matrix Equation, plus the 5 5 Quiet Patterns and the Solvability Rate

The classic Lights Out puzzle (press a cell, it and its neighbours flip; goal: all dark) built for the browser with a GF(2) linear-algebra solver inside. Three hinges: (1) the whole puzzle is one matrix equation A·x = b (mod 2) — over the field {0,1} where addition is XOR, pressing is linear and a solution is just a set of cells; (2) a mod-2 row operation is a single XOR (boards and matrix rows are bigint bitmasks); (3) the 5×5 board is famously singular — a dimension-2 null space (the "quiet patterns"), a ¼ solvability rate, and exactly 4 solutions per solvable board — all pinned by tests. Solver-equipped puzzle #2, after Sudoku's hint engine (#33).

🌐 Live demo: https://sen.ltd/portfolio/lights-out/
📦 GitHub: https://github.com/sen-ltd/lights-out

The whole game is one equation

Pressing cell i toggles i and its orthogonal neighbours. Over GF(2) —
the field {0,1} with XOR as addition — that's linear:

A·x = b   (mod 2)

b is the current board (1 = lit), x is which cells to press, and column i
of A is the toggle pattern of pressing i. Presses commute and a double press
cancels, so a solution is a set of cells — no order, no repetition. Solving
the puzzle is solving the system, and Gaussian elimination over GF(2)
finishes it mechanically.

A row operation is one XOR

Boards and matrix rows are bigint bitmasks, so the mod-2 row op (adding one
row to another) is a single XOR:

for (let r = 0; r < N; r++) {
  if (r !== rank && (rows[r] >> BigInt(col)) & 1n) rows[r] ^= rows[rank]; // XOR = mod-2 row op
}

Reduce the augmented matrix [A | b] to RREF and read off the pivots. If a
contradictory row (0 = 1) remains, the board is provably unsolvable — not
"probably hard", but impossible, with a certificate.

The famous singularity of 5×5

On the classic 5×5 board, A is not invertible: its null space has
dimension 2, spanned by the two quiet patterns — press-sets that change
nothing at all. Three consequences, all visible in the app and pinned by tests:

• Exactly ¼ of random boards are solvable (two parity constraints). A test samples 400 random boards and checks the fraction lands near 25%.
• Unsolvable boards are detected: elimination ends in a contradiction and solve returns null. A single lit corner is the classic impossible case.
• Every solvable board has exactly 4 solutions (particular + null space); bestSolve enumerates them and returns the fewest-press one.

it('null space has dimension 2 (the famous quiet patterns)', () => {
  expect(nullBasis(5)).toHaveLength(2);
});

On 3×3 and 4×4, A is invertible, so every board is solvable — the same code
proves that too (nullBasis(3) is empty). Switching sizes changes the
character of the matrix, which is half the fun.

Engine / shell split

All the math lives in src/lightsout.ts with no DOM reference, so the solver is
unit-tested directly — and every solution is verified by replaying it and
checking the board reaches all-dark (14 vitest cases). The UI (src/main.ts) is
a thin shell: grid, clicks, a one-cell hint, and a show-solution overlay.

src/lightsout.ts      — pure engine: toggle masks, GF(2) elimination, null basis,
                        fewest-press solve, random solvable boards
src/lightsout.test.ts — 14 cases (replay-verified solves, quiet patterns,
                        ¼-solvability statistics, unsolvable detection)
src/main.ts           — DOM shell: grid, hint / show-solution overlays

Takeaway

Lights Out is the textbook case of a game whose entire state space folds into
linear algebra: one equation, XOR-powered Gaussian elimination, and the
5×5 singularity (quiet patterns, ¼ solvability, 4 solutions) — all of it
playable. Press "Show solution" in the demo: the green-outlined cells are what
GF(2) says to press.

🌐 Live demo: https://sen.ltd/portfolio/lights-out/
📦 GitHub: https://github.com/sen-ltd/lights-out