日月離反 - atobirabon

ちょっと今回は趣味の悪い日記をやめといてライツアウトの解法について考えてみたいと思います．ちなみにライツアウトというのは10年ほど前に流行ったパズルゲームでして，5×5のマス目に配置されたボタンを押して，点灯しているボタンの明かりをすべて消したところでクリアとなります．ボタンを押すとそのボタン自身と上下左右の明かりのon/offの状態が反転します．もうすでに前時代的なゲームとなってしまったので，たいていライツアウトについて語り尽くされた感がありますが，暇なので書きます．

もし知らない人がいたら，まずはJaap's Puzzle Page/Lights Outで遊んでみるのが手っ取り早いと思います．少し下にスクロールしたところにあるJavaScript Lights Out (Classic)というリンクをクリックすれば遊べます．下の方まで歴代ライツアウトが勢揃いです．

ゲームの数学的考察についても，Jaap's Puzzle Page/The Mathematics of Lights Outが文句なしにおすすめです．徹底した分析に圧巻です．日本語では驚異のライツアウト解法ロジックというものがあるようです．プログラマー的視点で書かれてます．

で，牛刀鶏後じゃなくてなんとかというやつで，今回は先月末から惚れ込んでいるGAPという非常に強力な代数計算ソフトでライツアウトsolverを作成して*1みたわけです．それを使ってライツアウトというゲームの構造を見ていきます．

本記事は線型代数の教養（大学初年度程度；連立一次方程式の解空間及び固有値問題のさわり）レベルを読者に想定します．想定とか偉そうに言っておりますが，要するに自分がその程度だってことです．数式の嫌いな人は，はじめの「ライツアウトの万能手順」の章だけ見てください．そこを読めば誰でもライツアウトの幹部クラスになれます．ぼくは数学は好きですが苦手なので間違いを含む可能性は大いにありますのでご注意ください．

ではまず導入として，ライツアウトが確実に解ける方法を紹介する．

ライツアウトの万能手順

万能とはいっても人力で解く場合の万能である．まさかすべての解法パターンを載せて，全部暗記しろとは言わない．そのかわり，解くことが出来るすべての5×5マスの問題に対応可能な表を，今回作ったsolverを使って用意してみた．

この章をきっちりマスターすれば，きみもライツアウトの幹部クラスになれるだろう．そしてライツアウトに飽きることだろう．しかし必ずしも，というよりほとんどの場合最短手順ではないので，最短手を試行錯誤する淫靡な老後の楽しみはまだまだ残されている．そこは安心してほしい．それでも「あらゆる最短手順を制覇できなきゃ読む価値なし」と思う人は，この章のあとに「ライツアウトのマクロビオティックダイエット」の章を読むとよい．紙と鉛筆とにゅうろんさえあれば，どんな問題もその最短手順を知ることができる．そこまでマスターできれば，きみはもうライツアウトの大統領クラスだ．では解説に入る．

以下の表の一行の点灯パターン（■:on / □:off）の意味は，最下段にライトを寄せてきたときの状態をあらわしている．一番下までライトを寄せる方法は，点灯しているライトの真下を押していけば誰でも簡単にできる．できたらあとはすぐ下にある手順通りに押して解けばよい．解けるのは以下の7パターンのみで，表に当てはまらないものがでてきたら，はじめから解けない問題だったと思ってよい．

最下段にライトを追いやったときのライトの点灯位置（上）とその解法（下）
□ □ ■ ■ ■	□ ■ □ ■ □	□ ■ ■ □ ■	■ □ □ □ ■
□ □ □ ■ □ □ □ ■ ■ ■ □ ■ □ □ □ ■ ■ □ ■ ■ □ ■ □ □ □	□ □ ■ ■ ■ □ ■ □ ■ □ ■ ■ ■ □ □ □ □ □ □ □ ■ ■ ■ □ □	■ □ □ □ □ ■ ■ □ □ □ ■ □ ■ □ □ □ ■ ■ ■ □ □ □ □ □ ■	□ □ □ ■ ■ □ □ ■ □ □ □ ■ ■ □ ■ ■ □ ■ □ ■ ■ ■ □ □ □
■ ■ ■ □ □	■ ■ □ ■ ■	■ □ ■ ■ □
□ ■ □ □ □ ■ ■ ■ □ □ □ □ □ ■ □ ■ ■ □ ■ ■ □ □ □ ■ □	□ □ ■ □ □ □ ■ ■ ■ □ ■ □ □ □ ■ ■ □ ■ □ ■ □ □ ■ □ □	□ □ □ □ ■ □ □ □ ■ ■ □ □ ■ □ ■ □ ■ ■ ■ □ ■ □ □ □ □

これをいんさつしてぽけっとにでもしのばせておけば，どんなもんだいがでてきてもへっちゃら！めにもとまらぬはやさでといて，まわりのおともだちをあっといわせてやろう．さゆうがはんてんしているぱたーんは，こたえもはんてんしているだけだよ．かしこいきみならあんきもかのうだ！

にゅうろんがたりないきみにはもっとかんたんなほうほうがあるよ．

行:1-5,列:A-Eとして見たとき…

1段目で点灯中のライトの真下を押してを1段目を全部消す

2段目以降も同様にして4段目まで行い，5段目だけにライトが残るようにする*2

A5が点灯しているとき : D1とE1を押す

