Solvable Lights Out Boards and Level Generation with GF(2) Linear Algebra

Only a quarter of the possible boards in standard 5×5 Lights Out can be solved. Each press toggles its own cell and its orthogonal neighbours on the board; pressing twice cancels out. The puzzle is therefore a linear system with 25 unknowns over GF(2). Its press matrix has rank 23, leaving 2^23 solvable boards out of 2^25, with exactly 4 press parity vectors for each solvable board.

A level generator can guarantee a solution by starting with every light off and pressing buttons. Choose each button independently with probability 1/2 and the resulting boards are also uniform over the solvable set. Measure the minimum number of presses for each result, then keep boards within the range you want.

A press is addition mod 2

Tiger Electronics released Lights Out in 1995. The standard game has a 5×5 grid of lights and asks the player to turn them all off. A press toggles its own cell and the adjacent cells above, below and to either side, wherever those neighbours exist within the board. Edge buttons consequently affect fewer cells.

Write an unlit cell as 0 and a lit cell as 1. Toggling adds 1 modulo 2, where 1 + 1 = 0. Presses commute, and pressing the same button twice undoes its effect. A complete sequence can therefore be represented by a 25-entry vector x: each entry records whether its button was pressed an odd or even number of times.

Represent the board by another 25-entry vector b, and collect the effects of the buttons in a 25×25 matrix A. Column i has a 1 wherever button i toggles a cell. Turning every light off means solving b + A·x = 0. Addition and subtraction coincide in GF(2), so this is equivalent to A·x = b.

Gaussian elimination and the rank

The script rank_table.py stores each matrix row in a Python int. Each bit records whether the corresponding button affects that cell. Neighbour relationships work in both directions, so the matrix is symmetric: the same cross pattern describes a row or a column. For each bit position the script finds a pivot and uses XOR to eliminate that bit from the other rows. Counting the pivots gives the rank.

# Lights Out as a linear system over GF(2).
# Each button toggles itself and its four neighbours; a board is solvable iff it lies
# in the column space of the n*n x n*n press matrix. Rank is computed by Gaussian
# elimination with each matrix row packed into a Python int (one bit per cell).
def rank_gf2(n):
    N = n * n
    rows = []
    for i in range(N):
        r, c = divmod(i, n)
        v = 1 << i
        if r > 0: v |= 1 << (i - n)
        if r < n - 1: v |= 1 << (i + n)
        if c > 0: v |= 1 << (i - 1)
        if c < n - 1: v |= 1 << (i + 1)
        rows.append(v)
    rank = 0
    for bit in range(N):
        pivot = next((j for j in range(rank, N) if rows[j] >> bit & 1), None)
        if pivot is None:
            continue
        rows[rank], rows[pivot] = rows[pivot], rows[rank]
        for j in range(N):
            if j != rank and rows[j] >> bit & 1:
                rows[j] ^= rows[rank]
        rank += 1
    return rank

print(f"{'board':>5} {'rank':>4} {'nullity':>7} {'solvable boards':>22} {'share':>7} {'press vectors per board':>24}")
for n in range(2, 10):
    N = n * n
    r = rank_gf2(n)
    print(f"{n}x{n:<3} {r:4d} {N - r:7d} {2**r:22,} {100 / 2**(N - r):6.2f}% {2**(N - r):24d}")

board rank nullity        solvable boards   share  press vectors per board
2x2      4       0                     16 100.00%                        1
3x3      9       0                    512 100.00%                        1
4x4     12       4                  4,096   6.25%                       16
5x5     23       2              8,388,608  25.00%                        4
6x6     36       0         68,719,476,736 100.00%                        1
7x7     49       0    562,949,953,421,312 100.00%                        1
8x8     64       0 18,446,744,073,709,551,616 100.00%                        1
9x9     73       8 9,444,732,965,739,290,427,392   0.39%                      256

The image of the linear map contains 2^rank boards, so this is also the number of solvable boards. Nullity is the number of unknowns minus the rank, giving 25 - 23 = 2 for the standard board.

The kernel consists of all vectors q for which A·q = 0: press those buttons and the board is unchanged. Starting with any solution x₀, adding a kernel vector produces another solution to the same board, and every solution can be obtained this way. The solution set is a translate of the kernel, so it contains 2^nullity vectors. For 5×5, that gives 2^23 = 8,388,608 solvable boards, a quarter of the total, and 2^2 = 4 solutions per solvable board. A solver can compare these 4 solutions to find the shortest.

Those 4 solutions are press parity vectors. Counting different button orders, or allowing a button to be pressed an extra two times, would give many more operation sequences.

Recalculate the rank when changing the board size. A larger board can have a higher or lower solvable proportion: the 4×4 board has nullity 4 and only 6.25% of its boards are solvable. Every board from 6×6 through 8×8 is solvable, yet the proportion drops to about 0.39% at 9×9.

