Is a game of Knight's out possible?

Question

In lights out, there is a grid of cells (called lights) that can assume two states. All lights start off. You can toggle a given light, and it will automatically toggle its four neighbours. The aim of lights out is to have all lights toggled on at once.

Knights out is similar, except that the neighbours are instead the cells that are a knight's move away. Is it possible to solve all rectangular grids of knights out? Will it still be possible if the selected cell is not toggled (but the neighbours are still)? Please support your answer with relevant proofs.

Answer 1

Every Lights Out game

• where the lights have two states (on/off)
• which is reflexive (the pushed light also toggles)
• and which is symmetric (if light A is a neighbour of B, then B is a neighbour of A)

will allow you to go from all-lights on to all-lights off (and vice versa). There are several proofs. You can find two on my Lights Out page.

Another interesting question is whether every starting combination of lights on or off can be changed to the all-off state, i.e. whether every state is solvable. It is definitely not always solvable in an m×n rectangle where m and n are 6,7, or 8 modulo 9. You can see the reasons further down the same web page here. Some other rectangle sizes are always solvable (e.g. squares of sizes 2,3,4,5,10,11) others are not. There does not seem to be any easy pattern to it, but it is relatively straightforward to write a computer program to analyse each case, which is how I generated the results table on that page.

You also ask about the non-reflexive "Knights-Out" game. For sure the proof for the reflexive game does not work for the non-reflexive game. Small boards are certainly not solvable (e.g. on a 3x3 the middle light can never be toggled as it has no neighbours), but this question has not been much studied. I may dig out my computer programs and see what I get.

Edit:
In the table below are the first results from my computer program for the non-reflexive Knights Out game on any mxn rectangle with $1<m \le n<40$. A plus sign means that the all-on position can be solved, a minus means it can't. The number given is the nullity of the associated matrix, so if it says $k$ then the state of $k$ of the lights depends on the state of the other $mn-k$ lights. Only 1 in $2^k$ of the possible light patterns can be solved, and each of the solvable patterns has $2^k$ distinct solutions.

I have not yet looked more closely at the solutions to see if there are any interesting generalisable patterns in there. It does look like something interesting happens when $m=3, 9, 11, 17, 19, 25, 27, 33, 35$, where almost all the all-on rectangles are not solvable.

    m  2    3    4    5    6    7    8    9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26   27   28   29   30   31   32   33   34   35   36   37   38   39
