Lights Out

Lights Out is a 1995 handheld puzzle: a grid of lit buttons where pressing one toggles that light and its four neighbors. The goal is to turn every light off. It feels maddening — flip one and you ruin three others — so most people stab at it and hope.

But here is the secret the toy never tells you: pressing a button twice is the same as never pressing it at all. Order doesn't matter either. So the only thing that matters about a solution is which buttons you press an odd number of times — a yes/no choice per cell.

That single observation turns a chaotic-looking game into something rigid and mathematical. Every light obeys an equation, and "is this board solvable?" has a clean, fast answer — no guessing required.

Click the lights to set up any pattern you like. Each press toggles a cell and its orthogonal neighbors — that is the real Lights Out rule. Then press Solve and watch the puzzle collapse.

<p class="hint">{{hint}}</p>
<div id="board" class="board"></div>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="solve" type="button">{{btn_solve}}</button>
  <button id="rand" type="button">{{btn_rand}}</button>
  <button id="clear" type="button" class="ghost">{{btn_clear}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.board { display: grid; grid-template-columns: repeat(5, 50px); gap: 5px; margin: .4rem 0; }
.cell { width: 50px; height: 50px; border-radius: 9px; cursor: pointer; position: relative;
        border: 1px solid #adb1b8; background: #2b2f36; transition: all .12s; }
.cell.on { background: #ffd23f; border-color: #e0b400; box-shadow: 0 0 8px rgba(255,210,63,.6); }
.cell:hover { transform: scale(1.05); }
.cell.press::after { content: "↧"; position: absolute; inset: 0; display: flex;
        align-items: center; justify-content: center; font: 800 22px system-ui, sans-serif;
        color: #e63946; }
.cell.on.press::after { color: #1d3557; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

The solver isn't searching or guessing. It writes one equation per cell — the on/off state must flip an odd number of times — and runs Gaussian elimination mod 2. The press cells it highlights are a guaranteed solution, found in a fixed number of steps. If you build a board it can't fix, it tells you so with certainty: some boards are genuinely unsolvable, and the same math proves it.

How hard is Lights Out, really? The honest answer surprises people: it's easy — provably in P.

• The key field is GF(2), the numbers {0, 1} with addition being XOR (1+1 = 0). "Toggle" is addition mod 2, and pressing twice cancels — exactly the GF(2) rule.
• Each cell gives one linear equation. Unknowns are the press-or-not decisions; the equation says the cell's final parity must be off. An n×n board is a system of $n^{2}$ equations in $n^{2}$ unknowns over GF(2).
• Gaussian elimination solves it. The same row-reduction from school algebra works over GF(2), in roughly $O(n^{6})$ bit operations — polynomial, deterministic, complete.
• It also decides solvability. If reduction hits a contradiction (0 = 1), the board has no solution; the rank of the matrix tells you exactly how many boards are solvable and how many distinct solutions each has.

That is the punchline: unlike Minesweeper, whose consistency question is NP-complete, Lights Out has a hidden linear structure. Linearity is the great simplifier — it drops the problem far below the hard frontier of P vs NP. What looks like blind trial and error is one clean matrix solve.

"Solve a system of XOR equations" is one of the quietly most useful tasks in computing, and Lights Out is its playful face:

• Error-correcting codes: every CD, QR code and disk drive uses parity equations over GF(2); decoding is Gaussian elimination, exactly like solving the puzzle.
• Cryptography: linear pieces of ciphers are attacked with the same mod-2 algebra — and their weakness to it is precisely why ciphers add nonlinearity.
• Circuit and constraint solving: XOR constraints appear inside SAT solvers, where a dedicated linear-algebra engine handles them far faster than search.
• Teaching the power of structure: Lights Out is the cleanest demo that recognizing linearity can move a problem from "hopeless guessing" to "instant exact answer."

Learn why Lights Out is easy and you've met the workhorse of coding theory: solving linear systems over a finite field, the same idea behind much of factoring-era number theory and reliable digital communication.

Lights Out hides a reassuring secret: the chaos is fake. Once you notice that pressing twice cancels and order doesn't matter, the whole puzzle becomes a system of linear equations over GF(2) — and Gaussian elimination solves any board, decides solvability, and counts the solutions, all in polynomial time.

So the next time a problem feels like hopeless fumbling, ask whether it's secretly linear. Sometimes the hardness is real, as in Minesweeper. And sometimes, as here, a single algebraic insight switches the lights off all at once.