Solution to $n$ by $n$ game of lights out

Question

How can I solve an $n$ by $n$ game of Lights Out?

Answer 1

Treat the state of the board as a vector of length $n^2$ with binary number entries: a 1 for each light that's on, a 0 for each light that's off.

Clicking on a square toggles the state of that square and its neighbors. If that's square $i$, build a vector $v_i$ that has ones in each entry corresponding to the square and its neighbors. This gives you $n^2$ vectors, $v_1, \ldots, v_N$, where $N = n^2$.

Write your starting state as a vector $w$, and then express $w$ as a linear combination of the $v_i$s, using Gaussian elimination or whatever technique you like. For each $i$ for which $v_i$ has a coefficient of $1$ in the linear combination, click on square $i$. (The order in which you click doesn't matter.)

Added example: Let's look at the 3x3 board. We'll convert a board-state (indicated by . and *, where * is "on") by reading it out row-by-row to get a vector of 0s and 1s, which I'll write without blanks. So

.**
*..
.*.

becomes

011100010

So what are v1 through v9 for this case?

v1 = 110100000
v2 = 111010000
v3 = 011001000
v4 = 100110100
v5 = 010111010
v6 = 001011001
v7 = 000100110
v8 = 000010111
v9 = 000001011

Suppose we want to solve the puzzle above, i.e., write

as linear combination of v1 through v9. Let's first do some row-reduction to the matrix consisting of v1 through v9, with the target row stuck on the bottom.

v1 = 110100000
v2 = 111010000
v3 = 011001000
v4 = 100110100
v5 = 010111010
v6 = 001011001
v7 = 000100110
v8 = 000010111
v9 = 000001011
     011100010

I use the first row to clear out the first bit in all rows below it (namely the second and 4th); to the right of my matrix I'll write another matrix indicating how each row is currently composed (i.e., when I add v1 to v2, it becomes v1 + v2, hence has "1"s in both the first and second slot to the right, like this:

 110100000  1
 001110000  11
 011001000    1
 010010100  1  1
 010111010      1
 001011001       1
 000100110        1
 000010111         1
 000001011          1
 011100010

Now I'll use the third row to kill the second entry in every row (including the bottom row). Note that on the right-hand side, this means adding 001000000 to any row that needs a 1 in the second column cleared out!:

 101101000  1 1
 001110000  11
 011001000    1
 001011100  1 11
 001110010    1 1
 001011001       1
 000100110        1
 000010111         1
 000001011          1
 000101010  ..1......

Next, I'll use the 2nd row to clear out the 3rd entry in every other row. (I could swap the 2nd and 3rd rows, but I'm not going to bother; in general, to clear out the $k$th column, I'll use the first not-yet-used row that has a "1" in its $k$th entry). I'll go ahead and do THAT step now. Note that when I used the second row to clear out another row, I need to add 110000000 to the right hand side of each row I clear out:

 100011000   11
 001110000  11
 010111000  111
 000101100  0111
 000000010  111 1
 000101001  11   1
 000100110        1
 000010111         1
 000001011          1
 000101010  ..1......

I think you get the idea. When you're all done, the bottom row will contain all zeros, and to the right will be some sequence like ..11.1111, which says that to clear out the bottom row, you need to click on lights 3, 4, 6, 7, 8, and 9. (That's just an example, not my solution to this specific instance.)

Furthermore, the v1...v9 part of the matrix on the left will have rows that are all zero except for a single 1; the stuff on the right will be instructions for how to "kill" this single 1. So if you have any other initial position, you just look at the rows corresponding to the "on" lights, add up the right-hand sides (mod 2) and click on the lights corresponding to 1s in the final result.

Answer 2

This puzzle is quite easy to solve, since it can be described by a linear $n^2 \times n^2$ equation system over the binary field $\mathbb F_2$.

Each variable corresponds to one of the $n^2$ possible switching actions, and each row describes the pattern of lights which are toggled.