Lights Out 与矩阵

2026-05-19 · 3 分钟

#数学

Lights Out 游戏规则

Lights Out 是一款经典的逻辑谜题游戏。游戏面板是一个 $5 \times 5$ 的方格网格，每个方格是一个灯泡，初始状态为亮（1）或灭（0）。点击任意一个灯泡，会切换该灯泡及其上下左右四个相邻灯泡的状态（亮变灭，灭变亮）。

目标是让所有灯泡都熄灭。

问题的数学建模

将每个灯泡的状态表示为 $\mathbb{F}_2$ （模 2 域）上的变量：

$x_{i,j} \in \{0, 1\}$ ：是否点击位置 $(i, j)$ 的灯泡（1 表示点击）
$b_{i,j} \in \{0, 1\}$ ：位置 $(i, j)$ 的初始状态

点击某个灯泡产生的效果可以用一个邻接矩阵来描述。对于 $5 \times 5$ 的面板，我们将其展平为 25 个变量：

$\mathbf{x} = (x_1, x_2, \ldots, x_{25})^\top$

线性方程组可以写成：

$A \mathbf{x} = \mathbf{b}$

其中 $A$ 是一个 $25 \times 25$ 的矩阵， $A_{i,j} = 1$ 当且仅当点击 $j$ 会影响灯泡 $i$ 。

矩阵示例

对于 $3 \times 3$ 的简化面板，邻接矩阵为：

$A_{3\times3} = \begin{pmatrix} 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \ 1 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \ 0 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 \ 1 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 \ 0 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 0 \ 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 \ 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 \ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 \end{pmatrix}$

行向量与列向量

初始状态向量 $\mathbf{b}$ 也是一个列向量：

$\mathbf{b} = \begin{pmatrix} b_1 & b_2 & b_3 & b_4 & b_5 & b_6 & b_7 & b_8 & b_9 \end{pmatrix}^\top$

解向量 $\mathbf{x}$ 同样是列向量：

$\mathbf{x} = A^{-1} \mathbf{b} \quad (\text{当 } A \text{ 可逆时})$

在 $\mathbb{F}_2$ 上的高斯消元

由于所有运算都在 $\mathbb{F}_2$ 上进行（加法即 XOR），我们可以使用高斯消元法求解：

import numpy as np

def gf2_gaussian_elimination(A, b):
    """
    在 GF(2) 域上求解线性方程组 Ax = b

    参数:
        A: 方阵 (n×n), 元素为 0/1
        b: 右端项 (n,), 元素为 0/1

    返回:
        如果方程有解，返回一个特解 x (自由变量取 0)；
        如果无解，返回 None。
    """
    n = len(b)
    # 增广矩阵 [A | b]
    M = np.hstack([A, b.reshape(-1, 1)]).astype(np.uint8)

    pivot_cols = []  # 记录每个主元所在的列号
    row = 0          # 当前处理到的行（也就是秩）

    # 逐列进行消元
    for col in range(n):
        # 在当前列中，从 row 行开始寻找第一个为 1 的元素作为主元
        pivot = None
        for r in range(row, n):
            if M[r, col] == 1:
                pivot = r
                break

        # 如果该列全部为零，则是自由变量，直接进入下一列
        if pivot is None:
            continue

        # 将主元所在行交换到当前 row 行
        if pivot != row:
            M[[row, pivot]] = M[[pivot, row]]

        # Jordan 消元：将其他所有行的第 col 列都消为 0
        for r in range(n):
            if r != row and M[r, col] == 1:
                M[r] ^= M[row]

        # 记录该主元对应的列号，并增加已处理行数
        pivot_cols.append(col)
        row += 1

    # 检查是否存在矛盾方程：系数全为零，但右端项为 1
    for r in range(row, n):
        if M[r, n] == 1:
            return None  # 无解

    # 构造特解：自由变量默认为 0
    x = np.zeros(n, dtype=np.uint8)
    # 对于每个主元行，其对应的主元变量可以直接从右端项读出
    for r, c in enumerate(pivot_cols):
        x[c] = M[r, n]

    return x

矩阵乘法验证

对于任意解 $\mathbf{x}$ ，验证是否满足原始方程：

$\mathbf{b} = A \mathbf{x} \quad \text{或} \quad A \mathbf{x} + \mathbf{b} = \mathbf{0}$

如果矩阵 $A$ 的秩为 $r$ ，则解空间维数为 $n - r$ 。当 $r = n$ 时，解唯一。

内积与正交性

在 $\mathbb{F}_2^n$ 上定义内积：

$\langle \mathbf{u}, \mathbf{v} \rangle = \sum_{i=1}^n u_i v_i \pmod{2}$

两个解向量之间的差 $\mathbf{x}_1 - \mathbf{x}_2$ 属于 $A$ 的零空间：

$A(\mathbf{x}_1 - \mathbf{x}_2) = \mathbf{0}$

可解性

对于 Lights Out，一个有趣的结论是：当且仅当 $\mathbf{b}$ 与 $A$ 的左零空间正交时，方程组有解。

用公式表示：

$\forall \mathbf{y} \in \ker(A^\top): \langle \mathbf{y}, \mathbf{b} \rangle = 0$

实际游戏中的随机矩阵

除了标准 Lights Out，我们还可以生成随机谜题。对于一个随机生成的初始状态 $\mathbf{b}$ ，其可解概率取决于 $A$ 的秩。

$P(\text{可解}) = \frac{2^{\text{rank}(A)}}{2^n} = 2^{\text{rank}(A) - n}$

结语

通过将 Lights Out 建模为 $\mathbb{F}_2$ 上的线性系统，我们可以用矩阵运算和线性代数理论完全分析这个游戏。这展示了数学在游戏设计中的强大应用——将一个看似复杂的谜题转化为优雅的代数问题。

目录