The optimal solve for Flip Tiles: cracking Lights Out with linear algebra

Building Flip Tiles raised a counterintuitive question: each click changes 5 cells; the game looks chaotic. Why are some starting states trivially solvable and others impossible? The answer lives in linear algebra. Here's how to solve it.

The real structure of the problem

Start with a counterintuitive observation: pressing the same cell twice is identical to not pressing it. Each cell's state (on/off) is binary; toggling twice returns it. So no matter the order or count, only the parity (odd or even) of presses per cell matters.

So on 5x5 you don't decide "how many times" or "in what order" — you decide which of the 25 cells to press an odd number of times. 2^25 ≈ 33 million options.

This algebraic structure where variables are 0 or 1 is called linear algebra over GF(2) (Galois Field 2). Key difference from regular real-number algebra: 1 + 1 = 0 (two presses cancel).

Game as equations

For each cell (i, j), its final state depends on:

• Its initial state
• Whether it was pressed an odd number of times
• Whether each of its 4 neighbors was pressed an odd number of times

So "cell (i,j) finishes on" becomes a GF(2) linear equation. 25 cells → 25 equations in 25 unknowns. The rest is classical Gaussian elimination — just over GF(2). Undergrad linear algebra.

But you don't need linear algebra to win

All that math sets up a very practical strategy: Light Chasing. The Lights Out player community converged on this in the 1990s.

The core idea:

From row 2 down, if a cell above (row 1 equivalent) is on, click the cell directly below it. After processing the entire board, rows 1–4 will be fully off. Only row 5 remains.

Concretely:

1. Process row by row, from row 2 (y=1) to row 5 (y=4)
2. For each (x, y) in row y: if (x, y-1) is on, click (x, y)
3. After processing all rows, rows 1–4 are guaranteed off
4. Inspect row 5: may be fully off (you win), may be a specific pattern (lookup table), may be unsolvable

Step 4 is the catch. Light Chasing alone doesn't solve 100% of 5x5 boards, because some initial states are fundamentally unsolvable (mathematically: not in the solution space). But —

BverGame's Flip Tiles guarantees solvability

This was the key generator decision: our generator starts from "all on" and randomly performs N presses backward. This means every initial state has at least one solution, because we built it by going backward from a solved state.

This is completely different from "randomly generate a board, then check if solvable." The latter requires Gaussian elimination and about 75% of random 5x5 boards are unsolvable (only 2^15 = 32,768 of 33,554,432 states ≈ 0.1% are solvable).

So you can grind any Flip Tiles puzzle without fear — it has a solution. If stuck, try Light Chasing.

Higher dimensions

3x3: 8-dimensional solution space, all 512 states solvable.

4x4: 16-dimensional solution space, all 65,536 states solvable.

5x5: 23-dimensional solution space, only 2^23 / 2^25 ≈ 25% of states solvable.

6x6: back to all states solvable.

This irregularity comes from a periodic property of "null space dimension" in GF(2) matrices — the 5x5 matrix has a 2-dimensional null space, shrinking the solution space by a factor of 4. The "some sizes solvable, others not" quirk is what makes Lights Out mathematically charming.

The standard 5x5 minimum solve

For the standard 5x5 starting fully on, the proven minimum solve is 15 clicks. No human can do better. It's a mathematical fact.

But BverGame's Flip Tiles doesn't start fully on — it starts from "all on" with 5–15 random press operations applied backward. So your optimal solve count is whatever that backward count was — usually 5–20 clicks depending on level.

Math isn't there to scare you

I'm not writing this to flex on linear algebra. The point: many small games that look random have beautifully structured math underneath. Knowing that structure means you're no longer playing blind — you're in conversation with the designer.

Next time you open Flip Tiles, sweep your eyes across the board first. Think Light Chasing. Play a few times. You'll improve much faster than you'd guess.

Plus, this trick makes you look mysterious in front of friends.

Leo is BverGame's co-engineer. Lights Out's mathematical structure is fully proven in Marlow Anderson and Todd Feil's 1998 paper "Turning Lights Out with Linear Algebra." The "light chasing" terminology comes from the 1990s Lights Out player community; specific origin lost to time.