B5が点灯しているとき : B1とE1を押す

C5が点灯しているとき : D1を押す

手順1-5を繰り返すうちにすべてのライトが魔法のように消えます．途中で余計なことを考えてはいけません．あなたの行いが正しければ，2巡目までにすべて消えるはずです．

ライツアウトの問題設定

唐突だが，ライツアウトは有限体 $\mathbb{F}_2$ *3上で，
${\Large A{\bf x}+{\bf b}={\bf o}}$
の形の非同次方程式を解く問題である*4．具体的に，m×nの盤面の総数mn個のボタンそれぞれに左上から右下まで行ごとに1,2,3,...,mnと番号をつけていったとき，この ${\bf b} \in \mathbb{F}_2^{mn}$ は与えられた問題を表すmn次元列ベクトルで，それぞれのon/offの状態が1/0に対応しているものである． ${\bf x} \in \mathbb{F}_2^{mn}$ も同様の対応で，それぞれのボタンを押す回数を示す同次元の列ベクトルである．実際はボタンを2回押せば元の状態に戻るので，その要素は"1:押す"か"0:押さない"の値しかとらない*5ことがわかる． ${\bf o}$ は全消灯の状態を示す同次元の零ベクトルである．そして $A$ は，盤面に対するライトのon/offの作用を1/0で表したmn×mn行列である．これらの性質のため，問題を $\mathbb{F}_2$ の中で扱えば非常に都合がよくなる．言葉ではよく分からないと思われるので簡単な2×2の実例を見てみる．

2×2ライツアウト
1	2
3	4

赤い部分が点灯しているボタンを示す．当然，我々がやるべきことは ${\bf b}=\left(\begin{array}{cccc}1&0&1&1\end{array}\right)^{\mathrm T}$ を全部消す $\left(\begin{array}{cccc}0&0&0&0\end{array}\right)^{\mathrm T}$ ことである．この場合 $A{\bf x}+{\bf b}={\bf o}$ は以下のように書ける．
$\large{\left(\begin{array}{ccc} 1&1&1&0\\1&1&0&1\\1&0&1&1\\0&1&1&1\\ \end{array}\right)\left(\begin{array}{l} x_1\\x_2\\x_3\\x_4\\ \end{array}\right) + \left(\begin{array}{l} 1\\0\\1\\1 \end{array}\right) = \left(\begin{array}{l} 0\\0\\0\\0 \end{array}\right)}$

Aを行ごとに見てもらえばわかるが，1行目は左上のボタン-1を押したときの盤面全体への作用，つまりライトが反転するボタン-1,2,3は1，影響しないボタン-4は0で表されているものである．2行目も同様にボタン-2を押したときで，3行目以降も同じである．グラフ理論を知っているなら，Aはボタンへの作用をノードへのリンクとして表現した隣接行列だと見てもらえばよい．盤面との対応がわかりやすいよう，もう少し計算を進める． $\mathbb{F}_2$ の演算は下表の通りである．

$\mathbb{F}_2$ の加法（左）と乗法（右）
+	0	1		*	0	1
0	0	1		0	0	0
1	1	0		1	0	1

$\large{\left(\begin{array}{l} x_1+x_2+x_3\\x_1+x_2+x_4\\x_1+x_3+x_4\\x_2+x_3+x_4\\ \end{array}\right) + \left(\begin{array}{l} 1\\0\\1\\1 \end{array}\right) = \left(\begin{array}{l} 0\\0\\0\\0 \end{array}\right)}$

${\bf x}$ が示すボタンをすべて押し終えたときのボタン-1の状態は，ボタン-1,2,3を押した回数に依存した結果 $x_1+x_2+x_3+1$ である．これが0なら消えている状態である．これを満たす ${\bf x}$ を見つけることは，上の方程式を解いていることに他ならない． $A{\bf x}$ の内容を ${\bf b}$ に一致させれば ${\bf b}+{\bf b}={\bf o}$ である．

