熄灯谜题

一种单人游戏，在灯的矩形格子上进行，灯可以打开和关闭。一步操作包括翻转其中一个方格内的“开关”，从而切换该方格以及所有垂直和水平相邻方格的开/关状态。从随机选择的灯光模式开始，目标是关闭所有灯。确定是否有可能从所有灯都亮的状态开始到所有灯都关闭的状态，这个问题被称为“全亮问题”。正如 Sutner (1989) 所证明的，对于正方形格子，这总是可能的 (Rangel-Mondragon)。

这可以转化为以下代数问题。

1. 每个灯的配置可以看作是一个矩阵 ，其条目在 中（即，一个 (0,1)-矩阵，其中每个 1 代表一个亮着的灯，0 代表一个关闭的灯。例如，对于 的情况，

2. 放置在 处的开关动作可以解释为矩阵加法 ，其中 是矩阵，其中唯一等于 1 的条目是那些放置在 和相邻位置的条目；本质上有三种不同类型的矩阵 ，取决于 是角条目，

边条目，

或中间条目，

3. 由于矩阵加法是可交换的，因此执行移动的顺序是无关紧要的。

4. 每个获胜的移动组合都可以用数学形式表示为

这里， 表示 零矩阵，它对应于所有灯都关闭的情况，并且每个系数 表示开关 必须按下的次数。因为我们正在求解方程（模 2），所以它们可以用等价形式写成

此外，仅考虑 0 和 1 作为 的唯一可能值就足够了。因此，上面的等式实际上是域 上未定元 中的线性方程组。

例如，对应于初始（左侧）灯光模式的系统可以写成

它有恰好一个解：(, , )，这意味着通过按下开关 , , , 和 （对应于上图中的红点）来解决游戏。由于上述方程组的矩阵具有最大秩（它是一个行列式非零的 矩阵），因此在 -格子上的游戏总是可解的。

一般来说， 格子的可解模式是那些通过按下某些开关从无灯模式获得的模式。用线性代数的语言来说，它们是作为某些矩阵 之和的 -矩阵。例如，上面说明了 -格子的可解模式。尺寸为 或更小的所有其他矩形对于每种可能的起始模式都是可解的。

有时可能存在多个解。例如，在 的情况下，从所有灯都亮到所有灯都关闭，对于全亮模式有四种可能的解，如上所示。

某些模式无解。例如，在上面显示的 模式中，不可能关闭所有灯。

正如 Sutner (1989) 所证明的，对于任何尺寸的正方形格子，从所有灯都亮到所有灯都关闭总是可能的。上面的插图显示了 到 7 的所有可能解。对于 , 2, ...，解的数量（忽略旋转和反射）为 1, 1, 1, 16, 4, 1, 1, 1, 256, 1, 64, 1, 1, 16, 1, ... (OEIS A075462)，并且要按下的按钮的相应最小数量为 1, 4, 5, 4, 15, 28, 33, 40, 25, 44, 55, 72, 105, 56, 117, ... (OEIS A075464)。因此，具有唯一解的棋盘尺寸（将通过旋转或反射具有等效解的棋盘视为不同的棋盘）为 1, 2, 3, 6, 7, 8, 10, 12, 13, 15, 18, 20, ... (OEIS A076436; Cowen and Kennedy 2000)。

移除通过旋转或反射等价的解，给出了上面所示的不同解，其中有 1, 1, 1, 5, 1, 1, 1, 1, 43, 1, 10, 1, 1, 5, 1, ... (OEIS A075463)。因此，具有唯一解的棋盘尺寸（将通过旋转或反射具有等效解的棋盘视为等价的棋盘）为 1, 2, 3, 5, 6, 7, 8, 10, 12, 13, 15, 17, 18, ... (OEIS A076437)。