Light Outゲーム
ライツアウトはタカラから発売されているゲームですが。スマホのアプリでも多数あるようです。私はiPhoneの"25bit"というアプリを使ってます。
Light Outと線形代数
Light Outと線形代数は相性が良いようで検索すると多くの記事が見つかります。Qiitaにも以下の記事が見つかりました。
今回は以下の英語の論文を参考にしてLights OutをSagemathで解いて行こうと思います。ここでは主に5 x 5の大きさを考えますが、プログラム的にはM x Nの一般的なものを考慮して作ります。
順番としては以下のように考えて行きます。
- 各々のボタンが押されたときにどのライトが反転するのかを定義する行列を作る。（今回）
- 答えを得るためにはその逆行列を求めればよいが、5 x 5の場合は正則でないので工夫が必要
- 答えが求まるかどうかを判定
- 一つの解答からすべての解答を求め、最適なものを選ぶ
ボタン・ライトの関係を定義する行列
3 x 3の場合ボタン$b_{1,1}$を押すとライト$x_{1,1}.x_{1,2},x_{2,1}$が反転するのでこれを以下のように1行にして反転するもとを1, しないものを0で表すと以下のようになります。
b_{i,j} = (x_{1,1},x_{1,2},x_{1,3},x_{2,1}, x_{2,1}, ...,x_{3,3}) \\
= \begin{bmatrix} 1& 1& 0& 1& 0& 0& 0& 0& 0 \end{bmatrix}
これを3 x 3=9行並べると以下のような行列になります。
A(3,3)=\begin{bmatrix} 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{bmatrix}
なんとなく規則性が見えてきたと思いますが上記の論文によると5 x 5の場合には以下のように表されます。（M x Nの場合も同様に拡張できる）
A(5,5)=\begin{bmatrix} B&I&O&O&O\\
I&B&I&O&O\\
O&I&B&I&O\\
O&O&I&B&I\\
O&O&O&I&B\\
\end{bmatrix}\\
ここでO: ゼロ行列、I: 単位行列\\
B=\begin{bmatrix}
1& 1& 0& 0& 0\\
1& 1& 1& 0& 0 \\
0& 1& 1& 1& 0 \\
0& 0& 1& 1& 1 \\
0& 0& 0& 1& 1 \\
\end{bmatrix}
これをSagemathでプログラムしたのが以下になります。ここで重要なのはこの行列は剰余環$\mathbb{Z}/2 \mathbb{Z}$ で定義されている必要があることです。SagemathではMatrixSpace(GF(2),m,n) で行列を定義すると以後の計算を$\mathbb{Z}/2 \mathbb{Z}$で行ってくれるのでとても便利です。
次回（その２）ではこの行列を使ってLights Outを解く方法を示したいと思います。
import numpy as np
def makeA(m,n):
B = np.matrix([[1 if abs(i-j)<=1 else 0 for i in range(n)] for j in range(n)])
for j in range(m):
A1 = np.concatenate([B if i==j else np.identity(n) if abs(i-j)==1 else np.zeros((n,n)) for i in range(m)],1)
A = A1 if j==0 else np.concatenate([A,A1])
MS = MatrixSpace(GF(2),m*n,m*n)
return MS(A)
A = makeA(5,5)
print(A)
#[1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
#[1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
#[0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
#[0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
#[0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
#[1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
#[0 1 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0]
#[0 0 1 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0]
#[0 0 0 1 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0]
#[0 0 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0]
#[0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0]
#[0 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0]
#[0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0]
#[0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0]
#[0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0]
#[0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0]
#[0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 1 0 0 0]
#[0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 1 0 0]
#[0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 1 0]
#[0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 1]
#[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0]
#[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 0]
#[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0]
#[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1]
#[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1]
（開発環境：Cocalc Sage Worksheet）