Introduction

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.

Try It

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">Click a light to toggle it <b>and its four neighbors</b> — the real Lights Out rule. Then press <b>Solve</b>: a linear-algebra engine over GF(2) finds which buttons to press (highlighted) to turn the whole board off, or proves no solution exists.</p>
<div id="board" class="board"></div>
<div class="status" id="status">Toggle some lights, then Solve.</div>
<div class="btns">
  <button id="solve" type="button">Solve</button>
  <button id="rand" type="button">Random board</button>
  <button id="clear" type="button" class="ghost">All off</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Lights Out as linear algebra over GF(2). Pressing a button toggles it and its
    // 4 orthogonal neighbors. Toggling = addition mod 2 (XOR); pressing twice cancels;
    // order is irrelevant. So solving "turn every light off" is a linear system
    //   A x = b   over GF(2),
    // where x[i] = press button i (0/1), A[i] has 1s for button i's toggle set, and
    // b = current light state. Gaussian elimination mod 2 solves it in polynomial time
    // and decides solvability exactly (a 0 = 1 row means no solution).
const N = 5, M = N * N;
let lights = new Array(M).fill(0);   // current on/off state
let press  = new Array(M).fill(0);   // highlighted solution

const idx = (r, c) => r * N + c;
function toggleSet(i) {              // button i toggles itself + orthogonal neighbors
  const r = (i / N) | 0, c = i % N, s = [i];
  if (r > 0)     s.push(idx(r - 1, c));
  if (r < N - 1) s.push(idx(r + 1, c));
  if (c > 0)     s.push(idx(r, c - 1));
  if (c < N - 1) s.push(idx(r, c + 1));
  return s;
}
// Press matrix A: column i = which lights button i flips.
const A = Array.from({ length: M }, () => new Array(M).fill(0));
for (let i = 0; i < M; i++) for (const j of toggleSet(i)) A[j][i] = 1;

// Solve A x = b over GF(2). Returns x array, or null if inconsistent.
function solveGF2(b) {
  // Augmented rows: each row = M coefficient bits + 1 rhs bit, packed in an array.
  const rows = [];
  for (let i = 0; i < M; i++) rows.push(A[i].slice().concat(b[i]));
  const where = new Array(M).fill(-1);
  let row = 0;
  for (let col = 0; col < M && row < M; col++) {
    let piv = -1;
    for (let r = row; r < M; r++) if (rows[r][col]) { piv = r; break; }
    if (piv === -1) continue;
    [rows[row], rows[piv]] = [rows[piv], rows[row]];
    for (let r = 0; r < M; r++)
      if (r !== row && rows[r][col])
        for (let k = col; k <= M; k++) rows[r][k] ^= rows[row][k];
    where[col] = row; row++;
  }
  // Inconsistency: a row 0...0 | 1 means no solution.
  for (let r = 0; r < M; r++) {
    let allZero = true;
    for (let k = 0; k < M; k++) if (rows[r][k]) { allZero = false; break; }
    if (allZero && rows[r][M]) return null;
  }
  const x = new Array(M).fill(0);
  for (let col = 0; col < M; col++) if (where[col] !== -1) x[col] = rows[where[col]][M];
  return x;
}

function render() {
  const b = document.getElementById('board'); b.innerHTML = '';
  for (let i = 0; i < M; i++) {
    const d = document.createElement('div');
    d.className = 'cell' + (lights[i] ? ' on' : '') + (press[i] ? ' press' : '');
    d.addEventListener('click', () => {
      for (const j of toggleSet(i)) lights[j] ^= 1;  // a click presses button i
      press = new Array(M).fill(0);
      render(); setStatus('Toggle some lights, then Solve.', '');
    });
    b.appendChild(d);
  }
}
function setStatus(t, cls) { const s = document.getElementById('status'); s.textContent = t; s.className = 'status ' + cls; }

document.getElementById('solve').addEventListener('click', () => {
  const x = solveGF2(lights.slice());
  if (!x) { press = new Array(M).fill(0); render(); setStatus('✗ This board has no solution (the equations contradict).', 'bad'); return; }
  press = x;
  const k = x.reduce((a, v) => a + v, 0);
  render();
  setStatus(fmt('✓ Solved by Gaussian elimination — press the %k% marked buttons.', { k: k }), 'ok');
  console.log('Press set (1 = press):', x.join(''));
});
document.getElementById('rand').addEventListener('click', () => {
  // A board built by random presses is always solvable; this guarantees a fun, solvable start.
  lights = new Array(M).fill(0);
  for (let i = 0; i < M; i++) if (Math.random() < 0.5) for (const j of toggleSet(i)) lights[j] ^= 1;
  press = new Array(M).fill(0); render(); setStatus('Random solvable board. Press Solve.', '');
});
document.getElementById('clear').addEventListener('click', () => {
  lights = new Array(M).fill(0); press = new Array(M).fill(0); render(); setStatus('All off. Toggle some lights, then Solve.', '');
});

// Start with a small solvable pattern.
for (const j of toggleSet(idx(2, 2))) lights[j] ^= 1;
for (const j of toggleSet(idx(0, 0))) lights[j] ^= 1;
render();
Result
Console

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.

The Real Complexity

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 n2n^{2} equations in n2n^{2} unknowns over GF(2).
  • Gaussian elimination solves it. The same row-reduction from school algebra works over GF(2), in roughly O(n6)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.

Where It Matters

"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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/lights-out/Content licensed under CC BY-NC 4.0.