今回は連立方程式を使ってパズル「ライツアウト」を解いてみましょう。パズルの説明は拙作のページ「Puzzle DE Programming: ライツアウトの解法」をお読みください。
下記 URL によると、ライツアウトの解法は連立一次方程式を解くことに帰着させることができるそうです。
具体的にいうと、5 行 5 列盤のライツアウトの解は、次に示す 25 本の連立方程式を解くことで求めることができます。
(Xij-1 + Xi-1j + Xij + Xi+1j + Xij+1 + Bij) mod 2 = 0, 0 < i <= 5, 0 < j <= 5
Xij はボタン (i, j) を押す回数、Bij はボタン (i, j) の状態 (点灯・消灯) を表します。たとえば、ボタン (i, j) が点灯している場合、自身のボタンと周囲のボタンを押す回数が奇数回であれば、それを消灯することができます。逆に、消灯している場合であれば、ボタンを押す回数が偶数回であれば消灯したままになります。これを行列で表すと Ax + B ≡ 0 (mod 2) となります。≡ は合同式を表す記号です
数学の世界では、加減乗除ができる数の体系を「体」といいます。特に、数が n 個しかないものを有限体 (またはガロア体) といい GF(n) と表記します。n が素数のとき、その剰余 (0, 1, ..., n - 1) は有限体になります。2 は素数なので GF(2) であり、四則演算ができるのでガウスの消去法により Ax + B ≡ 0 (mod 2) を解くことができます。
GF(2) は 0 と 1 だけの世界です。加算と乗算は次のように定義できます。
+ | 0 | 1 * | 0 | 1 ---+---+--- ---+---+--- 0 | 0 | 1 0 | 0 | 0 ---+---+--- ---+---+--- 1 | 1 | 0 1 | 0 | 1
GF(n) の場合、加算と乗算の演算結果 m が n 以上になったら m mod n を計算します。GF(2) の場合、加法は排他的論理和 (XOR) に、乗法は論理積 (AND) と同じになります (0 と 1 の掛け算と考えてもかまいません)。
減算の場合、x - y を x + (- y) と考えます。(- y) の加法の逆元といいます。y + (- y) = 0 が成り立つので、0 の逆元は 0 で 1 の逆元は 1 であることがわかります。減算は次のようになります。
0 - 0 = 0 + (0) = 0 0 - 1 = 0 + (1) = 1 1 - 0 = 1 + (0) = 1 1 - 1 = 1 + (1) = 0
GF(2) の場合、加算と減算は同じ結果 (排他的論理和) になります。したがって、連立方程式 Ax + B ≡ 0 (mod 2) は Ax ≡ B (mod 2) を解けばいいことになります。徐算の場合も同様に、x / y を x * (1 / y) として考えて、逆数 y-1 を求めればいいのですが、GF(2) の徐算は簡単で 0 / 1 = 0 と 1 / 1 = 1 になります。
今回は 5 行 5 列盤に限定せずに n 行 m 列盤のライツアウトを解くプログラムを作ります。最初に拡大係数行列を生成する関数 make_matrix() を作りましょう。次のリストを見てください。
リスト : 拡大係数行列の生成
# 盤面とボタンの位置関係 (5 * 5 盤の場合)
#
# 1 6 11 16 21
# 2 7 12 17 22
# 3 8 13 18 23
# 4 9 14 19 24
# 5 10 15 20 25
# 拡大係数行列の作成
function make_matrix(ys::Matrix{Int})
n, m = size(ys)
k = n * m
xs = zeros(Int, k, k + 1)
for y = 1 : n, x = 1 : m
z = (x - 1) * n + y
for (dx, dy) = [(-1, 0), (0, -1), (0, 0), (0, 1), (1, 0)]
y1 = y + dy
x1 = x + dx
if 0 < x1 <= m && 0 < y1 <= n
xs[z, (x1 - 1) * n + y1] = 1
end
end
end
xs[:, end] = reshape(ys, k, 1)
xs
end
make_matrix() の引数 ys はボタンの点灯パターンを表す二次元配列です。ys の shape が (n, m) とすると、拡大係数行列の大きさは (n * m, n * m + 1) になります。プログラムでは n * m の値を変数 k にセットしています。
次に for ループの中で、ボタン (y 行 x 列) を押したときに反転するボタンの位置を求め、その位置に対応する係数行列の要素を 1 にセットします。ボタンの位置 (1 次元配列での添字) は Julia の配列に合わせています。具体的には、ボタン (y, x) の位置は (x - 1) * n + y 番目になります。最後に、行列 xs の end 列目 (xs[:, end]) に ys をセットします。これが連立方程式の左辺式になります。
次はライツアウトを解く関数 lo() を作ります。考え方はガウスの消去法と同じです。
リスト : ライツアウトの解法
function lo(ys::Matrix{Int})
ans = []
zs = make_matrix(ys)
n = size(zs, 1)
m = n + 1
for i = 1 : n
select_pivot(zs, i)
if zs[i, i] == 0
if all(isequal(0), zs[i:end, i:end])
m = i
break # 複数の解がある
end
return ans # 解なし
end
for j = i + 1 : n
if zs[j, i] == 1
zs[j, i:end] = xor.(zs[j, i:end], zs[i, i:end])
end
end
end
temp = zs[:, end]
for j = 0 : 2 ^ (n + 1 - m) - 1
if n + 1 - m > 0
zs[m:end, end] = num_conv(j, n + 1 - m, 2)
end
# 後退代入
for k = m - 1 : -1 : 1
v = dot(zs[k, k+1:n], zs[k+1:end, end]) % 2
zs[k, end] = xor(zs[k, end], v)
end
push!(ans, reshape(zs[:, end], size(ys)))
zs[:, end] = temp
end
ans
end
変数 m は階数を表していて n + 1 に初期化します。前進消去で係数 zs[j, i] を 0 にするときは、zs の j 行目と i 行目の排他的論理和を計算するだけです。zs[i, i] が 0 で zs[i:end, i:end] がすべて 0 のときは複数の解がある場合です。i の値が階数になるので、それを m にセットして break でループを脱出します。zs[i:end, i:end] の要素に 1 がある場合は解くことができません。return で ans (空の配列) を返します。
後退代入をする前に、zs の end 列目の値を temp に保存しておきます。m が n + 1 よりも小さい場合、2 ^ (n + 1 - m) 個の解が存在します。最初の for ループで 0 から 2 ^ (n + 1 - m) - 1 の値を生成します。それを関数 num_conv() で 2 進数の配列に変換し、zs[m:end, end] にセットします。後退代入も簡単で、内積の結果を mod 2 にして、それと zs[k, end] の排他的論理和をとるだけです。ans に解を格納したあと、zs[:, end] に temp を代入して元の値に戻します。
それでは実際に試してみましょう。日月離反 - atobirabon によると、『どんなm×nライツアウトも，すべてのライトがonのときは必ず解ける．』 とのことなので、全て点灯した状態を解いてみましょう。ライツアウトの数学的な解析を公開されている作者様に感謝いたします。
実行結果は次のようになりました。ご参考までに、基本変形したあとの拡大係数行列を表示しています。
julia> printanswer(lo(ones(Int, 3, 3))) 1 1 0 1 0 0 0 0 0 1 0 1 1 0 0 1 0 0 0 1 0 0 1 1 1 0 0 0 0 0 0 0 0 1 0 1 1 0 0 1 0 0 0 0 1 0 1 1 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 No 1, 手数 = 5 1 0 1 0 1 0 1 0 1 julia> printanswer(lo(ones(Int, 3, 4))) 1 1 0 1 0 0 0 0 0 0 0 0 1 0 1 1 0 0 1 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 0 0 0 1 0 1 1 1 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 No 1, 手数 = 10 1 1 1 1 1 0 0 1 1 1 1 1 julia> printanswer(lo(ones(Int, 4, 4))) 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 No 1, 手数 = 10 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 0 No 2, 手数 = 6 1 0 0 1 0 0 0 0 0 1 1 0 0 1 1 0 No 3, 手数 = 4 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 No 4, 手数 = 8 0 0 1 1 1 0 1 1 0 1 0 0 1 0 1 0 No 5, 手数 = 4 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 No 6, 手数 = 8 0 1 0 1 0 0 1 0 1 1 0 1 1 1 0 0 No 7, 手数 = 6 1 0 0 0 0 0 1 1 0 0 1 1 1 0 0 0 No 8, 手数 = 10 1 1 1 1 1 0 0 1 1 1 1 1 0 0 0 0 No 9, 手数 = 6 0 1 1 0 0 1 1 0 0 0 0 0 1 0 0 1 No 10, 手数 = 6 0 0 0 1 1 1 0 0 1 1 0 0 0 0 0 1 No 11, 手数 = 8 1 1 0 0 1 1 0 1 0 0 1 0 0 1 0 1 No 12, 手数 = 12 1 0 1 1 0 1 1 1 1 1 1 0 1 1 0 1 No 13, 手数 = 8 1 0 1 0 0 1 0 0 1 0 1 1 0 0 1 1 No 14, 手数 = 12 1 1 0 1 1 1 1 0 0 1 1 1 1 0 1 1 No 15, 手数 = 10 0 0 0 0 1 1 1 1 1 0 0 1 1 1 1 1 No 16, 手数 = 10 0 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 julia> printanswer(lo(ones(Int, 4, 5))) 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 No 1, 手数 = 10 0 1 1 1 0 0 1 0 1 0 0 1 0 1 0 0 1 1 1 0 julia> printanswer(lo(ones(Int, 5, 5))) 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 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 1 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 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 0 0 0 0 0 1 0 1 0 0 0 0 0 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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 No 1, 手数 = 15 0 0 0 1 1 1 1 0 1 1 1 1 1 0 0 0 1 1 1 0 1 0 1 1 0 No 2, 手数 = 15 0 1 1 0 1 0 1 1 1 0 0 0 1 1 1 1 1 0 1 1 1 1 0 0 0 No 3, 手数 = 15 1 1 0 0 0 1 1 0 1 1 0 0 1 1 1 0 1 1 1 0 0 1 1 0 1 No 4, 手数 = 15 1 0 1 1 0 0 1 1 1 0 1 1 1 0 0 1 1 0 1 1 0 0 0 1 1 julia> printanswer(lo(ones(Int, 5, 6))) 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 0 0 0 0 0 1 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 0 0 0 1 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 1 0 1 0 0 0 0 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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 No 1, 手数 = 14 0 0 1 1 0 0 1 0 1 1 0 1 0 1 0 0 1 0 1 0 1 1 0 1 0 0 1 1 0 0 julia> printanswer(lo(ones(Int, 6, 6))) 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 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 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 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 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 1 0 0 0 0 0 0 0 0 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 1 1 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 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 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 No 1, 手数 = 28 1 0 1 1 0 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 0 1 1 0 1
4 * 4 盤は 16 通り、5 * 5 盤は 4 通りの解があり、3 * 3, 3 * 4, 4 * 5, 6 * 6 の各盤はユニーク解でした。
実行速度ですが、試しに 25 * 25 盤の全点灯パターンを解いたところ、解はユニークで手数が 353 手、時間は初回の実行が 0.24 秒、二回目の実行が 0.12 秒 (Julia ver 1.6.4, Ubuntu 18.04 (WSL), Intel Core i5-6200U 2.30GHz) でした。Ｃ/Ｃ++ などで書き直すともっと速くなると思いますが、大きな盤面を解くのでなければ、このままで十分なように思います。
#
# lightsout.jl : ライツアウトの解法 (連立方程式バージョン)
#
# Copyright (C) 2018-2021 Makoto Hiroi
#
using LinearAlgebra
# 拡大係数行列の作成
function make_matrix(ys::Matrix{Int})
n, m = size(ys)
k = n * m
xs = zeros(Int, k, k + 1)
for y = 1 : n, x = 1 : m
z = (x - 1) * n + y
for (dx, dy) = [(-1, 0), (0, -1), (0, 0), (0, 1), (1, 0)]
y1 = y + dy
x1 = x + dx
if 0 < x1 <= m && 0 < y1 <= n
xs[z, (x1 - 1) * n + y1] = 1
end
end
end
xs[:, end] = reshape(ys, k, 1)
xs
end
# ピボット選択
function select_pivot(xs::Matrix{Int}, i::Int)
_, k = findmax(xs[i:end, i]) # 0 と 1 しかないので、絶対値を求める必要はない
k += i - 1
if k != i
temp = xs[i, :]
xs[i, :] = xs[k, :]
xs[k, :] = temp
end
end
# 数値 m を n 桁 c 進数に変換
function num_conv(m::Int, n::Int, c::Int)
buff = zeros(Int, n)
i = 1
while m > 0
buff[i] = m % c
m = div(m, c)
i += 1
end
buff
end
# 行列の表示
function print_matrix(xs::Matrix{Int})
n, m = size(xs)
for i = 1 : n
for j = 1 : m
print("$(xs[i, j]) ")
end
println("")
end
end
# 解の表示
function printanswer(ans)
for (i, a) = enumerate(ans)
println("No $i, 手数 = $(sum(a))")
print_matrix(a)
println("")
end
end
# ライツアウトの解法
function lo(ys::Matrix{Int})
ans = []
zs = make_matrix(ys)
n = size(zs, 1)
m = n + 1
for i = 1 : n
select_pivot(zs, i)
if zs[i, i] == 0
if all(isequal(0), zs[i:end, i:end])
m = i
break # 複数の解がある
end
return ans # 解なし
end
for j = i + 1 : n
if zs[j, i] == 1
zs[j, i:end] = xor.(zs[j, i:end], zs[i, i:end])
end
end
end
print_matrix(zs) # debug
temp = zs[:, end]
for j = 0 : 2 ^ (n + 1 - m) - 1
if n + 1 - m > 0
zs[m:end, end] = num_conv(j, n + 1 - m, 2)
end
# 後退代入
for k = m - 1 : -1 : 1
v = dot(zs[k, k+1:n], zs[k+1:end, end]) % 2
zs[k, end] = xor(zs[k, end], v)
end
push!(ans, reshape(zs[:, end], size(ys)))
zs[:, end] = temp
end
ans
end
「８めくり」はライツアウトに類似のパズルです。ルールは簡単で、あるボタンを押すと周囲のボタンの状態が反転します。つまり、光っているボタンは消灯し、消えていたボタンは点灯します。次の図を見てください。
０１２
３４５ ボタンの番号
６７８
□□□ ■■■ □□□ □■□ □□□ ■□■
□□□ ←→ ■□■ □□□ ←→ ■■□ □□□ ←→ ■■■
□□□ ■■■ □□□ □□□ □□□ □□□
４を押す ０を押す １を押す
図 : 反転パターン
中央のボタン 4 を押すと、その周囲のボタン 8 個の状態が反転します。押したボタンの状態は反転しません。もう一度同じボタンを押すと、再度ボタンの状態が反転するので、元の状態に戻ります。隅のボタン 0 を押すと 3 個のボタンの状態が反転し、辺にあるボタン 1 を押すと 5 個のボタンの状態が反転します。
８めくりの解法プログラムも簡単に作ることができます。プログラムと実行結果を示します。
#
# turn8.jl : ８めくりパズルの解法 (連立方程式バージョン)
#
# Copyright (C) 2018-2021 Makoto Hiroi
#
using LinearAlgebra
# 係数行列の作成
function make_matrix(ys::Matrix{Int})
n, m = size(ys)
k = n * m
xs = zeros(Int, k, k + 1)
for y = 1 : n, x = 1 : m
z = (x - 1) * n + y
for (dx, dy) = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
y1 = y + dy
x1 = x + dx
if 0 < x1 <= m && 0 < y1 <= n
xs[z, (x1 - 1) * n + y1] = 1
end
end
end
xs[:, end] = reshape(ys, k, 1)
xs
end
# ピボット選択
function select_pivot(xs::Matrix{Int}, i::Int)
_, k = findmax(xs[i:end, i]) # 0 と 1 しかないので、絶対値を求める必要はない
k += i - 1
if k != i
temp = xs[i, :]
xs[i, :] = xs[k, :]
xs[k, :] = temp
end
end
# 数値 m を n 桁 c 進数に変換
function num_conv(m::Int, n::Int, c::Int)
buff = zeros(Int, n)
i = 1
while m > 0
buff[i] = m % c
m = div(m, c)
i += 1
end
buff
end
# 行列の表示
function print_matrix(xs::Matrix{Int})
n, m = size(xs)
for i = 1 : n
for j = 1 : m
print("$(xs[i, j]) ")
end
println("")
end
end
# 解の表示
function printanswer(ans)
for (i, a) = enumerate(ans)
println("No $i, 手数 = $(sum(a))")
print_matrix(a)
println("")
end
end
# ８めくりパズルの解法
function turn8(ys::Matrix{Int})
ans = []
zs = make_matrix(ys)
n = size(zs, 1)
m = n + 1
for i = 1 : n
select_pivot(zs, i)
if zs[i, i] == 0
if all(isequal(0), zs[i:end, i:end])
m = i
break # 複数の解がある
end
return ans # 解なし
end
for j = i + 1 : n
if zs[j, i] == 1
zs[j, i:end] = xor.(zs[j, i:end], zs[i, i:end])
end
end
end
temp = zs[:, end]
for j = 0 : 2 ^ (n + 1 - m) - 1
if n + 1 - m > 0
zs[m:end, end] = num_conv(j, n + 1 - m, 2)
end
# 後退代入
for k = m - 1 : -1 : 1
v = dot(zs[k, k+1:n], zs[k+1:end, end]) % 2
zs[k, end] = xor(zs[k, end], v)
end
push!(ans, reshape(zs[:, end], size(ys)))
zs[:, end] = temp
end
ans
end
julia> printanswer(turn8(ones(Int, 4, 4))) No 1, 手数 = 6 1 0 1 0 0 1 0 0 0 1 0 0 1 0 1 0 No 2, 手数 = 8 0 1 1 1 1 1 0 0 1 0 1 0 1 0 0 0 No 3, 手数 = 8 0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 No 4, 手数 = 10 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 0 No 5, 手数 = 8 0 1 0 0 1 1 1 0 0 1 1 1 0 0 1 0 No 6, 手数 = 6 1 0 0 1 0 1 1 0 1 0 0 1 0 0 0 0 No 7, 手数 = 10 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 No 8, 手数 = 8 0 0 0 1 0 1 0 1 0 0 1 1 1 1 1 0 No 9, 手数 = 8 1 0 0 0 1 0 1 0 1 1 0 0 0 1 1 1 No 10, 手数 = 6 0 1 0 1 0 0 1 0 0 0 1 0 0 1 0 1 No 11, 手数 = 6 0 0 0 0 1 0 0 1 0 1 1 0 1 0 0 1 No 12, 手数 = 8 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 No 13, 手数 = 10 0 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 No 14, 手数 = 8 1 0 1 1 1 0 0 0 0 0 0 1 1 1 0 1 No 15, 手数 = 8 1 1 1 0 0 0 1 1 0 1 0 1 0 0 0 1 No 16, 手数 = 10 0 0 1 1 1 0 1 1 1 0 1 1 0 0 1 1 julia> printanswer(turn8(ones(Int, 5, 5))) julia> printanswer(turn8(ones(Int, 6, 6))) No 1, 手数 = 16 1 0 0 0 0 1 0 1 1 1 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 1 1 1 0 1 0 0 0 0 1 julia> printanswer(turn8(ones(Int, 7, 7))) julia> printanswer(turn8(ones(Int, 8, 8))) No 1, 手数 = 32 0 1 1 0 0 1 1 0 1 1 0 1 1 0 1 1 1 0 1 0 0 1 0 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 0 1 0 1 0 0 1 0 1 1 1 0 1 1 0 1 1 0 1 1 0 0 1 1 0 julia> printanswer(turn8(ones(Int, 9, 9))) julia> printanswer(turn8(ones(Int, 10, 10))) No 1, 手数 = 60 1 0 1 1 1 1 1 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 1 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 1 1 1 1 1 0 1
ライツアウトと違って、盤のサイズによっては全点灯パターンが解けないこともあります。実行速度ですが、32 * 32 盤を解くのに初回の実行で 0.33 秒、二回目の実行で 0.22 秒かかりました。なお、deepgreen さんが作成された解法プログラム (turnover3.exe) を使うと、32 * 32 盤でも 94 msec (Windows 10, Intel Core i5-6200U 2.30GHz) で解くことができます。ソースコードも公開されているので、deepgreen さんの Web ページをお読みください。deepgreen さんに感謝いたします。
ところで、拙作のページ「Scheme Programming: パズルに挑戦 ８めくりの解答」で最長手数を求めたことがあります。4 * 4 盤の場合、最長手数は 7 手で、局面の総数は全部のボタンが消灯した状態を含めて 4096 通りになりました。全局面の 1 / 16 しかありません。4 * 6 盤の場合、最長手数は 24 手で、全局面数は 2 ^ 24 = 16777216 通りになります。5 * 5 盤の場合、全消灯に到達できる局面は 2 ^ 25 / 2 = 16777216 通りあり、その中で最長手数は 20 手 (126 通り) になります。興味のある方はいろいろ試してみてください。