$\large{\left{\begin{eqnarray} x_1+x_2+x_3&=&1\\x_1+x_2+x_4&=&0\\x_1+x_3+x_4&=&1\\x_2+x_3+x_4&=&1\\ \end{eqnarray}\right.$

こんなややこしいことをせずとも，問題を見ればひと目で解は明らかに ${\bf x}=\left(\begin{array}{cccc}0&0&1&0\end{array}\right)^{\mathrm T}$ であるので，ひとまず解が直感と一致することを確かめてみればよい．また，det(A)=1と正則なので ${\bf x}=A^{-1}{\bf b}$ を計算しても解が求まる．2×2の場合はたまたま $A^{-1}=A$ である*6．

$\large{{\bf x}=A^{-1}{\bf b}=\left(\begin{array}{ccc} 1&1&1&0\\1&1&0&1\\1&0&1&1\\0&1&1&1\\ \end{array}\right)}\left(\begin{array}{l} 1\\0\\1\\1 \end{array}\right)=\left(\begin{array}{l} 1+0+1+0\\1+0+0+1\\1+0+1+1\\0+0+1+1 \end{array}\right)=\left(\begin{array}{l} 0\\0\\1\\0 \end{array}\right)$

すべてのm×nのゲームで行列Aが正則なら，どんな問題に対しても解は必ずuniqueに定まる．偉そうな言い方をすれば，線型写像が全単射であり，すべての問題と解が一対一に対応するということである．もしそうなら何も苦労することはないが，それほど都合のよいゲームではない．実は，ライツアウトの標準的なサイズである5×5は解に自由度があり，問題とその解が1対4の対応となっている*7．同時に，これは解が存在しない問題もあるという事実を示している．次の章からは，この点に着目してその構造を探る．

ライツアウトのヌルスペ

ライツアウトというゲームのまさに“核”をなす性質をこの章で述べる．以降では，特に断らない限り5×5のライツアウトについて述べることにする．

一般に，このゲームのような関係を表すAをブロック行列として見ると，n×n三重対角行列Tとn×n単位行列Iのブロックをm×mグリッドの三重対角線上に配置した，

${\Large A=\left(\begin{array}{CCCCCCC}T&I&&&&&\\I&T&I&&&\\&I&T&I&&&&\\&&\vdots&&&&\\&&I&T&I&&\\&&&I&T&I&\\&&&&&I&T\end{array}\right)$

となる形をしている．具体的に5×5の場合の $A$ を以下にライトのパターンとして示す．

5×5ライツアウトのA
■ ■ □ □ □ ■ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ■ ■ ■ □ □ □ ■ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ■ ■ ■ □ □ □ ■ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ■ ■ ■ □ □ □ ■ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ■ ■ □ □ □ □ ■ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ■ □ □ □ □ ■ ■ □ □ □ ■ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ■ □ □ □ ■ ■ ■ □ □ □ ■ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ■ □ □ □ ■ ■ ■ □ □ □ ■ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ■ □ □ □ ■ ■ ■ □ □ □ ■ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ■ □ □ □ ■ ■ □ □ □ □ ■ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ■ □ □ □ □ ■ ■ □ □ □ ■ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ■ □ □ □ ■ ■ ■ □ □ □ ■ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ■ □ □ □ ■ ■ ■ □ □ □ ■ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ■ □ □ □ ■ ■ ■ □ □ □ ■ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ■ □ □ □ ■ ■ □ □ □ □ ■ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ■ □ □ □ □ ■ ■ □ □ □ ■ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ■ □ □ □ ■ ■ ■ □ □ □ ■ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ■ □ □ □ ■ ■ ■ □ □ □ ■ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ■ □ □ □ ■ ■ ■ □ □ □ ■ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ■ □ □ □ ■ ■ □ □ □ □ ■ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ■ □ □ □ □ ■ ■ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ■ □ □ □ ■ ■ ■ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ■ □ □ □ ■ ■ ■ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ■ □ □ □ ■ ■ ■ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ■ □ □ □ ■ ■

見ての通りAは，ボタン総数mn=25で25×25の対称行列である．また， ${\bf x}, \quad {\bf b} \in \mathbb{F}_2^{25}$ である．この場合det(A)=0であり逆元が存在しない．つまり解は問題次第で，不定（解が複数存在する）または不能（解けない）になる．続いてGAPでAの階数(rank)を計算してみるとrank(A)=23で，2本のベクトルが余分（線型従属）であることがわかる．この事実から， $\mathbb{F}_2^{25}$ の部分空間となるAのカーネル（零空間;null space）
${\large {\mathrm Ker}A=\{{\bf x} \in \mathbb{F}_2^{25} | A{\bf x}={\bf o}\}$
の次元はdim(KerA)=25-23=2であることがわかる．ただ空間といっても有限体であるので，2つの基底の線型和はそれぞれ使うか使わない場合の組み合わせ数を考えるだけで，元の総数はたったの $|{\mathrm Ker}A|=2^2=4$ である．KerAのすべての元は零元を除けば全部で以下の3つ．

KerAの零元を除くすべての元
■ ■ □ ■ ■ □ □ □ □ □ ■ ■ □ ■ ■ □ □ □ □ □ ■ ■ □ ■ ■	■ □ ■ □ ■ ■ □ ■ □ ■ □ □ □ □ □ ■ □ ■ □ ■ ■ □ ■ □ ■	□ ■ ■ ■ □ ■ □ ■ □ ■ ■ ■ □ ■ ■ ■ □ ■ □ ■ □ ■ ■ ■ □

これらのパターンを左から ${\bf q}_1,{\bf q}_2,{\bf q}_3$ と名付ける．ただし ${\bf q}_1,{\bf q}_2$ はKerAの線型独立な2つの元，つまり基底で， ${\bf q}_3$ だけはそれらの線型結合 ${\bf q}_3={\bf q}_1+{\bf q}_2$ であることに注意．実はこれら3つのパターンが，ライツアウトの解法において非常に重要な役割を果たす．他のサイトで"quiet patterns"や「0解」などと呼ばれているのは，まさにこのKerAのことである．

非同次方程式 $A{\bf x}+{\bf b}={\bf o}$ の解 ${\bf x}$ は， $A{\bf c}+{\bf b}={\bf o}({\bf b} \neq {\bf o})$ を満たす特殊解 ${\bf c}$ とKerAの任意の元 ${\bf q}_k$ の線形結合で表せる．便宜上，零ベクトルを ${\bf q}_0$ として ${\bf q}_k$ に含めたとすれば，特殊解 ${\bf c}$ が存在する場合に $A{\bf x}+{\bf b}={\bf o}$ の解は，以下のように4通りの解として簡単に書ける．

$\large{{\bf x}={\bf c}+{\bf q}_k \quad (k=0,1,2,3)}$

$\forall {\bf q}_k \in {\mathrm Ker}A, \quad A{\bf q}_k={\bf o}$ が成り立つので，
${\large A{\bf x}+{\bf b}=A({\bf c}+{\bf q}_k)+{\bf b}={\bf b}+{\bf o}+{\bf b}={\bf o}}$
であり，たしかに解である．また，任意のライトパターン ${\bf d}$ のとき，どの ${\bf q}_k$ のパターンを押しても，

${\large A{\bf q}_k+{\bf d}={\bf o}+{\bf d}={\bf d}}$

であるので，ボタンを何も押さなかった場合と同じになる．実際には， ${\bf q}_k$ のボタンを押せば，すべてのライトに対して偶数回スイッチが作用していることになるので，ライトパターンは不変である．

便利なことに，KerAのパターンは与えられた問題が解けるかどうかの簡単なチェックにも使える．

theorem-1:
対称なゲーム $A$ において，ある問題 ${\bf b}$ が与えられたとき，
(i) すべての ${\bf q} \in {\mathrm Ker}A$ に対し ${\bf q}^{\mathrm T}{\bf b}=0$ が成り立つ．
$\Longleftrightarrow$ 問題 ${\bf b}$ を解く ${\bf x}$ が存在する．
(ii) ${\bf q}^{\mathrm T}{\bf b}\neq 0$ となる ${\bf q}$ が，少なくとも１つ存在する．
$\Longleftrightarrow$ 問題 ${\bf b}$ を解く ${\bf x}$ は存在しない．

これは5×5ライツアウトに限らず一般に成り立つ．対称なゲーム $A$ というのは， $A$ が対称行列であることを言っている*8．これは5×5に限らず，任意のpでm×nのライツアウト一般に成り立つ．この性質は $A=A^{\mathrm T}$ の対称性に依るものである

(i)について、十分条件は明らかなので必要条件を示す。
proof:
${\large W=\{ {\bf w} \in \mathbb{F}_p^{mn} | \forall {\bf q} \in {\mathrm Ker} A : {\bf q}^{\mathrm T}{\bf w} = 0 \}}$

上記の性質を満たす集合を考える．この $W$ は任意の係数 $\alpha,\beta$ と， ${\bf w}_1,{\bf w}_2 \in W$ に対して，

${\large {\bf q}^{\mathrm T}(\alpha{\bf w}_1 + \beta{\bf w}_2)=0}$

がいえるので $\mathbb{F}_p^{mn}$ の部分空間となる．

$A{\bf q}=A^{\mathrm T}{\bf q}={\bf o}$ より， $\forall {\bf y} \in {\mathrm Im}A$ に対し，
${\bf y}^{\mathrm T}{\bf q}={\bf q}^{\mathrm T}{\bf y} = 0$ が成り立つので ${\mathrm Im} A \subset W$ が言える．

また、 ${\mathrm dim}(W) = {{\mathrm dim}({\mathrm Im} A) = {\mathrm dim}(\mathbb{F}_p^{mn}) - {\mathrm dim}({\mathrm Ker} A)$
より、 $W = {\mathrm Im}A$ が言える。

$W = {\mathrm Im}A$ より， $A{\bf x}+{\bf b}$ において， ${\bf b} \in W$ ならば， $-{\bf b} \in W={\mathrm Im}A$ なので， $A{\bf x}=-{\bf b}$ となるような ${\bf x}$ を選び， $A{\bf x}+{\bf b}={\bf o}$ にできる．

以上より，ある問題 ${\bf b}$ が与えられたときの $A{\bf x}+{\bf b}={\bf o}$ の解 ${\bf x}$ の存在は ${\bf b} \in W$ と同値であることが示せた．(ii)は(i)と同じ内容である．

■

念のため確認しておくが，実際はすべての ${\bf q} \in {\mathrm Ker}A$ について積 ${\bf q}^{\mathrm T}{\bf b}$ をしらみつぶしに調べる必要はない．すべての基底について ${\bf b}$ との積がすべて0になることさえ確認すれば，それら基底の任意の線型和との積も必ず0である．5×5の例で示すなら，

${\bf q}_1^{\mathrm T}{\bf b}=0,\quad{\bf q}_2^{\mathrm T}{\bf b}=0 \qquad \Rightarrow \qquad {\bf q}_3^{\mathrm T}{\bf b}=({\bf q}_1^{\mathrm T}+{\bf q}_2^{\mathrm T}){\bf b}={\bf q}_1^{\mathrm T}{\bf b}+{\bf q}_2^{\mathrm T}{\bf b}=0$

パズルを解く際にはあまり有用ではないかもしれないが，以下の定理も示しておく．

theorem-2:
どんなm×nライツアウトも，すべてのライトがonのときは必ず解ける．

Aが正則であるものについては解を持つことが明らかなので，Aが正則でないものについて証明する．その下準備として，

lemma:
${\bf q} \in {\mathrm Ker}A$ はどれも $q_i=1$ となる成分を必ず偶数個含む．

proof:
1,2,...,i,...,mn個の中のあるi番目のボタンについて考える．

すべてボタンを押し終えたとき，i番目のボタンのライトが消えているためには，i番目のボタンとその上下左右に隣接するボタンが押された回数が偶数回（通常ライツアウトの場合は0,2,4回のいずれか）でなければならない．

上記は，あるi番目のボタンにスイッチが作用した回数の総和，つまり $A{\bf q}$ のi行目の要素 $(A{\bf q})_i$ のことであり，これが
${\large (A{\bf q})_i={\sum_{j=1}^{mn}a_{ij}x_j=\underbrace{1+1+\cdots+1}_{\text even(0 or 2 or 4)}=0}}$
となることを言っている．これがすべてのiで成り立っているので $A{\bf q}= {\bf o}$ である．

ならば，もしある ${\bf q}$ の成分 $q_i$ が1であったとき，i番目のボタンの四方に隣接する奇数個のボタンも押されているはずである．

この関係を捉えるため， ${\bf q}$ の中で1を持つ成分の添え字を集めた集合
${\large V=\{ i | A{\bf q}= {\bf o}, \quad q_i=1\}}$
をつくる．また $V$ の元の総数を $|V|$ と書くことにする．

上記のような集合 $V$ の要素をそれぞれ接点(vertices)と見なしてボタンの隣接関係を辺(edges)としてあらわす無向グラフ $G=\{V,E\}$ を作ったとき，すべての接点で奇数個の辺を持つグラフの形が得られる．

これらすべての辺の総数 $|E|$ を数えることにする．
ある接点 $i \in V$ が持つ奇数個の辺の数を $2\alpha_{i}-1$ とすると，
${\large |E| = \frac{1}{2} {\sum_{V}(2\alpha_{i}-1)}}$
である．前に1/2が付いているのは重複して数えた分を除くためである．辺の総数は必ず整数なので， ${\sum_{V}(2\alpha_{i}-1)}$ は2で割り切れるはずである．奇数同士の和が2で割り切れるためには，接点の総数 $|V|$ が必ず偶数でなければならない．

したがって ${\bf q}$ の中で $q_i=1$ となる成分の総数は偶数個である．

lemmaより，
すべてのライトがon，つまり与えられた問題が ${\bf b}=\left(\begin{array}{cccc}1&1&\cdots&1\end{array}\right)^{\mathrm T}$ ならば，
${\large{\forall {\bf q} \in {\mathrm Ker}A: \quad {\bf q}^{\mathrm T}{\bf b}=\underbrace{1+1+\cdots+1}_{\text even}=0}$
が成り立つ．よって，theorem-1の(i)に示した条件を満たす．

問題が全点灯（ライトがすべてon）ならどんなm×nライツアウトでも解を持つ．

■

（もっとスマートに書ければよいがなんともくどい証明）

以上の事実を特に5×5ライツアウトに関するものとしてまとめると，

解をひとつ見つけたとき，KerAの3つのパターンを足しあわせれば4通りのすべての解がつくれる．

問題と解が1対4対応となることから，解ける問題の総数は $2^{25}/4=2^{23}=8388608$ である．これはrank(A)=23であることからも明らかで，5×5の盤面で反転可能なパターンとは，23の線型独立なベクトルの $2^{23}$ 通りの線型和のことである．

どの ${\bf q} \in {\mathrm Ker}A$ のパターンを押しても状況を変えない．

KerAのすべての基底と問題 ${\bf b}$ の積 ${\bf q}^{\mathrm T}{\bf b}$ がすべて0であれば解がある．もし，どれかひとつでも0でないものがあれば解けない問題である．

上記の判定方法はどちらかといえばコンピュータ向けであるので，人の目でやる場合は，（結局同じを計算をしていることになるが）KerAのパターンの左からふたつ ${\bf q}_1,{\bf q}_2$ を見ながら，与えられた問題のパターンと重なる部分の個数を数え，すべて偶数個なら解ける，また，どれか一つでも奇数個になるパターンがあったら解けないものと判定すればよい．

どんなm×nライツアウトでもすべてのライトがonなら必ず解ける．

これだけ重要な事実がKerAからわんさか掘り出せるのだから，よっぽどのことである．

ライツアウトのマクロビオティックダイエット

ここまではこんぴゅーたーをふんだんに使いましたが，この章はあくまで人力解答にこだわります．紙と鉛筆とにゅうろんを用意してください．いそふらぼんはいりません．

5×5のライツアウトで，ある解をひとつ見つければ，あとはKerAの3つのパターンを足しあわせることですべての解が表せることは前の章で述べた．つまり，最初の章で紹介した万能手順と，前章の方法を併せて使えばよい．

まず，万能手順で解を1つ見つけ，それにKerAの3パターンを足したものの中で，最短のものを選ぶというのがおおまかな流れである．実に単純明快である．一応具体的な方法を述べるが，工夫次第でもっと効率のよいやり方があるかもしれない．

1. 5×5のマス目を紙に書く．
2. 万能手順のいずれかの方法を使ってすべてのライトを消す．
3. そのとき押したボタンに対応するマスに正の字なりを書いて押した回数を記録しておく．
4. 奇数回だったマスをすべて塗りつぶす（これが４つの解のひとつ）．
5. 手元のマス目とKerAの3つのパターンを重ねて比較する．
6. 「塗りつぶしたマスに重なる個数」から「塗りつぶしていないマスに重なる個数」を引く．これを３つのKerAのパターンについて計算．（慣れれば一番重なる部分が多くなりそうなものだけやってもよい）
7. 計算結果が一番大きくなるものをひとつ選び（0以下なら最初の解が最短），重ねた部分を反転させれば最短手順完成．

おそらくないが，暇と要望があれば図解入りにするかもしれない．

ライツアウトのアイスペ

ほかに，興味深い現象として問題 ${\bf b}$ とその解 ${\bf x}$ が同じになる，つまり最初に点灯していたボタンを押すだけで解けてしまうパターンがある．これを考えてみることにしよう．この問題は $A{\bf x}+{\bf x}={\bf o}$ の解 ${\bf x}$ を求めることに相当し，当然 ${\bf x}={\bf o}$ （最初から全部消えている状態）はその自明な解のひとつである．

式を見て分かる通り，これは $A{\bf x}=\lambda{\bf x}$ で $\lambda=-1$ のときの固有ベクトルを求める問題そのものである．したがってこの解空間Ker(A+I)とは， $A$ の固有値 $\lambda=-1$ に対応する固有空間 $E_A(-1)$ のことである． $E_A(-1)$ に属するものを「固有反転パターン」のと呼ぶことにする．

任意の固有反転パターン ${\bf p} \in E_A(-1)$ を使えば $A{\bf p}=-{\bf p}$ として ${\bf p}$ を反転したパターンが現れる．ということは，もし問題 ${\bf b}={\bf p}$ であったなら
${\Large A{\bf p}+{\bf p}=-{\bf p}+{\bf p}={\bf o}}$
となるので，最初にライトが点いていた部分を押すだけで解ける．またもし現在の盤面のライトの状態がある ${\bf d}$ であったとき，
${\Large A{\bf p}+{\bf d}=-{\bf p}+{\bf d}}$
となる．これはつまり， ${\bf d}$ の固有反転パターン ${\bf p}$ にあたる部分の点灯状態を，他の部分に影響を与えることなくそっくりそのまま反転できるということである．

$E_A(-1)$ のすべての元は，以下の5パターン（基底）の $2^5=32$ 通りの組み合わせ（線型和）で作れる．自明な解となる零ベクトル除けば全部で31通りある．

${\tiny E_{A}(-1)}$ の5つの基底
□ □ □ □ ■ □ □ □ ■ □ □ □ ■ □ □ □ ■ □ □ □ ■ □ □ □ □	□ □ □ ■ □ □ □ ■ □ ■ □ ■ □ ■ □ ■ □ ■ □ □ □ ■ □ □ □	□ □ ■ □ □ □ ■ □ ■ □ ■ □ ■ □ ■ □ ■ □ ■ □ □ □ ■ □ □	□ ■ □ □ □ ■ □ ■ □ □ □ ■ □ ■ □ □ □ ■ □ ■ □ □ □ ■ □	■ □ □ □ □ □ ■ □ □ □ □ □ ■ □ □ □ □ □ ■ □ □ □ □ □ ■

${\tiny E_{A}(-1)}$ の零元を除く31通りのすべての固有反転パターン
□ □ □ □ ■ □ □ □ ■ □ □ □ ■ □ □ □ ■ □ □ □ ■ □ □ □ □	□ □ □ ■ □ □ □ ■ □ ■ □ ■ □ ■ □ ■ □ ■ □ □ □ ■ □ □ □	□ □ □ ■ ■ □ □ ■ ■ ■ □ ■ ■ ■ □ ■ ■ ■ □ □ ■ ■ □ □ □	□ □ ■ □ □ □ ■ □ ■ □ ■ □ ■ □ ■ □ ■ □ ■ □ □ □ ■ □ □	□ □ ■ □ ■ □ ■ □ □ □ ■ □ □ □ ■ □ □ □ ■ □ ■ □ ■ □ □
□ □ ■ ■ □ □ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ □ □ ■ ■ □ □	□ □ ■ ■ ■ □ ■ ■ □ ■ ■ ■ □ ■ ■ ■ □ ■ ■ □ ■ ■ ■ □ □	□ ■ □ □ □ ■ □ ■ □ □ □ ■ □ ■ □ □ □ ■ □ ■ □ □ □ ■ □	□ ■ □ □ ■ ■ □ ■ ■ □ □ ■ ■ ■ □ □ ■ ■ □ ■ ■ □ □ ■ □	□ ■ □ ■ □ ■ □ □ □ ■ □ □ □ □ □ ■ □ □ □ ■ □ ■ □ ■ □
□ ■ □ ■ ■ ■ □ □ ■ ■ □ □ ■ □ □ ■ ■ □ □ ■ ■ ■ □ ■ □	□ ■ ■ □ □ ■ ■ ■ ■ □ ■ ■ ■ ■ ■ □ ■ ■ ■ ■ □ □ ■ ■ □	□ ■ ■ □ ■ ■ ■ ■ □ □ ■ ■ □ ■ ■ □ □ ■ ■ ■ ■ □ ■ ■ □	□ ■ ■ ■ □ ■ ■ □ ■ ■ ■ □ ■ □ ■ ■ ■ □ ■ ■ □ ■ ■ ■ □	□ ■ ■ ■ ■ ■ ■ □ □ ■ ■ □ □ □ ■ ■ □ □ ■ ■ ■ ■ ■ ■ □
■ □ □ □ □ □ ■ □ □ □ □ □ ■ □ □ □ □ □ ■ □ □ □ □ □ ■	■ □ □ □ ■ □ ■ □ ■ □ □ □ □ □ □ □ ■ □ ■ □ ■ □ □ □ ■	■ □ □ ■ □ □ ■ ■ □ ■ □ ■ ■ ■ □ ■ □ ■ ■ □ □ ■ □ □ ■	■ □ □ ■ ■ □ ■ ■ ■ ■ □ ■ □ ■ □ ■ ■ ■ ■ □ ■ ■ □ □ ■	■ □ ■ □ □ □ □ □ ■ □ ■ □ □ □ ■ □ ■ □ □ □ □ □ ■ □ ■
■ □ ■ □ ■ □ □ □ □ □ ■ □ ■ □ ■ □ □ □ □ □ ■ □ ■ □ ■	■ □ ■ ■ □ □ □ ■ ■ ■ ■ ■ □ ■ ■ ■ ■ ■ □ □ □ ■ ■ □ ■	■ □ ■ ■ ■ □ □ ■ □ ■ ■ ■ ■ ■ ■ ■ □ ■ □ □ ■ ■ ■ □ ■	■ ■ □ □ □ ■ ■ ■ □ □ □ ■ ■ ■ □ □ □ ■ ■ ■ □ □ □ ■ ■	■ ■ □ □ ■ ■ ■ ■ ■ □ □ ■ □ ■ □ □ ■ ■ ■ ■ ■ □ □ ■ ■
■ ■ □ ■ □ ■ ■ □ □ ■ □ □ ■ □ □ ■ □ □ ■ ■ □ ■ □ ■ ■	■ ■ □ ■ ■ ■ ■ □ ■ ■ □ □ □ □ □ ■ ■ □ ■ ■ ■ ■ □ ■ ■	■ ■ ■ □ □ ■ □ ■ ■ □ ■ ■ □ ■ ■ □ ■ ■ □ ■ □ □ ■ ■ ■	■ ■ ■ □ ■ ■ □ ■ □ □ ■ ■ ■ ■ ■ □ □ ■ □ ■ ■ □ ■ ■ ■	■ ■ ■ ■ □ ■ □ □ ■ ■ ■ □ □ □ ■ ■ ■ □ □ ■ □ ■ ■ ■ ■
■ ■ ■ ■ ■ ■ □ □ □ ■ ■ □ ■ □ ■ ■ □ □ □ ■ ■ ■ ■ ■ ■

References: ライツアウトの参考資料たち

Jaap's Puzzle Page/The Mathematics of Lights Out

http://www.geocities.com/jaapsch/puzzles/lomath.htm

Setting Switches in a Grid (1995) / J. Goldwasser, W. Klostermeyer, G. Trapp, and C.-Q. Zhang

http://citeseer.ist.psu.edu/goldwasser95setting.html

驚異のライツアウト解法ロジック

http://www.ic-net.or.jp/home/takaken/nt/light/light2.html

Lights Out VB clone

http://dalila.sip.ucm.es/~cpareja/lo/

Appendix-1: ライツアウトの残尿感

そろそろ疲れてきた．でもまだここで扱いきれなかった話題はいくつもある．

消灯→赤→緑→消灯→赤→…の3状態をとるようなライツアウト

単に $\mathbb{F}_3$ の上で連立方程式を解いてやるだけです．5状態，7状態だろうと解けます．が，例えば $p=4$ など $p$ が素数でない場合は面倒だったのでもう無視してます．

m×nライツアウトの一般化

任意のm×nゲームを解くだけならたいした仕事ではありません． $A^{-1}$ が存在するなら楽に解けますし，存在しない場合も複数の解を求めればよいだけです．理論面での一般化路線として，mとnをパラメータとする解の存在条件や自由度，また最短手順などに関するライツアウト定理を打ち立てるようなことは，ぼくには力不足で到底できません．このあたり興味のある人はJaapsのページを見てください．

群論やグラフ理論を駆使した分析

勉強不足です．

Appendix-2: ライツアウトの旅路の果て

あまり大規模なライツアウトに挑戦しようとすると，パズルの楽しみなどどうでもよくなり，ただ解の幾何学紋様を眺めることだけが唯一の（uniqueな）楽しみになってきます．また，ライトの状態が3〜7段階ともなると，解の模様を塗り分けてプリントして部屋に飾っておきたくなります．そこで，興味深い現象を最後にひとつ紹介しておわりにしようと思います．塗り分けが面倒なのでカラフルなものは紹介しません．

9×3ライツアウトの ${\tiny{A^{-1}}$
■ □ ■ □ □ ■ ■ ■ □ □ □ □ ■ ■ □ □ □ ■ ■ □ ■ ■ □ □ □ ■ ■ □ □ □ □ ■ □ ■ ■ ■ □ □ □ ■ ■ ■ □ ■ □ □ □ □ □ ■ □ ■ ■ ■ ■ □ ■ ■ □ □ □ ■ ■ □ □ □ □ ■ ■ ■ □ □ ■ □ ■ □ □ ■ ■ ■ □ □ □ ■ □ ■ ■ □ □ ■ □ □ □ □ □ ■ □ ■ ■ ■ □ ■ ■ ■ □ ■ □ □ □ ■ □ ■ ■ ■ □ ■ □ □ □ □ □ ■ □ ■ ■ ■ □ □ □ ■ ■ ■ □ ■ □ ■ □ □ ■ ■ □ ■ □ □ □ □ □ ■ □ □ ■ ■ □ ■ □ ■ □ ■ ■ □ □ ■ ■ ■ □ □ □ ■ ■ □ ■ □ □ □ ■ □ ■ ■ □ ■ □ □ □ ■ □ ■ ■ □ ■ ■ ■ ■ □ ■ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ■ ■ ■ □ □ ■ □ ■ □ □ □ ■ □ ■ ■ □ ■ □ □ □ ■ □ ■ ■ □ ■ □ □ □ □ □ □ □ □ □ □ □ □ ■ □ □ ■ ■ □ ■ □ ■ □ ■ ■ □ □ ■ □ □ □ □ □ □ □ □ □ □ □ □ □ ■ □ ■ ■ ■ □ □ □ ■ ■ ■ □ ■ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ■ □ ■ ■ ■ □ ■ ■ ■ □ ■ □ □ ■ ■ □ □ □ ■ ■ □ ■ ■ □ □ □ ■ ■ ■ □ □ ■ □ ■ □ □ ■ ■ ■ □ ■ ■ ■ □ ■ □ □ □ □ □ ■ □ ■ ■ ■ □ ■ □ □ □ □ □ ■ □ ■ ■ ■ □ ■ ■ ■ □ □ ■ □ ■ □ □ ■ ■ ■ □ □ □ ■ ■ □ ■ ■ □ □ □ ■ ■ □ □ ■ □ ■ ■ ■ □ ■ ■ ■ □ ■ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ■ □ ■ ■ ■ □ □ □ ■ ■ ■ □ ■ □ □ □ □ □ □ □ □ □ □ □ □ □ ■ □ □ ■ ■ □ ■ □ ■ □ ■ ■ □ □ ■ □ □ □ □ □ □ □ □ □ □ □ □ ■ □ ■ ■ □ ■ □ □ □ ■ □ ■ ■ □ ■ □ □ □ ■ □ ■ □ □ ■ ■ ■ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ■ □ ■ ■ ■ ■ □ ■ ■ □ ■ □ □ □ ■ □ ■ ■ □ ■ □ □ □ ■ □ ■ ■ □ □ □ ■ ■ ■ □ □ ■ ■ □ ■ □ ■ □ ■ ■ □ □ ■ □ □ □ □ □ ■ □ ■ ■ □ □ ■ □ ■ □ ■ ■ ■ □ □ □ ■ ■ ■ □ ■ □ □ □ □ □ ■ □ ■ ■ ■ □ ■ □ □ □ ■ □ ■ ■ ■ □ ■ ■ ■ □ ■ □ □ □ □ □ ■ □ □ ■ ■ □ ■ □ □ □ ■ ■ ■ □ □ ■ □ ■ □ □ ■ ■ ■ □ □ □ □ ■ ■ □ □ □ ■ ■ □ ■ ■ ■ ■ □ ■ □ □ □ □ □ ■ □ ■ ■ ■ □ □ □ ■ ■ ■ □ ■ □ □ □ □ ■ ■ □ □ □ ■ ■ □ ■ ■ □ □ □ ■ ■ □ □ □ □ ■ ■ ■ □ □ ■ □ ■

上のパターンは9×3ライツアウトの $A^{-1}$ を求めたものです．まるでミステリーサークルのようです．オマケで15×3と4×16ライツアウトの $A^{-1}$ を画像にしたものも右下につけときます．

（つづくかも）

*1:こんな大袈裟なソフトをわざわざ使わなくても単なる掃き出し法のプログラムを書けば済む話だが，GAPなら有限体やベクトル空間の扱いが非常に楽だし，発展的な使い方も期待できそうなので使ってみた．

*2:これをchasingと呼ぶそうです．

*3:簡単に言えば，演算が{0,1}の中で閉じた集合のこと．プログラマー的には通常の和(+)と積(*)の演算が排他的論理和(xor)と論理積(and)に置き換わったと思えばよい．

*4: $\mathbb{F}_2$ つまり $-1 \equiv 1 \pmod{2}$ のもとでは ${\bf b}=-{\bf b}$ と見なせるので $A{\bf x}={\bf b}$ を解いても同じになるが， $\mathbb{F}_p,\quad p \neq 2$ のときは $-1 \not \equiv 1 \pmod{p}$ となり一般性を失うので $A{\bf x}+{\bf b}={\bf o}$ と見るのが好ましい．また，「ボタンを押す」+(on)「問題面」=(makes)「ライトが全部消える」という意味合いでも自然な表記である．

*5:2の倍数回押しても0回に等しいということである．また解法は押す順序に関係しないというきわめて重要な性質もある．

*6:もしふつうの行列計算ソフトなどを使って（計算機的）実数 ${\bf R}$ の中でまともに逆元を求めたら $A^{-1}/{\det(A)}$ が出てきてしまい，うまい具合に整数解を得られない．あとからdet(A)を掛けて丸めるか， $A{\bf x}/\det(A)+{\bf b}={\bf o}$ の方程式を解いてから，最後にmod 2をとる必要がある．余因子行列を求めてもよい． $A$ が正則ならこの方法で解いても特に問題ない．

*7:3×3や6×6や7×7ならばAは正則である．一方，4×4や5×5なら正則でない．また，とんでもないことに，4×4の場合は16通りの解が存在する．

*8:symmetric,reflexiveな性質を持つゲーム一般について言及したものがJaapsのページにある．