xiv. Lights Out

Problem. An $n\times m$ grid of lights; pressing a cell toggles it and its 4 neighbours. Turn every light off, with the fewest presses.

Presses commute and pressing twice cancels, so a solution is a set of cells: a linear system over GF(2) with $nm$ unknowns. Two ways to solve it:

Method	Cost	Notes
light chasing: choose the first row, then each light still on in row $i-1$ forces a press below it	$O(2^m\cdot nm)$	simple, gives the minimum over all solutions by trying every first row
Gaussian elimination over GF(2) on $nm$ variables	$O((nm{)}^3/64)$ with bitsets	solvability and one solution; the minimum needs enumeration of the null space
chasing + elimination: express the last row as a linear function of the first row ($m$ unknowns)	$O(m^3+n{m}^2)$	best for large $n$

vector<vector<int>> lightsOut(const vector<vector<int>>& g) {  // presses that turn all lights off, or empty if none (min presses)
    int n = sz(g), m = sz(g[0]); vector<vector<int>> best; int bestCnt = INT_MAX;
    for (int mask = 0; mask < (1 << m); mask++) {  // choose the first row; every later row is forced ("light chasing")
        vector<vector<int>> a = g, p(n, vector<int>(m, 0)); int cnt = 0;
        auto press = [&](int i, int j) {
            p[i][j] = 1; cnt++;
            int di[] = {0, 1, -1, 0, 0}, dj[] = {0, 0, 0, 1, -1};
            for (int k = 0; k < 5; k++) { int x = i + di[k], y = j + dj[k]; if (x >= 0 && x < n && y >= 0 && y < m) a[x][y] ^= 1; }
        };
        for (int j = 0; j < m; j++) if (mask >> j & 1) press(0, j);
        for (int i = 1; i < n; i++) for (int j = 0; j < m; j++) if (a[i - 1][j]) press(i, j);
        bool ok = true; for (int j = 0; j < m; j++) if (a[n - 1][j]) ok = false;
        if (ok && cnt < bestCnt) bestCnt = cnt, best = p;
    }
    return best;
}

Proof: light chasing is complete

Fix the presses in row $0$. A light in row $i-1$ (for $i\ge 1$) can afterwards only be changed by presses in rows $i-1$ (already fixed) or $i$, and the only cell in row $i$ adjacent to it is the one directly below; so that press is forced exactly when the light is on. Hence each first-row choice determines a unique press pattern for the whole grid, which is a solution iff the last row ends up dark. Enumerating all $2^m$ first rows therefore enumerates all solutions, and the minimum press count among them is optimal. Tested against brute force over all press subsets for boards up to $4\times 4$.

The standard $5\times 5$ board is solvable for exactly $2^{23}$ of the $2^{25}$ starting patterns (the press matrix has a 2-dimensional null space).