LIGHTS OUT SOLVER

点いた灯りを、
すべて消す。

現在の点灯状態を盤面に入力してください。
すべての灯りを消すために押す場所を、GF(2)上の連立方程式から求めます。

CURRENT STATE

現在の盤面を入力する

点灯消灯

5 × 5

UNDER THE HOOD

盤面の大きさではなく、
辺の長さで解く。

各マスを押すかどうかを0と1で表し、足し算を排他的論理和として計算します。盤面全体を未知数にする代わりに、4近傍は行送り、8近傍は縦横への分離を利用しています。

ALGORITHM & COMPLEXITY計算方法を詳しく見る

GF(2)上の線形方程式

同じマスを2回押すと変化が相殺されるため、各マスは「押さない＝0」「押す＝1」だけ考えれば十分です。現在の点灯状態をベクトル b、押し方を x、1回押したときの反転規則を行列 A とすると、全消灯の条件は次の式になります。

b + Ax = 0　⇔　Ax = b　（GF(2)）

素朴に解くと未知数は HW 個なので、Gaussian eliminationは時間 O((HW)³)、メモリ O((HW)²) です。このページでは盤面の構造を使い、この大きな行列を作りません。

4近傍：行送り

最初の行の押し方を仮定すると、1行目を目標どおり消すための2行目の押し方が決まり、同様に下へ進むと残りの全行が一意に決まります。最後の行も消える条件だけが、最初の行を未知数とする小さな線形方程式になります。

実装では盤面を必要に応じて転置し、短辺を m = min(H, W)、長辺を n = max(H, W) として、未知数を常に m 個に抑えます。

TIMEO(HW min(H, W))正方形 N×N なら O(N³)MEMORYO(HW)

8近傍：縦と横に分離

3×3の反転効果は、押した位置をまず縦方向の3マスへ広げ、それぞれを横方向の3マスへ広げる計算に分解できます。これは盤面を2回操作するという意味ではなく、押した位置から反転対象を求める作用を縦と横に分けるものです。対角線とその両隣が1の三重対角行列を T_k、押し方を行列 P、現在の盤面を B とすると、条件は次の形です。

T_H P T_W = B

まず縦方向、次に横方向の線形方程式を解きます。各辺について消去法を一度だけ準備し、それを反対側の辺の本数だけ再利用します。

TIMEO(H³ + W³)正方形 N×N なら O(N³)MEMORYO(H² + W²)

解なしと複数解

消去後に「左辺はすべて0なのに右辺は1」という行が現れれば、全消灯にする押し方は存在しません。自由変数が残る場合は複数の解があります。このソルバーは自由変数を0にした解を1つ返すため、押す回数が最小とは限りません。

計算量はGF(2)の通常のスカラー演算で数えた上界です。実装では最大20ビットをJavaScriptの32ビット整数1個にまとめて処理するため、このページのサイズではさらに軽量です。

点いた灯りを、すべて消す。