ライツアウトを GF(2) の線形代数で解く — パズル全体が1本の行列方程式、5×5 の quiet pattern と可解率 1/4

古典パズル ライツアウト（セルを押すと自分＋上下左右が反転、全消灯が目標）を、GF(2) 上の線形代数ソルバー内蔵でブラウザに実装した。勘所は 3 つ: (1) パズル全体が 1 本の行列方程式 A·x = b (mod 2) になる — XOR を加算とする体 {0,1} 上では「押す」が線形で、解は押すセルの集合（順序も回数も無関係）、(2) ガウス消去の行基本変形が XOR 1 発（盤面と行を bigint のビットマスクで持つ）、(3) 5×5 は行列が特異で、null space（次元2）の "quiet pattern"、可解率 1/4、可解盤の解が常に 4 つ — を全部テストで pin した。#33 数独に続く「ソルバー内蔵パズル」第 2 弾。

🌐 ライブデモ: https://sen.ltd/portfolio/lights-out/
📦 GitHub: https://github.com/sen-ltd/lights-out

パズル全体が 1 本の方程式

セル i を押すと i と直交隣接セルが反転する。GF(2)——加算が XOR の体 {0,1}——の上では、これは完全に線形だ:

A·x = b   (mod 2)

b は現在の盤面（1=点灯）、x は押すセル、A の第 i 列はセル i を押したときの反転パターン。押す操作は可換で、同じセルを 2 度押せば打ち消し合うから、解は押すセルの集合でしかない——順序も回数も存在しない。つまりパズルを解くこと＝この連立方程式を解くことであり、それは GF(2) 上のガウス消去で機械的に終わる。

行基本変形は XOR 1 発

盤面も行列の行も bigint のビットマスクで持つ。すると mod 2 の行基本変形（行の加算）はただの XOR になる:

for (let r = 0; r < N; r++) {
  if (r !== rank && (rows[r] >> BigInt(col)) & 1n) rows[r] ^= rows[rank]; // XOR = mod-2 行演算
}

拡大係数行列 [A | b] を RREF まで潰し、ピボット変数を読み出せば解が出る。矛盾行（0 = 1）が残ればその盤面は解けないと証明付きで言える——「解けそうにない」ではなく。

5×5 は特異、という有名な話

古典の 5×5 では A が可逆でない。null space の次元は 2 で、その基底が有名な quiet pattern——押しても盤面が一切変わらない押し方の集合だ。帰結が 3 つあり、アプリでも見えるし、全部テストで pin してある:

• ランダム盤面の可解率はちょうど 1/4（パリティ制約 2 本）。テストは 400 盤をサンプリングして比率が 25% 近傍に落ちることを確認する。
• 解けない盤面は検出される。消去の最後に矛盾行が残り solve は null を返す。角 1 マスだけ点灯は古典的な不可解例。
• 可解盤の解は常に 4 つ（特殊解 + null space）。bestSolve は 4 つを列挙して最少プレス解を返す。

it('null space has dimension 2 (the famous quiet patterns)', () => {
  expect(nullBasis(5)).toHaveLength(2);
});

一方 3×3 や 4×4 では A が可逆なので全盤面が可解——同じコードがそれも証明する（nullBasis(3) は空）。サイズを切り替えると行列の顔つきが変わるのが、このパズルの面白さだ。

エンジンと殻の分離

数学はすべて src/lightsout.ts にあり DOM を参照しない。だからソルバーを直接単体テストでき、全ての解は「実際にリプレイして全消灯に到達するか」で検証している（vitest 14 ケース）。UI 側 (src/main.ts) はグリッド描画・クリック・ヒント（次の 1 手）・解の重ね表示だけの薄い殻。

src/lightsout.ts      — 純粋エンジン: 反転マスク, GF(2) 消去, null 基底, 最少プレス解, 可解盤生成
src/lightsout.test.ts — 14 ケース（リプレイ検証・quiet pattern・可解率 1/4 統計・不可解検出）
src/main.ts           — DOM 殻: グリッド・ヒント・解表示

まとめ

ライツアウトは「ゲームの全状態遷移が線形代数に畳める」気持ちよさの見本だ。方程式 1 本、XOR のガウス消去、そして 5×5 の特異性（quiet pattern・可解率 1/4・解 4 つ）まで、教科書の線形代数がそのまま遊べる形になる。#33 数独のヒントエンジンに続くソルバー内蔵パズル第 2 弾。デモで「Show solution」を押すと、緑枠のセルが GF(2) が導いた答えだ。

🌐 ライブデモ: https://sen.ltd/portfolio/lights-out/
📦 GitHub: https://github.com/sen-ltd/lights-out