The first row kills it

September 9, 2026 · algorithms

The action space is finite: one press per cell. Sequences of actions look huge. Two properties cut the plans to 2^{MN}. Then the first row makes the rest forced: 2^N.

The problem

AcWing 95, Flip Switch. Twenty-five lights in a $5 \times 5$ grid. $1$ is on, $0$ is off. One step: pick a cell, toggle it, and toggle its four orthogonal neighbors — left, right, up, down, if they exist. Goal: every light on, in at most $6$ presses. If that cannot be done, the answer is $-1$ .

A first board, then press the top-left cell, then the center:

1 0 1 1 1        0 1 1 1 1        0 1 1 1 1
0 1 1 0 1        1 1 1 0 1        1 1 0 0 1
1 0 1 1 1   →    1 0 1 1 1   →    1 1 0 0 1
1 0 0 0 0        1 0 0 0 0        1 0 1 0 0
1 1 0 1 1        1 1 0 1 1        1 1 0 1 1

Top-left hits itself, its right neighbor, and the cell below. Center hits itself and all four neighbors. The rest of the board does not move.

Input: a positive integer $n$ ( $0 < n \le 500$ ), the number of puzzles. Then $n$ blocks. Each block is five lines of five characters, each '0' or '1'. A blank line between blocks.

Output: $n$ lines. Each line is the minimum number of presses that turns that board all on, or $-1$ if it takes more than $6$ .

Sample input:

Sample output:

3
2
-1

The problem is $5 \times 5$ . I still want to talk about a general $M \times N$ board.

Plays look huge

At first I had no handle. Too many clicks.

The state is the board. Write $S$ for the set of boards, each lamp $b_{ij} \in \{0, 1\}$ . An action is one press — not a string of presses. The action space is finite:

A = \{a_{11}, a_{12}, \ldots, a_{1N}, \ldots, a_{MN}\}, \qquad |A| = MN.

The transition function $T: S \times A \to S$ sends a board and a press to the board after that press. Write $T_{a}: S \to S$ for the map $T_{a}(s) = T(s, a)$ .

A play is a sequence of actions, any length, letters reusable. That is a word over $A$ , not an element of $A$ :

(a_{i_1 j_1}, a_{i_2 j_2}, \ldots, a_{i_n j_n}), \qquad n = 1, 2, \ldots

The final state after that word is

T_{a_{i_n j_n}} \circ \cdots \circ T_{a_{i_2 j_2}} \circ T_{a_{i_1 j_1}}(s).

Countably many words: finitely many of each length, so list length $1$ , then length $2$ , then length $3$ , and so on. Still too many to brute-force. You need the two properties below.

Then two properties.

Press twice, nothing happened

Propositioninvolution

$T_{a_{ij}} \circ T_{a_{ij}} = \operatorname{id}_{S}$ . Pressing the same cell twice is the identity on states. The board does not move.

Order does not matter

Propositionactions commute

$T_{a_{ij}} \circ T_{a_{kl}} = T_{a_{kl}} \circ T_{a_{ij}}$ . Any two consecutive actions can be swapped and the final state is the same. Hence any permutation of a sequence of actions leaves the state unchanged.

Proof

If we only fire one of the two actions, there is nothing to prove. So take two presses, $a_{ij}$ and $a_{kl}$ . Pick an arbitrary lamp. Three cases.

Neither action reaches it. Swap does nothing.
Exactly one action reaches it. It still flips once, either order.
Both actions reach it. It flips twice either way, so it stays as it was.

The lamp was arbitrary, so the whole board agrees: the two maps $T_{a_{ij}} \circ T_{a_{kl}}$ and $T_{a_{kl}} \circ T_{a_{ij}}$ are equal.

Those two shrink the sequences, not $A$ . Swap until the actions sit in a fixed order — left to right, top to bottom — and cancel every double. What remains is one bit per cell:

a_{ij} \in \{0, 1\},

$0$ skip, $1$ press. A reduced plan is a matrix in $\{0,1\}^{M \times N}$ . Apply the press at $(i,j)$ exactly when $a_{ij} = 1$ , in that order. $2^{MN}$ reduced plans. $A$ was finite the whole time.

The first row kills it

One more property, and that kills it.

Propositionthe rest is forced

Once the first-row bits $a_{11}, \ldots, a_{1N} \in \{0, 1\}$ are chosen, every later $a_{ij}$ is determined if you want all lights on.

The first row is the only row you still get to choose. Everything under it is a chase.

Why. You have already chosen $a_{11}, \ldots, a_{1N} \in \{0, 1\}$ . Those presses (or skips) are done. What can still touch row $1$ ? An action on row $1$ would be going back on the choice. An action on row $3$ or lower never reaches row $1$ : it flips itself, its left and right, and the cell above it, which is still only row $2$ . The only later action that can still flip a lamp on row $1$ is the cell standing directly underneath, in row $2$ .

So each leftover $0$ on row $1$ is an order, not a puzzle. If lamp $(1,j)$ is still off, you must set $a_{2j} = 1$ . Skip it and that $0$ is dead forever. If lamp $(1,j)$ is already on, you must set $a_{2j} = 0$ : pressing would turn it off, and nothing later can save it.

