Problem
A lock consists of an \(N\times N\) square of LEDs. Each LED is either off or lit. Touching one LED toggles that LED together with its horizontal and vertical neighbors. The goal is to choose a minimum-size set of LEDs to touch so that every LED is lit.
Input
- Line 1: an integer \(N\), the side length of the square.
- Next \(N\) lines: \(N\) characters each, using
.for an unlit LED and*for a lit LED.
Output
Print exactly \(N\) lines of \(N\) characters. Use X for an LED to touch and . for an LED to leave untouched. The number of touches must be minimal.
Constraints
\[ 3\leq N\leq15. \]
The test data guarantees a unique minimum solution.
Example
Input:
3
...
*..
... Output:
X..
..X
X.. Solution
This is the complement of the Lights Out problem over \(\operatorname{GF}(2)\). Let \(\mathbf{b}\) be the input board, with \(1\) for a lit LED, let \(\mathbf{p}\) describe the LEDs we touch, and let \(A\) be the action matrix. Ordinary Lights Out asks for a touch pattern that produces a target of all zeros. Here the target is the all-ones vector \(\mathbf{1}\), so
\[ \mathbf{b}+A\mathbf{p}=\mathbf{1} \quad\Longleftrightarrow\quad A\mathbf{p}=\mathbf{1}+\mathbf{b}. \]
Addition and subtraction are identical over \(\operatorname{GF}(2)\), so \(\mathbf{1}+\mathbf{b}\) is simply the bitwise complement of the input board. Gauss-Jordan elimination can solve this system, but it does not by itself choose a minimum-weight solution when \(A\) is singular. The square-grid geometry gives a smaller and more direct search.
Every Row after the First Is Forced
Assume the touches in the first row have been chosen. Once those touches are fixed, the only remaining buttons that can change the first row are the buttons directly below it. Therefore, every LED still off in the first row forces a touch in the same column of the second row. After that, every LED still off in the second row forces the corresponding touch in the third row, and so on.
Consequently, each of the \(2^N\) possible first-row masks determines at most one complete touch pattern. Trying every first row therefore examines every solution, without searching all \(2^{N^2}\) subsets of the board.
Bitmask Recurrence
Store each row in an \(N\)-bit integer. Let \(b_r\) be input row \(r\), \(p_r\) the touches in row \(r\), and \(M:=2^N-1\) the mask whose \(N\) bits are all set. Touches within one row affect that row through
\[ H(p):=p\oplus((p\ll1)\mathbin{\&}M)\oplus(p\gg1), \]
where \(\oplus\) is XOR. Once \(p_{r-1}\) and \(p_r\) are known, the state of row \(r\) before touching the row below is
\[ b_r\oplus p_{r-1}\oplus H(p_r). \]
Touching row \(r+1\) changes row \(r\) only in the corresponding columns, so the unique mask that turns row \(r\) entirely on is
\[ p_{r+1} =M\oplus b_r\oplus p_{r-1}\oplus H(p_r), \qquad p_{-1}:=0. \]
After chasing the touches downward, no row remains below the last one. A candidate is valid exactly when
\[ b_{N-1}\oplus p_{N-2}\oplus H(p_{N-1})=M. \]
Why the Result Is Optimal
Every possible solution has some first-row mask, and the recurrence reconstructs the only complete touch pattern compatible with that mask. Enumerating all \(2^N\) first rows therefore enumerates all valid solutions. Selecting the candidate with the smallest number of set bits gives the global minimum, not a local approximation.
The action matrix is singular for some allowed sizes. In those cases a solvable board can have several valid touch patterns, even though the puzzle guarantees a unique minimum. This is exactly where returning an arbitrary Gauss-Jordan solution would be insufficient.
More precisely, for \(3\leq N\leq15\), the singular sizes are \(N=4,5,9,11,14\), with nullities \(4,2,8,6,4\), respectively. A solvable board at nullity \(k\) has \(2^k\) valid touch patterns. The remaining allowed sizes have full rank and therefore at most one valid pattern.
Complexity
Each of the \(2^N\) first-row masks requires one pass through \(N\) rows:
\[ \text{time}=O(N2^N), \qquad \text{space}=O(N). \]
At \(N=15\), only \(32768\) first-row masks are examined.
Python 3 Implementation
n = int(input())
full = (1 << n) - 1
board = []
for _ in range(n):
row = input().strip()
board.append(sum((cell == "*") << col for col, cell in enumerate(row)))
def horizontal(mask):
return mask ^ ((mask << 1) & full) ^ (mask >> 1)
best = None
best_size = n * n + 1
for first_row in range(1 << n):
touches = [first_row]
for row in range(n - 1):
previous = touches[row - 1] if row > 0 else 0
current = board[row] ^ horizontal(touches[row]) ^ previous
touches.append(current ^ full)
last = board[-1] ^ horizontal(touches[-1]) ^ touches[-2]
if last != full:
continue
touch_count = sum(mask.bit_count() for mask in touches)
if touch_count < best_size:
best = touches
best_size = touch_count
for mask in best:
print("".join("X" if (mask >> col) & 1 else "." for col in range(n)))