はじめに
「ライツアウト（Lights Out）」は、1995年にTiger Electronicsから発売された電子パズルです。基本となる盤面は、ライト付きのボタンが縦横に5個ずつ並んだ5×5の格子。ボタンを押して、点灯しているライトをすべて消すことを目指します。出典：Wikipedia「Lights Out (game)」
ボタンを押すとそのマスだけでなく、押したマスと上下左右のマスが一緒に反転し、点いていたライトは消え、消えていたライトは点きます。一つの操作が周囲にも影響するところが、このパズルの難しさです。
この仕組みには、1995年の製品以前にも先例があります。例えば1983年には、Vulcan Electronicsから、同様の反転操作を使う「XL-25」が発売されていました。また、ライツアウトにも6×6の盤面を使う「Lights Out Deluxe」や、立方体の各面を使う「Lights Out Cube」などのバリエーションがあります。単純な反転のルールから、盤面の形や大きさを変えたパズルへと広がっています。出典：Jaap's Puzzle Page「Lights Out」
この記事では、ライツアウトを整数計画問題として定式化し、PythonからSCIPを使って解きます。まず全消灯できる押し方を求め、さらに目的関数を加えて、最小手数の解法を探してみます。
今回のルール
この記事では、次のルールを扱います。
- 各マスは点灯（1）か消灯（0）の状態を持つ。
- ボタンを押すと、そのマスと上下左右のマスが反転する。
- 盤面の外側には影響しない。端と反対側の端はつながっていない。
- すべてのマスを消灯させればクリア。
- 1個のボタンを1回押す操作を1手と数える。
3×3の簡単な問題を解いてみると下図のようになりました。赤丸が押すボタンです。
画像では全消灯でなく全点灯でクリアとなっているので注意してください。
ちなみにこちらのサイトを使わせていただきました->https://justy.co.jp/lightsout/
盤面の状態は操作の順番に依らない
さて、下図を見てください。「真ん中のボタン→左上のボタン」、「左上のボタン→真ん中のボタン」の2パターンの押し方をした場合の盤面の遷移を表しています。最終状態はどちらでも同じになっています。
なぜでしょうか。
それは、盤面全体ではなく、一つのライトが何回反転するかに注目すると分かります。
- AとBのどちらにも影響されないライトは、反転しません。
- AかBの片方だけに影響されるライトは、1回反転します。
- AとBの両方に影響されるライトは、2回反転して元に戻ります。
図の紫枠は、両方のボタンに影響されるマスです。A→BでもB→Aでも「消灯→点灯→消灯」となります。反転させるボタンの順番を入れ替えても、反転する回数は変わりません。
ボタンの数や押す回数が増えても、考え方は同じです。各ライトの最終状態は、反転回数が偶数なら初期状態と同じ、奇数なら初期状態と逆になります。どのボタンによる反転が先だったかは関係ありません。
同じボタンを2回押す操作は除外できる
次に、同じボタンAを2回押してみます。Aが反転させるマスは毎回同じなので、それらのライトはすべて2回反転して元に戻ります。
図では全消灯から始めていますが、最初に点いていたライトも「点灯→消灯→点灯」と戻ります。したがって、どんな初期状態でも、同じボタンを2回押した結果は、押さなかった場合と同じです。
2回の操作が連続していなくても良いです。「A→B→A」は「A→A→B」にできるので、Aの2回分を取り除いた「B」だけの操作と同じ最終状態になります。
最少手数を求める場合、同じ結果のまま減らせる操作を残す必要はありません。したがって、各ボタンを押す回数は0回か1回に限定してよいことになります。
これで、考える対象をどの順番で何回押すかから、どのボタンを押すかに絞れました。次の定式化では、各ボタンに「押す＝1、押さない＝0」という変数を一つずつ用意すれば十分です。
変数の定義
盤面を $N\times M$ とし、行・列の添字は0から始めます。
盤面の行数を $N$、列数を $M$ とします。$N,M$ は正の整数で、盤面には縦に $N$個、横に $M$ 個のマスが並びます。
初期状態を $b_{r,c}\in\{0,1\}$、押す場所を表す変数を
各マスは、行番号と列番号の組 $(r,c)$ で指定します。
- 行番号 $r$ は、上から下へ $0,1,\ldots,N-1$
- 列番号 $c$ は、左から右へ $0,1,\ldots,M-1$
つまり、
$$
r\in\{0,1,\ldots,N-1\},\qquad
c\in\{0,1,\ldots,M-1\}
$$
です。左上のマスは $(0,0)$、右下のマスは $(N-1,M-1)$ となります。例えば3×3の盤面では、次のように番号を付けます。
| 行番号 ＼ 列番号 | $c=0$ | $c=1$ | $c=2$ |
|---|---|---|---|
| $r=0$ | $(0,0)$ | $(0,1)$ | $(0,2)$ |
| $r=1$ | $(1,0)$ | $(1,1)$ | $(1,2)$ |
| $r=2$ | $(2,0)$ | $(2,1)$ | $(2,2)$ |
以降、盤面内のマス全体の集合を
$$
V=\{(r,c)\mid r,c\in\mathbb Z,\ 0\leq r<N,\ 0\leq c<M\}
$$
と書きます。各マス $(r,c)\in V$ に対して、初期状態を表す定数 $b_{r,c}$ を、点灯なら1、消灯なら0とします。
押す場所を表す変数を
x_{r,c}=\begin{cases}
1 & \text{ボタンを押す}\\
0 & \text{ボタンを押さない}
\end{cases}
とします。
さらに、マス $(r,c)$ を反転させるボタンの集合を $N(r,c)$ とします。自分自身と、盤面内に存在する上下左右のマスです。
例えば左上の隅を押したとき、反転するのは、「押したマス」、「押したマスの右のマス」、「押したマスの下のマス」なので
$$
N(0,0)=\{(0,0),(1,0),(0,1)\}
$$
です（$N,M\geq2$ の場合）。
「消灯する」を制約式に
あるマスが最終的に消えている条件は
$$
b_{r,c}+\sum_{(i,j)\in N(r,c)}x_{i,j}\equiv0\pmod2
$$
です。偶奇のみを考えればよいので$\mod 2$で考えます。
初めから消えていれば反転回数は偶数、初めから点いていれば反転回数は奇数である必要があります。初期状態の $b_{r,c}$ を足すことで、どちらも「偶数になる」と書けます。
ここで整数変数 $k_{r,c}$ を導入すると、合同式を次の線形等式に置き換えられます。
$$
b_{r,c}+\sum_{(i,j)\in N(r,c)}x_{i,j}=2k_{r,c}.
$$
例えば左上が点灯していれば
$$
1+x_{0,0}+x_{1,0}+x_{0,1}=2k_{0,0}
$$
となります。周囲の3個のボタンのうち、1個か3個を押せば、このマスを消せます。
マス $(r,c)$ を反転させられるボタンの個数を $d_{r,c}=|N(r,c)|$ とします。
各ボタンを押す回数は0か1なので、反転回数の合計は
$$
0\leq\sum_{(i,j)\in N(r,c)}x_{i,j}\leq d_{r,c}
$$
です。初期状態 $b_{r,c}$ を足し、左辺が $2k_{r,c}$ であることを使うと
$$
b_{r,c}\leq 2k_{r,c}\leq b_{r,c}+d_{r,c}
$$
が得られます。したがって、$k_{r,c}$ の上限は $(b_{r,c}+d_{r,c})/2$ です。$k_{r,c}$ は整数なので、小数部分を切り捨てた値までに制限できます。$\lfloor a\rfloor$ は、$a$ 以下の最大の整数を表します。
$b_{r,c}=1$ の場合は、等式と整数条件から自動的に $k_{r,c}\geq1$ となります。
以上より、補助変数の範囲を
$$
0\leq k_{r,c}\leq\left\lfloor\frac{b_{r,c}+d_{r,c}}2\right\rfloor,
\qquad k_{r,c}\in\mathbb Z
$$
とできます。$k$ を連続変数にしてしまうと偶奇の制約がなくなるので、整数であることが必要です。
目的関数で最少手数を求める
各 $x$ は、そのボタンを押すかどうかを表すので、手数は単純に $\sum x_{r,c}$ です。全体のモデルは次のようになります。
\begin{aligned}
\text{minimize}\quad &\sum_{r=0}^{N-1}\sum_{c=0}^{M-1}x_{r,c}\\
\text{subject to}\quad
&\forall r,c,\quad b_{r,c}+\sum_{(i,j)\in N(r,c)}x_{i,j}=2k_{r,c},\\
&\forall r,c, \quad x_{r,c}\in\{0,1\} ,\\
& \forall r,c,\quad k_{r,c}\in\mathbb Z,\quad
0\leq k_{r,c}\leq\left\lfloor\frac{b_{r,c}+d_{r,c}}2\right\rfloor.
\end{aligned}
二値変数が $NM$ 個、補助整数変数が $NM$ 個、等式制約が $NM$ 本です。
実行可能解(全消灯できる押し方)が一つ見つかればよい場合は、目的関数を0にしても構いません。その場合、返された解が最少手数とは限りません。
PythonからSCIPを使う
Pythonでモデルを書き、解く部分にはSCIPを使います。そのためのインターフェースがPySCIPOptです。LPファイルを自分で組み立てる代わりに、Pythonから変数・制約・目的関数を登録します。
以下、Python 3.12.14、PySCIPOpt 6.2.1、SCIP 10.0.2、Windows 11で確認しました。
python -m pip install pyscipopt==6.2.1
対応環境ではSCIPを含むビルド済みパッケージを利用できます。詳細は公式インストールガイドを参照。
次のコードだけで例題を解けます。
from pyscipopt import Model, quicksum
b = [
[1, 1, 0, 1, 1],
[0, 1, 0, 0, 0],
[1, 0, 1, 0, 1],
[0, 0, 0, 1, 0],
[1, 0, 1, 1, 0],
]
H, W = len(b), len(b[0])
def neighbors(r, c):
for dr, dc in ((0, 0), (-1, 0), (1, 0), (0, -1), (0, 1)):
nr, nc = r + dr, c + dc
if 0 <= nr < H and 0 <= nc < W:
yield nr, nc
model = Model("lightsout")
model.hideOutput()
model.setParam("limits/time", 30)
x = {(r, c): model.addVar(vtype="B", name=f"x_{r}_{c}")
for r in range(H) for c in range(W)}
for r in range(H):
for c in range(W):
around = list(neighbors(r, c))
k = model.addVar(vtype="I", lb=0,
ub=(b[r][c] + len(around)) // 2)
model.addCons(b[r][c] + quicksum(x[p] for p in around) == 2*k)
model.setObjective(quicksum(x.values()), "minimize")
# LP形式で保存したい場合：model.writeProblem("lightsout.lp")
model.optimize()
status = str(model.getStatus())
print("status:", status)
if model.getNSols() > 0:
sol = model.getBestSol()
presses = [[int(round(model.getSolVal(sol, x[r, c])))
for c in range(W)] for r in range(H)]
for row in presses:
print(*row)
print("presses:", sum(map(sum, presses)))
# 実際に反転させて、全消灯することも確認する。
state = [row[:] for row in b]
for r in range(H):
for c in range(W):
if presses[r][c]:
for nr, nc in neighbors(r, c):
state[nr][nc] ^= 1
assert not any(map(any, state))
if status != "optimal":
print("全消灯する解は得られましたが、最少性は未保障です。")
elif status == "infeasible":
print("この盤面を全消灯する押し方はありません。")
else:
print("解の有無を確定できませんでした。")
実行結果は次のようになりました。
status: optimal
1 0 1 1 0
0 1 0 1 0
0 0 1 0 1
1 0 0 1 0
1 1 0 0 0
presses: 11
optimal は設定した目的関数に対する最適性を表します。今回の目的関数は手数なので、11手より少ない解はありません。一方、目的関数を0にしたモデルの optimal は、最少手数の証明を意味しません。
実行可能解と最適解
最初からランダムに点灯させると、解けない盤面ができる場合があります。全消灯した盤面にランダムな押し方を適用して、必ず解ける盤面を生成できます。(その押し方をもう一度適用すれば全消灯すできますね。)
各ボタンを確率1/2で選び、3×3、4×4、5×5を各3盤面生成しました。Pythonの random.Random(seed) を使い、seedは順に300～302、400～402、500～502です。
同じ盤面に対して、目的関数を0にした場合と、手数の最小化にした場合を比較しました。
| 盤面 | seed | 目的関数0で得た手数 | 最少手数 |
|---|---|---|---|
| 3×3 | 300 | 5 | 5 |
| 3×3 | 301 | 4 | 4 |
| 3×3 | 302 | 6 | 6 |
| 4×4 | 400 | 10 | 4 |
| 4×4 | 401 | 9 | 5 |
| 4×4 | 402 | 11 | 5 |
| 5×5 | 500 | 16 | 12 |
| 5×5 | 501 | 10 | 10 |
| 5×5 | 502 | 17 | 7 |
例えば4×4のseed=400では、最初のモデルが返した10手の解に対し、手数を最小化すると4手の解が得られました。全消灯する条件は同じでも、目的関数を変えると、求める解が変わることが分かります。目的関数0のモデルが選ぶ解は、環境やソルバーによって変わる可能性があります。
求解時間の測定
結果は下図。
- 縦軸：解を求めるのにかかった時間
- 横軸：ライツアウトのマスの数
- 左のグラフ：実行可能解を1つ求める場合
- 右のグラフ：最適解(最短手数の解)を求める場合
- 計算は5秒で打ち切る
-
time.perf_counter()を使い、model.optimize()の呼び出しから戻るまでを計測 - モデルの作成・ライブラリの読み込み・図の描画は含まない
実行可能解を探す場合は、サイズが大きくなるにつれて計算時間も大きくなる傾向がありますが、最適解を求める場合はそうなってはいませんね。
線形代数とのつながり
各ボタンがどのライトを反転させるかを0/1行列 $A$ にまとめると、消灯の条件は
$$
Ax=b\pmod2
$$
です。ここでは $-b=b$ が成り立つので、先ほどの $b+Ax\equiv0$ と同じ条件です。
この連立方程式は、0と1を使う体 $\mathrm{GF}(2)$ 上のガウス消去法でも解けます。実行可能な解を求めるだけなら、この構造を直接使えます。
一方、「1の個数を最小化する(手数を最小化する)」という目的は、連立方程式を一度解くだけでは一般には達成されません。自由変数が残る場合、その選び方で手数が変わるためです。自由変数の数が少なければ、それらの組合せを列挙して最少手数を求める方法もあります。
整数計画として書く利点は、この最少手数の条件に加えて、押す場所ごとのコストや「このボタンは押せない」といった追加条件も、同じモデルに組み込めることです。
例えば押すコストを $w_{r,c}>0$ とすれば、目的関数を $\sum w_{r,c}x_{r,c}$ に変更できます。押せないボタンには $x_{r,c}=0$ を追加します。
偶奇というパズルの性質を $b+\sum x=2k$ と表すだけで、全消灯の条件と最少手数の目的を分けて扱えるようになりました。