That writes the whole of row $2$ . Now look at row $2$ . Same story: the only people who can still fix it live in row $3$ , directly below. And so on, down the board.

Last row: nobody lives underneath. If a $0$ is still sitting there when the chase arrives, the first-row choice was a dead end. $-1$ for that branch.

A small board, three by three. Suppose the first row is already pressed, and this is what you are looking at:

0 1 0
1 1 1
1 1 1

Row $1$ has two debts, columns $1$ and $3$ . So $a_{21} = a_{23} = 1$ . After $a_{21}$ :

1 1 0
0 0 1
0 1 1

After $a_{23}$ :

1 1 1
0 1 0
0 1 0

Row $1$ is clean. Row $2$ now owes columns $1$ and $3$ . So $a_{31} = a_{33} = 1$ . After $a_{31}$ :

1 1 1
1 1 0
1 0 0

After $a_{33}$ :

1 1 1
1 1 1
1 1 1

All on. You never chose row $2$ or row $3$ . The two zeros on top wrote the whole script.

If the last row had come out with a $0$ , that would not mean “try something else downstairs.” There is no downstairs. It would mean this first row was wrong, and you try another of the $2^{N}$ first rows.

So the thing you actually enumerate is the first row. $2^{N}$ searches. Not $2^{MN}$ . For $N = 5$ that is $32$ first rows.

I used to play this as a kid. Some little game in a browser. I clicked by feel until the lights went on. Now it is like being shown how the trick is done. Simple.

The board

A row is only five bits. I stored each row as a size_t mask, five of them in an array. Bit $0$ is the leftmost lamp — the same order print_board walks.

const int kNumRows = 5;
const int kNumCols = 5;
const int kMaxPresses = 6;
const size_t kRowAllOnMask = (1 << kNumCols) - 1;

using Board = std::array<size_t, kNumRows>;

kRowAllOnMask is 0b11111. A row is all on exactly when it equals that mask.

Building a board from five strings: if the character is '1', set that bit.

Board make_board(const std::array<std::string_view, kNumRows>& rows) {
  Board board{};
  for (size_t row = 0; row < kNumRows; ++row) {
    for (size_t col = 0; col < kNumCols; ++col) {
      if (rows[row][col] == '1') {
        board[row] |= 1 << col;
      }
    }
  }
  return board;
}

bool is_light_on(const Board& board, size_t row, size_t col) {
  return (board[row] & (1 << col)) > 0;
}

Flip, then press

One lamp: XOR the bit, written the long way. If it is on, clear it. If it is off, set it.

void flip_light(Board& board, size_t row, size_t col) {
  size_t bit_mask = 1 << col;
  if ((board[row] & bit_mask) > 0) {
    board[row] &= ~bit_mask;
  } else {
    board[row] |= bit_mask;
  }
}

A press is five flips, or fewer on the border: the cell itself, then left, right, above, below, each only if that neighbor exists.

void press_switch(Board& board, size_t row, size_t col) {
  flip_light(board, row, col);

  if (col > 0) {
    flip_light(board, row, col - 1);
  }

  if (col < kNumCols - 1) {
    flip_light(board, row, col + 1);
  }

  if (row > 0) {
    flip_light(board, row - 1, col);
  }

  if (row < kNumRows - 1) {
    flip_light(board, row + 1, col);
  }
}

Press twice at the same cell and you have $\operatorname{id}_{S}$ again. That is the involution, sitting in the code: press_switch is $T_{a}$ , its own inverse, so the first-row search can press, recurse, then press again to undo.

Chase down, enumerate the first row

Once the first row is chosen, walk rows $1$ through $4$ . If the lamp above is still off, press here. That is $a_{ij}$ forced by $b_{i-1,j}$ . If we already used more than $6$ presses, give up. When the chase ends, the last row still has to be all on — nothing sits under it to save it.

The board is passed by value. The copy is the one we wreck. The original first-row board stays.

int complete_board(Board board, int press_count) {
  for (size_t row = 1; row < kNumRows; ++row) {
    for (size_t col = 0; col < kNumCols; ++col) {
      if (!is_light_on(board, row - 1, col)) {
        press_switch(board, row, col);
        ++press_count;
        if (press_count > kMaxPresses) {
          return -1;
        }
      }
    }
  }

  if ((board[kNumRows - 1] & kRowAllOnMask) != kRowAllOnMask) {
    return -1;
  }

  return press_count;
}

First row: at column col, try press, then try skip. After a press, call press_switch again to revoke it, then go down the skip branch. When col runs off the row, chase.

int min_presses(Board& board, size_t col, int press_count) {
  if (col >= kNumCols) {
    return complete_board(board, press_count);
  }

  int min_press_count = -1;

  press_switch(board, 0, col);
  int press_count_if_pressed = min_presses(board, col + 1, press_count + 1);
  press_switch(board, 0, col);

  if (press_count_if_pressed != -1) {
    min_press_count = press_count_if_pressed;
  }

  int press_count_if_skipped = min_presses(board, col + 1, press_count);
  if (min_press_count == -1 || (press_count_if_skipped != -1 &&
                                press_count_if_skipped < min_press_count)) {
    min_press_count = press_count_if_skipped;
  }

  return min_press_count;
}

The three sample boards go in as string rows, same as the input. Answers $3$ , $2$ , $-1$ .