n    ---  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---
2  | - 4
3  | - 2  - 3
4  | + 0  - 4  - 8
5  | + 2  - 5  - 4  - 5
6  | + 4  - 6  + 0  + 6  +12
7  | + 2  - 7  - 4  - 7  + 6  - 7
8  | + 0  - 8  + 0  - 8  + 0  - 8  -16
9  | - 2  - 9  + 4  - 9  - 6  - 9  - 8  - 9
10 | - 4  -10  + 8  +10  + 4  +10  + 0  -10  -20
11 | - 2  -11  + 4  -11  - 6  -11  - 8  -11  -10  -11
12 | + 0  -12  + 0  -12  + 0  -12  + 0  -12  + 0  -12  -24
13 | + 2  -13  - 4  -13  + 6  -13  - 8  -13  +10  -13  -12  -13
14 | + 4  -14  + 0  +14  +12  +14  + 0  -14  + 4  -14  + 0  +14  +28
15 | + 2  -15  - 4  -15  + 6  -15  - 8  -15  +10  -15  -12  -15  +14  -15
16 | + 0  -16  - 8  -16  + 0  -16  + 0  -16  + 8  -16  + 0  -16  + 0  -16  -32
17 | - 2  -17  - 4  -17  - 6  -17  + 8  -17  -10  -17  -12  -17  -14  -17  -16  -17
18 | - 4  -18  + 0  +18  + 4  +18  +16  -18  - 4  -18  + 0  +18  + 4  +18  + 0  -18  -36
19 | - 2  -19  - 4  -19  - 6  -19  + 8  -19  -10  -19  -12  -19  -14  -19  -16  -19  -18  -19
20 | + 0  -20  + 0  -20  + 0  -20  + 0  -20  + 0  -20  + 0  -20  + 0  -20  + 0  -20  + 0  -20  -40
21 | + 2  -21  + 4  -21  + 6  -21  - 8  -21  +10  -21  -12  -21  +14  -21  -16  -21  +18  -21  -20  -21
22 | + 4  -22  + 8  +22  +12  +22  + 0  -22  +20  -22  + 0  +22  +12  +22  + 8  -22  + 4  -22  + 0  +22  +44
23 | + 2  -23  + 4  -23  + 6  -23  - 8  -23  +10  -23  -12  -23  +14  -23  -16  -23  +18  -23  -20  -23  +22  -23
24 | + 0  -24  + 0  -24  + 0  -24  + 0  -24  + 0  -24  + 0  -24  + 0  -24  + 0  -24  + 0  -24  + 0  -24  + 0  -24  -48
25 | - 2  -25  - 4  -25  - 6  -25  - 8  -25  -10  -25  +12  -25  -14  -25  -16  -25  -18  -25  -20  -25  -22  -25  -24  -25
26 | - 4  -26  + 0  +26  + 4  +26  + 0  -26  - 4  -26  +24  +26  + 4  +26  + 0  -26  - 4  -26  + 0  +26  + 4  +26  + 0  -26  -52
27 | - 2  -27  - 4  -27  - 6  -27  - 8  -27  -10  -27  +12  -27  -14  -27  -16  -27  -18  -27  -20  -27  -22  -27  -24  -27  -26  -27
28 | + 0  -28  - 8  -28  + 0  -28  -16  -28  + 8  -28  + 0  -28  + 0  -28  - 8  -28  +16  -28  + 0  -28  + 8  -28  + 0  -28  + 0  -28  -56
29 | + 2  -29  - 4  -29  + 6  -29  - 8  -29  +10  -29  -12  -29  +14  -29  -16  -29  +18  -29  -20  -29  +22  -29  -24  -29  +26  -29  -28  -29
30 | + 4  -30  + 0  +30  +12  +30  + 0  -30  + 4  -30  + 0  +30  +28  +30  + 0  -30  + 4  -30  + 0  +30  +12  +30  + 0  -30  + 4  -30  + 0  +30  +60
31 | + 2  -31  - 4  -31  + 6  -31  - 8  -31  +10  -31  -12  -31  +14  -31  -16  -31  +18  -31  -20  -31  +22  -31  -24  -31  +26  -31  -28  -31  +30  -31
32 | + 0  -32  + 0  -32  + 0  -32  + 0  -32  + 0  -32  + 0  -32  + 0  -32  + 0  -32  + 0  -32  + 0  -32  + 0  -32  + 0  -32  + 0  -32  + 0  -32  + 0  -32  -64
33 | - 2  -33  + 4  -33  - 6  -33  - 8  -33  -10  -33  -12  -33  -14  -33  +16  -33  -18  -33  -20  -33  -22  -33  -24  -33  -26  -33  -28  -33  -30  -33  -32  -33
34 | - 4  -34  + 8  +34  + 4  +34  + 0  -34  -20  -34  + 0  +34  + 4  +34  +32  -34  - 4  -34  + 0  +34  +20  +34  + 0  -34  - 4  -34  + 8  +34  + 4  +34  + 0  -34  -68
35 | - 2  -35  + 4  -35  - 6  -35  - 8  -35  -10  -35  -12  -35  -14  -35  +16  -35  -18  -35  -20  -35  -22  -35  -24  -35  -26  -35  -28  -35  -30  -35  -32  -35  -34  -35
36 | + 0  -36  + 0  -36  + 0  -36  + 0  -36  + 0  -36  + 0  -36  + 0  -36  + 0  -36  + 0  -36  + 0  -36  + 0  -36  + 0  -36  + 0  -36  + 0  -36  + 0  -36  + 0  -36  + 0  -36  -72
37 | + 2  -37  - 4  -37  + 6  -37  + 8  -37  +10  -37  -12  -37  +14  -37  -16  -37  +18  -37  -20  -37  +22  -37  -24  -37  +26  -37  -28  -37  +30  -37  -32  -37  +34  -37  -36  -37
38 | + 4  -38  + 0  +38  +12  +38  +16  -38  + 4  -38  + 0  +38  +12  +38  + 0  -38  +36  -38  + 0  +38  +12  +38  + 0  -38  + 4  -38  +16  +38  +12  +38  + 0  -38  + 4  -38  + 0  +38  +76
39 | + 2  -39  - 4  -39  + 6  -39  + 8  -39  +10  -39  -12  -39  +14  -39  -16  -39  +18  -39  -20  -39  +22  -39  -24  -39  +26  -39  -28  -39  +30  -39  -32  -39  +34  -39  -36  -39  +38  -39

Answer 2

The first variant of Knights Out is solvable. In fact, given any network of lights where toggling a light also toggles its neighbors, it is possible to turn on all the lights! This beautiful fact requires some pretty fancy linear algebra to prove, which I have adapted from page 238 of Algebraic Combinatorics by Richard Stanley.

---

From now on, all addition and multiplication will be modulo 2.

Number the lights 1, 2, ..., n. Let $A$ be a matrix whose $i,j$ entry is equal to 1 if the pressing button i toggles light j, and 0 otherwise. This means that $A$ is symmetric and has 1s on its diagonal. Solving lights out is equivalent to finding a vector $x$ for which $Ax=\def\1{{\bf 1}}\1$, where $\1$ is the all ones vector; the vector $x$ translates into a successful switching strategy by pressing each button i for which $x_i=1$.

A standard fact from linear algebra is

Lemma: The equation $Ax=y$ has a solution $x$ if and only if $y$ is orthogonal to every vector in the null space of $A^T$.

(A vector $z$ is in the null space if $Az=\def\0{{\bf0}}\0$, and two vectors $y,z$ being orthogonal means that $y^Tz=0$.)

In light of this, assume $Az=\0$, so that $z^TAz=z^T\0=0$. Writing $A=I+B$ as the identity matrix plus a symmetric matrix $B$ with zeroes on the diagonal, we have $$ \require{cancel} 0=z^TAz=z^TIz+{z^TBz}\stackrel{1.}=z^Tz+0\stackrel{2.}=z^T\1 \tag{*} $$

1. The reason that $z^TBz=0$ is because $z^TBz=\sum_{i=1}^n\sum_{j=1}^n b_{i,j}z_iz_j$, but this sum is necessarily even (i.e. 0 mod 2) since the $i,j$ summand equals the $j,i$ summand for all $i\neq j$, while each $b_{ii}=0$.

2. The reason that $z^Tz=z^T\1$ is that $z^Tz=\sum_{i=1}^n z_i^2$, but modulo 2, it is always true $z^2=z$ (you only need to check $0^2=0$ and $1^2=1$), so $z^Tz=\sum_{i=1}^n z_i^2=\sum_{i=1}^nz_i=z^T\1$.

We have proved in (*) that $\1$ is orthogonal to every $z$ for which $Az=0$, so the Lemma implies $Ax=\1$ has a solution.