Checking solvability with light chasing

Light chasing solves the board without constructing a matrix. Choose which buttons to press in the first row, then work downwards. Wherever a light remains on in the preceding row, press the button directly beneath it. This clears the preceding row without disturbing any row further up. Once the first row’s presses are fixed, all later presses are forced; only the bottom row can remain lit at the end.

There are just 2^5 = 32 choices for the first row. Try each one, and the board is solvable if any choice leaves the bottom row dark. On an initially dark board, successful choices recover the full press vectors that leave it dark: the quiet patterns forming the kernel. The script light_chasing.py enumerates these, then checks 100,000 random boards to estimate the solvable proportion.

# Independent cross-check without linear algebra: "light chasing".
# Choose which of the 32 first-row buttons to press, then walk down the board pressing
# the button under every lit cell. Only the last row can stay lit; the board is solvable
# iff some first-row choice leaves it dark. On an all-dark board, the first-row choices
# that leave it dark are exactly the quiet patterns (the kernel), so their count is 2^nullity.
import random

random.seed(42)
N = 5

def press(board, r, c):
    for y, x in ((r, c), (r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
        if 0 <= y < N and 0 <= x < N:
            board[y][x] ^= 1

def chase(board, first_row):
    b = [row[:] for row in board]
    for c in range(N):
        if first_row >> c & 1:
            press(b, 0, c)
    for r in range(1, N):
        for c in range(N):
            if b[r - 1][c]:
                press(b, r, c)
    return not any(b[N - 1])

def quiet_pattern(first_row):
    # Record which buttons light chasing presses on an all-dark board for this first row.
    b = [[0] * N for _ in range(N)]
    pressed = [[0] * N for _ in range(N)]
    for c in range(N):
        if first_row >> c & 1:
            press(b, 0, c); pressed[0][c] = 1
    for r in range(1, N):
        for c in range(N):
            if b[r - 1][c]:
                press(b, r, c); pressed[r][c] = 1
    return None if any(b[N - 1]) else pressed

dark = [[0] * N for _ in range(N)]
quiet = [(f, quiet_pattern(f)) for f in range(32) if chase(dark, f)]
print(f"5x5: first-row choices that keep an all-dark board dark = {len(quiet)} -> nullity = {len(quiet).bit_length() - 1}")
for f, pat in quiet:
    weight = sum(map(sum, pat))
    print(f"  first row {f:05b}  quiet pattern weight {weight:2d}  rows: " + " ".join("".join(map(str, row)) for row in pat))

trials = 100_000
solvable = 0
for _ in range(trials):
    board = [[random.randrange(2) for _ in range(N)] for _ in range(N)]
    solvable += any(chase(board, f) for f in range(32))
p = solvable / trials
ci = 1.96 * (p * (1 - p) / trials) ** 0.5
print(f"random 5x5 boards solvable: {p:.4f} +/- {ci:.4f}  (linear algebra says 2^23 / 2^25 = 0.2500)")

5x5: first-row choices that keep an all-dark board dark = 4 -> nullity = 2
  first row 00000  quiet pattern weight  0  rows: 00000 00000 00000 00000 00000
  first row 01110  quiet pattern weight 16  rows: 01110 10101 11011 10101 01110
  first row 10101  quiet pattern weight 12  rows: 10101 10101 00000 10101 10101
  first row 11011  quiet pattern weight 12  rows: 11011 00000 11011 00000 11011
random 5x5 boards solvable: 0.2497 +/- 0.0027  (linear algebra says 2^23 / 2^25 = 0.2500)

Exactly 4 first-row choices return the dark board to darkness, so the kernel has size 4 and nullity 2. One choice presses nothing; the non-zero patterns have weights 16, 12 and 12, where weight counts the 1s in a press vector.

The full patterns beginning with 01110 and 10101, v₁ and v₂, form a basis for the kernel. XOR them to get the remaining non-zero pattern, beginning with 11011. Adding each non-zero pattern to a known solution gives the other solutions.

The random-board estimate is 0.2497 ± 0.0027, an approximate 95% confidence interval containing 0.25. Trying 32 first-row choices determines whether a board is solvable without enumerating all 2^25 boards.

What a level generator can promise

Starting from a dark board makes solvability straightforward: repeat the same presses and the board goes dark again. The choice of presses determines the distribution of levels produced.

Generator A chooses each button independently with probability 1/2. This makes every one of the 2^25 press vectors equally likely. Under A·x, exactly 4 vectors map to each solvable board, giving every such board probability 4 / 2^25 = 1 / 2^23.

Generator B makes exactly k presses, choosing a button uniformly each time and allowing repeats. Its distribution depends on k and cannot be uniform across all solvable boards. The script generator.py produces 20,000 boards for each setting, then measures the minimum number of presses with light chasing.

# Two level generators for 5x5 Lights Out, both starting from the all-dark board.
#   A: each of the 25 buttons is pressed independently with probability 1/2.
#      Every board produced is solvable, and the 2^25 press vectors map 4-to-1 onto the
#      2^23 solvable boards, so the boards are uniform over the solvable set.
#   B: press k uniformly random buttons (repeats allowed). Also always solvable, but the
#      distribution over boards depends on k, so there is no uniformity claim.
# "Difficulty" below is the minimum number of presses among the 4 press vectors that
# solve the board; it is found by trying all 32 first rows with light chasing.
import random
from collections import Counter

random.seed(42)
N = 5

def press(board, r, c):
    for y, x in ((r, c), (r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
        if 0 <= y < N and 0 <= x < N:
            board[y][x] ^= 1

def min_presses(board):
    best = None
    for first in range(32):
        b = [row[:] for row in board]
        presses = 0
        for c in range(N):
            if first >> c & 1:
                press(b, 0, c); presses += 1
        for r in range(1, N):
            for c in range(N):
                if b[r - 1][c]:
                    press(b, r, c); presses += 1
        if not any(b[N - 1]) and (best is None or presses < best):
            best = presses
    return best  # None would mean unsolvable

def gen_a():
    b = [[0] * N for _ in range(N)]
    for i in range(N * N):
        if random.random() < 0.5:
            press(b, *divmod(i, N))
    return b

def gen_b(k):
    b = [[0] * N for _ in range(N)]
    for _ in range(k):
        press(b, *divmod(random.randrange(N * N), N))
    return b

trials = 20_000
for name, gen in (("A: each button w.p. 1/2", gen_a), ("B: k=3 random presses", lambda: gen_b(3)), ("B: k=10 random presses", lambda: gen_b(10))):
    hist = Counter()
    unsolvable = 0
    for _ in range(trials):
        m = min_presses(gen())
        if m is None: unsolvable += 1
        else: hist[m] += 1
    mean = sum(k * v for k, v in hist.items()) / trials
    print(f"{name:26s} unsolvable={unsolvable}  mean min presses={mean:5.2f}  distribution={dict(sorted(hist.items()))}")

A: each button w.p. 1/2    unsolvable=0  mean min presses= 9.90  distribution={1: 1, 3: 6, 4: 31, 5: 116, 6: 427, 7: 1080, 8: 2333, 9: 3895, 10: 4632, 11: 3966, 12: 2416, 13: 885, 14: 184, 15: 28}
B: k=3 random presses      unsolvable=0  mean min presses= 2.76  distribution={1: 2429, 3: 17571}
B: k=10 random presses     unsolvable=0  mean min presses= 7.01  distribution={2: 148, 4: 2028, 6: 7403, 8: 8376, 10: 2045}

The generation count puts an upper bound on the shortest solution. Repeated presses can cancel, and another solution may use fewer buttons. The shortest solutions averaged 9.90 presses for A, 2.76 for B with k=3, and 7.01 for B with k=10.

The distributions for B have a further restriction. With k=3, every board needs either 1 or 3 presses; with k=10, every minimum is even. All the non-zero quiet patterns found above have even weight. XORing one with a solution preserves the parity of its button count, so all 4 solutions of a given board have the same parity, including the minimum. Repeated presses during generation also cancel in pairs. A board generated with k presses must therefore have a minimum press count with the same parity as k.

Measuring difficulty

The function min_presses tries all 32 first-row choices and returns the smallest press count among those that clear the board. For a solvable standard 5×5 board, this compares all 4 solutions. A result of 0 means the board is already dark; discard it before offering it to a player.

For uniform sampling within a chosen press-count range, call gen_a() and pass each board to min_presses, keeping only those in range. Filtering this way preserves uniformity within the accepted set. A’s sample clusters around 9 to 11 presses, with very few boards needing 4 presses or fewer, so prepare low-count levels offline rather than leave the player waiting for candidates. If uniform sampling is unnecessary, call gen_b(k) with k as the upper limit, then check that the actual minimum falls within the required range.

Minimum press count does not measure the time a player needs to find a solution. Playtest the selected boards and use that time to decide which levels belong near the start.

Notes

Check the solvable proportion before generating random light states. Standard 5×5 has rank 23 and only 2^23 solvable boards; finding the shortest solution requires comparing its 4 press parity vectors.
Use light chasing to check a solver: try all 32 first-row choices, with kernel size 4 and a random-board solvable proportion of 25% as reference values.
For uniform solvable boards, start dark and select each button independently with probability 1/2. Consider a fixed k when the generation count needs a limit.
Before choosing a fixed k, check that its parity permits the minimum press counts you want.
Recalculate nullity for each board size. It is 4 at 4×4, zero from 6×6 through 8×8, and 8 at 9×9.
Apply the minimum-press filter before offering a level, then use playtesting to adjust the accepted range.