Lights Out 可解盤面判定與關卡生成：GF(2) 線性代數

標準 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) 加法：按一格會同時翻轉該格與上下左右鄰格，超出盤面的部分不算，邊緣的按鍵影響格數因此較少。

把暗記成 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 就是多少。

# 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}")

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 盤面有 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 個盤面，估計可解比例：

# 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)")

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₂構成 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 算最少按鍵數：

# 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()))}")

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。
把最少按鍵數接成出題前的篩選條件，再用試玩結果調整保留範圍。