# Lights Out 可解盤面判定與關卡生成：GF(2) 線性代數 > 標準 5×5 Lights Out 只有四分之一盤面可解，GF(2) 高斯消去算出 rank 23 就知道。從全暗盤面開始，每顆按鍵獨立以 1/2 機率選取，就能均勻產生可解盤面，再用最少按鍵數篩選關卡。 原文：https://sheng.page/posts/lights-out-solvable-boards-and-level-generation/ · 發布：2026-10-23 · 作者：Sheng 標準 5×5 Lights Out 按一下會翻轉自己與盤面內的上下左右鄰格，同一格翻兩次就抵消，因此可以寫成 GF(2) 上 25 個未知數的線性方程組。按鍵影響矩陣的 rank 是 23，全部 `2^25` 個盤面裡，只有 `2^23` 個可解，每個可解盤面恰有 4 組按鍵奇偶向量。 做關卡生成器時，從全暗盤面開始按，就能保證產出的盤面有解；每顆鍵獨立以 1/2 機率選取，還能在可解盤面裡均勻取樣。產出後再算最少按鍵數，留下符合目標範圍的關卡。 ## 按一下是 mod 2 加法 Lights Out 是 Tiger Electronics 在 1995 年發行的益智遊戲，標準盤面有 5×5 盞燈，目標是把燈全部關掉。按鍵效果可以寫成 [GF(2) 加法](https://raw.org/research/solving-lightsout-using-linear-algebra/)：按一格會同時翻轉該格與上下左右鄰格，超出盤面的部分不算，邊緣的按鍵影響格數因此較少。 把暗記成 0、亮記成 1，翻轉就是加 1 再取 mod 2，`1 + 1 = 0`。按同一顆鍵兩次會抵消，先按哪一顆也不影響結果，所以每顆鍵只要記「按奇數次還是偶數次」，不必保留整段操作順序。這組紀錄就是 25 維的 GF(2) 向量 `x`，其中 1 表示按奇數次，0 表示按偶數次。 盤面同樣可以寫成 25 維向量 `b`，按鍵影響則放進 25×25 矩陣 `A`，第 `i` 欄記錄按第 `i` 顆鍵會翻轉哪些格子。要把盤面關掉，就解有 25 個未知數的 `b + A·x = 0`；在 GF(2) 裡，加法與減法相同，因此等同於解 `A·x = b`。 ## 高斯消去算 rank `rank_table.py` 把矩陣每一列塞進一個 Python `int`，每個 bit 記錄對應的按鍵會不會影響這一格。標準規則的鄰接關係是雙向的，矩陣因此對稱，列與欄都能用同一個十字形建立。高斯消去時逐 bit 找 pivot，再用 XOR 消掉其他列同一位置的 1，最後找到幾個 pivot，rank 就是多少。 ```python # Lights Out as a linear system over GF(2). # Each button toggles itself and its four neighbours; a board is solvable iff it lies # in the column space of the n*n x n*n press matrix. Rank is computed by Gaussian # elimination with each matrix row packed into a Python int (one bit per cell). def rank_gf2(n): N = n * n rows = [] for i in range(N): r, c = divmod(i, n) v = 1 << i if r > 0: v |= 1 << (i - n) if r < n - 1: v |= 1 << (i + n) if c > 0: v |= 1 << (i - 1) if c < n - 1: v |= 1 << (i + 1) rows.append(v) rank = 0 for bit in range(N): pivot = next((j for j in range(rank, N) if rows[j] >> bit & 1), None) if pivot is None: continue rows[rank], rows[pivot] = rows[pivot], rows[rank] for j in range(N): if j != rank and rows[j] >> bit & 1: rows[j] ^= rows[rank] rank += 1 return rank print(f"{'board':>5} {'rank':>4} {'nullity':>7} {'solvable boards':>22} {'share':>7} {'press vectors per board':>24}") for n in range(2, 10): N = n * n r = rank_gf2(n) print(f"{n}x{n:<3} {r:4d} {N - r:7d} {2**r:22,} {100 / 2**(N - r):6.2f}% {2**(N - r):24d}") ``` ```text board rank nullity solvable boards share press vectors per board 2x2 4 0 16 100.00% 1 3x3 9 0 512 100.00% 1 4x4 12 4 4,096 6.25% 16 5x5 23 2 8,388,608 25.00% 4 6x6 36 0 68,719,476,736 100.00% 1 7x7 49 0 562,949,953,421,312 100.00% 1 8x8 64 0 18,446,744,073,709,551,616 100.00% 1 9x9 73 8 9,444,732,965,739,290,427,392 0.39% 256 ``` rank 決定這個線性映射能產出多少盤面：像空間有 `2^rank` 個元素，所以可解盤面數就是 `2^rank`。nullity 則是未知數個數減掉 rank，對 5×5 而言是 `25 - 23 = 2`。 kernel 是所有滿足 `A·q = 0` 的按鍵向量，照著其中一組按完，盤面不會改變。已知一組解 `x₀`，把它與任意 kernel 向量相加，仍會解出同一盤面；所有解也都能這樣得到，因此解集合是 kernel 的平移，每個可解盤面有 `2^nullity` 組解。[5×5 盤面](https://people.math.carleton.ca/~kcheung/math/notes/MATH1107/09/09_lights_out_soln_count.html)有 `2^23 = 8,388,608` 個可解盤面，占全部四分之一，每盤有 `2^2 = 4` 組解。 「4 組解」指按鍵奇偶向量，只記每顆鍵最後要不要按一次。若把按鍵順序或多按兩次也算成不同操作，操作序列就遠遠超過 4 組。 換盤面尺寸時，要重新算 rank，尺寸大不代表可解比例就高。4×4 的 nullity 是 4，只有 6.25% 可解；6×6 到 8×8 卻全都可解，9×9 又降到約 0.39%。 ## 用 light chasing 判定盤面是否可解 還有一個不建矩陣的解法：先決定第一列哪些鍵要按，再往下逐列處理。上一列哪一格還亮，就按它正下方的鍵，這樣能關掉上一列，也不會再動到更上面的列。第一列一旦決定，後面每列的按法就跟著確定，走到底只可能剩最後一列還亮。 第一列有 `2^5 = 32` 種按法，逐一試過，只要其中一種讓最後一列全暗，盤面就可解。在全暗盤面做同樣的事，按完仍全暗的完整按鍵向量就是 quiet pattern，也就是 kernel 的元素。`light_chasing.py` 先列出這些向量，再隨機產生 100,000 個盤面，估計可解比例： ```python # Independent cross-check without linear algebra: "light chasing". # Choose which of the 32 first-row buttons to press, then walk down the board pressing # the button under every lit cell. Only the last row can stay lit; the board is solvable # iff some first-row choice leaves it dark. On an all-dark board, the first-row choices # that leave it dark are exactly the quiet patterns (the kernel), so their count is 2^nullity. import random random.seed(42) N = 5 def press(board, r, c): for y, x in ((r, c), (r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)): if 0 <= y < N and 0 <= x < N: board[y][x] ^= 1 def chase(board, first_row): b = [row[:] for row in board] for c in range(N): if first_row >> c & 1: press(b, 0, c) for r in range(1, N): for c in range(N): if b[r - 1][c]: press(b, r, c) return not any(b[N - 1]) def quiet_pattern(first_row): # Record which buttons light chasing presses on an all-dark board for this first row. b = [[0] * N for _ in range(N)] pressed = [[0] * N for _ in range(N)] for c in range(N): if first_row >> c & 1: press(b, 0, c); pressed[0][c] = 1 for r in range(1, N): for c in range(N): if b[r - 1][c]: press(b, r, c); pressed[r][c] = 1 return None if any(b[N - 1]) else pressed dark = [[0] * N for _ in range(N)] quiet = [(f, quiet_pattern(f)) for f in range(32) if chase(dark, f)] print(f"5x5: first-row choices that keep an all-dark board dark = {len(quiet)} -> nullity = {len(quiet).bit_length() - 1}") for f, pat in quiet: weight = sum(map(sum, pat)) print(f" first row {f:05b} quiet pattern weight {weight:2d} rows: " + " ".join("".join(map(str, row)) for row in pat)) trials = 100_000 solvable = 0 for _ in range(trials): board = [[random.randrange(2) for _ in range(N)] for _ in range(N)] solvable += any(chase(board, f) for f in range(32)) p = solvable / trials ci = 1.96 * (p * (1 - p) / trials) ** 0.5 print(f"random 5x5 boards solvable: {p:.4f} +/- {ci:.4f} (linear algebra says 2^23 / 2^25 = 0.2500)") ``` ```text 5x5: first-row choices that keep an all-dark board dark = 4 -> nullity = 2 first row 00000 quiet pattern weight 0 rows: 00000 00000 00000 00000 00000 first row 01110 quiet pattern weight 16 rows: 01110 10101 11011 10101 01110 first row 10101 quiet pattern weight 12 rows: 10101 10101 00000 10101 10101 first row 11011 quiet pattern weight 12 rows: 11011 00000 11011 00000 11011 random 5x5 boards solvable: 0.2497 +/- 0.0027 (linear algebra says 2^23 / 2^25 = 0.2500) ``` 全暗盤面有 4 種首列選擇能成功，對應 4 個 quiet pattern，因此 nullity 是 2。第一組完全不按，另外三組的按鍵數分別是 16、12、12，輸出的 weight 就是在數向量裡有幾個 1。 首列 `01110` 與 `10101` 對應的完整向量 [`v₁`、`v₂`](https://raw.org/research/solving-lightsout-using-linear-algebra/)構成 kernel 的一組基底，首列 `11011` 那組則是兩者的 XOR。找到一組解後，分別加上這些非零向量，就能得到其餘解。 抽樣得到的可解比例是 `0.2497 ± 0.0027`，這個近似 95% 信賴區間包含 0.25。每個盤面試 32 種首列按法，就能判定是否可解，不必列舉全部 `2^25` 個盤面。 ## 關卡生成器能保證什麼 從全暗盤面按出一個關卡，再按一次相同的鍵就能回到全暗，因此生成時已經保證可解。哪些盤面比較容易出現，取決於按鍵的選法。 生成器 A 對每顆鍵獨立擲一次公平硬幣，決定要不要按。這讓全部 `2^25` 個按鍵向量等機率出現，而 `A·x` 對每個可解盤面恰有 4 個原像，所以每個可解盤面的機率都是 `4 / 2^25 = 1 / 2^23`。 生成器 B 固定按 `k` 次，每次均勻選一顆鍵，允許重複。盤面分布會隨 `k` 改變，無法均勻涵蓋所有可解盤面。`generator.py` 對每種設定產生 20,000 個盤面，再用 light chasing 算最少按鍵數： ```python # Two level generators for 5x5 Lights Out, both starting from the all-dark board. # A: each of the 25 buttons is pressed independently with probability 1/2. # Every board produced is solvable, and the 2^25 press vectors map 4-to-1 onto the # 2^23 solvable boards, so the boards are uniform over the solvable set. # B: press k uniformly random buttons (repeats allowed). Also always solvable, but the # distribution over boards depends on k, so there is no uniformity claim. # "Difficulty" below is the minimum number of presses among the 4 press vectors that # solve the board; it is found by trying all 32 first rows with light chasing. import random from collections import Counter random.seed(42) N = 5 def press(board, r, c): for y, x in ((r, c), (r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)): if 0 <= y < N and 0 <= x < N: board[y][x] ^= 1 def min_presses(board): best = None for first in range(32): b = [row[:] for row in board] presses = 0 for c in range(N): if first >> c & 1: press(b, 0, c); presses += 1 for r in range(1, N): for c in range(N): if b[r - 1][c]: press(b, r, c); presses += 1 if not any(b[N - 1]) and (best is None or presses < best): best = presses return best # None would mean unsolvable def gen_a(): b = [[0] * N for _ in range(N)] for i in range(N * N): if random.random() < 0.5: press(b, *divmod(i, N)) return b def gen_b(k): b = [[0] * N for _ in range(N)] for _ in range(k): press(b, *divmod(random.randrange(N * N), N)) return b trials = 20_000 for name, gen in (("A: each button w.p. 1/2", gen_a), ("B: k=3 random presses", lambda: gen_b(3)), ("B: k=10 random presses", lambda: gen_b(10))): hist = Counter() unsolvable = 0 for _ in range(trials): m = min_presses(gen()) if m is None: unsolvable += 1 else: hist[m] += 1 mean = sum(k * v for k, v in hist.items()) / trials print(f"{name:26s} unsolvable={unsolvable} mean min presses={mean:5.2f} distribution={dict(sorted(hist.items()))}") ``` ```text A: each button w.p. 1/2 unsolvable=0 mean min presses= 9.90 distribution={1: 1, 3: 6, 4: 31, 5: 116, 6: 427, 7: 1080, 8: 2333, 9: 3895, 10: 4632, 11: 3966, 12: 2416, 13: 885, 14: 184, 15: 28} B: k=3 random presses unsolvable=0 mean min presses= 2.76 distribution={1: 2429, 3: 17571} B: k=10 random presses unsolvable=0 mean min presses= 7.01 distribution={2: 148, 4: 2028, 6: 7403, 8: 8376, 10: 2045} ``` 生成時的按鍵數是最少按鍵數的上限，兩者可以相等，也可能因重複按鍵抵消，或存在更短的另一組解，而讓解題需要的按鍵更少。A 的平均最少按鍵數是 9.90，B 設 `k=3` 時是 2.76，設 `k=10` 時則是 7.01。 B 還有一個明顯限制：`k=3` 只出現最少按 1 下或 3 下的盤面，`k=10` 則全部是偶數。前面列出的非零 quiet pattern，weight 都是偶數，把其中任一組與一個解做 XOR，按鍵數的奇偶不會改變。因此同一盤面的 4 組解都具有相同奇偶，最少按鍵數也不例外；生成時按 `k` 次，即使有重複按鍵，抵消的次數也是成對扣掉，最後的奇偶必定與 `k` 相同。 ## 難度怎麼量 `min_presses` 把 32 種首列按法全部試過，從能關掉整個盤面的解裡回傳最少按鍵數。對標準 5×5 可解盤面，這等同於比較全部 4 組解。回傳 0 表示盤面原本就全暗，出關卡時要排除。 A 的最少按鍵數集中在 9 到 11 下，4 下以內的盤面很少。需要在指定步數範圍內均勻出題，就重複呼叫 `gen_a()`，把盤面交給 `min_presses`，只保留範圍內的結果，留下的盤面仍然均勻；少步數關卡適合先離線產好，免得玩家等候篩選。不要求均勻時，可以呼叫 `gen_b(k)`，用 `k` 設定可接受的按鍵數上限，再檢查實際最少按鍵數是否落在範圍內。 最少按鍵數無法反映玩家找出解法要花多久，篩完關卡後還要試玩，再用解題時間安排關卡順序。 ## 補充筆記 - 隨機填燈前先算可解比例：標準 5×5 的 rank 是 23，只有 `2^23` 個可解盤面；找最短解時要比較全部 4 組按鍵奇偶向量。 - 檢查 solver 時，可用 light chasing 試完 32 種首列按法，以 kernel 大小 4 與隨機盤面可解比例 25% 作為對照。 - 要均勻抽可解盤面，就從全暗開始，每顆鍵獨立以 1/2 機率選取；需要限制生成步數時，再考慮固定按 `k` 次。 - 固定按 `k` 次前，先確認目標最少按鍵數的奇偶能對上。 - 換盤面尺寸就重算 nullity：4×4 是 4，6×6 到 8×8 是 0，9×9 又是 8。 - 把最少按鍵數接成出題前的篩選條件，再用試玩結果調整保留範圍。 ## 延伸閱讀 - raw.org〈[Solving Lights Out Using Linear Algebra over GF(2)](https://raw.org/research/solving-lightsout-using-linear-algebra/)〉：部落格長文，介紹遊戲背景與 GF(2) 解法，列出 rank 23 和兩個 quiet pattern 向量。 - Carleton〈[Counting solutions for Lights Out](https://people.math.carleton.ca/~kcheung/math/notes/MATH1107/09/09_lights_out_soln_count.html)〉：線性代數課程講義，從 nullspace 計算解數，並列出標準 5×5 每個可解盤面恰有 4 組解。 > 想法與技術判斷出自 Sheng，和 Claude 一起起草 · 範例在 Mac 上以 Python 3.15.0 實測。