問題の説明
ライツアウトは「(株)タカラ」から1995年に発売されたパズルゲーム機で、光っているボタンをすべて消すことができればクリアとなります。ライツアウトのルールは拙作の ライツアウトの解法 をお読みください。
ところで、ライツアウトの変形バージョンではボタンの色を増やした N 色ライツアウトが有名ですが、このほかにもボタンを押したときの反転パターンや盤面の形を変えたバージョンを考えることができます。ここでは 3 つの変形版「ライツアウト」を取り上げてみましょう。使用するプログラミング言語は Python3 (PyPy3) です。
●反転パターンをＸに変更
最初にボタンを押したときの反転パターンを変更してみましょう。反転パターンは次のようなＸの形にしてみました。
基本的な法則はライツアウトと同じなので、ボタンを押す組み合わせは全部で 2^25 (2 の 25 乗)、約 32 万通りになります。このパターンだと上から 1 行ずつ消していく方法は使えませんが、細江万太郎さんが考案された「ライツアウトを連立方程式で解く方法」で高速に解くことができるはずです。興味のある方は、高橋謙一郎さんの コンピュータ＆パズル にある 驚異のライツアウト解法ロジック や、以下の拙作のページをお読みください。
そこで、今回は解法プログラムではなく最長手数を調べることにしました。プログラムは ライツアウトの解法：最長手数を求める の反転パターンを変更するだけです。
結果は次のようになりました。
>>>> s = time.time(); solver_max(pattern_x); print(time.time() - s) 1 : 25 2 : 300 3 : 2300 4 : 12442 5 : 49402 6 : 145824 7 : 317136 8 : 493505 9 : 525929 10 : 363348 11 : 150868 12 : 33156 13 : 2916 合計 = 2097152 2.9880876541137695 実行環境 : PyPy3 (ver 7.3.1), Ubuntu 20.04 LTS (WSL1), Intel Core i5-6200U 2.30GHz
実行時間は約 3 秒、ライトがすべて消えている完成形も含めて全部で 2,097,152 通りとなりました。ライツアウトの 1/4 しかありません。最長手数も 13 手と短くなりました。パターンの総数が少ないので、ライツアウトよりも簡単なように思われます。ですが、実際のゲームでは 1 行ずつ消していく方法が使えないので、ライツアウトよりも難しく感じるかもしれませんね。
●点灯と消灯で反転パターンを変える
次はボタンの点灯と消灯で反転パターンが異なるライツアウトを考えてみましょう。次の図を見てください。
上図に示すように、消灯しているボタンを押したときは今までと同じですが、点灯しているボタンを押すとＸの形（押したボタンと斜め 4 方向のボタン）に反転します。このパターンの面白いところは、同じボタンを 4 回押すと元の状態に戻ることです。次の図を見てください。
一見すると 4 色ライツアウトと同じようですが、ライトの状態はオン・オフの 2 種類しかないので、局面の総数はそれほど多くはないでしょう。5 行 5 列盤の場合、局面は最大で 2 ^ 25 = 33554432 通りですが、ライツアウトではその 1/4 の 8388608 通りしかありません。これより多くなるのか少なくなるのか、ちょっと興味があります。そこで、局面の総数と最長手数を求めるプログラムを作ってみました。
実行結果を示します。
>>>> s = time.time(); solver_max1(); print(time.time() - s) 1 : 25 2 : 357 3 : 4021 4 : 37809 5 : 299268 6 : 1935410 7 : 8667086 8 : 16621708 9 : 5852793 10 : 135954 合計 = 33554432 63.49892473220825
実行時間は約 64 秒、局面の総数は初期状態を含めて 33554432 通りになりました。つまり、ライトがどんな点灯パターンでも必ず解くことができるわけです。この結果は予想していなかったので、M.Hiroi もびっくりしました。ライツアウトの最長手数は 15 手ですが、この変形版は 10 手と短くなりました。もしかすると、ライツアウトよりも簡単に解けるのかもしれませんね。
●菱形ライツアウト
最後は、下図のように盤面の形を菱形に変えてみましょう。
ボタンは全部で 25 個あります。反転パターンはライツアウトと同じく、押したボタンと左右上下のボタンの状態が反転します。局面の総数と最長手数はライツアウトよりも増えるのか減るのか、プログラムを作って調べてみました。
結果は次のようになりました。
>>>> s = time.time(); solver_max(make_pattern()); print(time.time() - s) 1 : 25 2 : 300 3 : 2300 4 : 12650 5 : 53130 6 : 177100 7 : 480700 8 : 1081575 9 : 2042975 10 : 3268760 11 : 4457400 12 : 5200300 13 : 5200300 14 : 4457400 15 : 3268760 16 : 2042975 17 : 1081575 18 : 480700 19 : 177100 20 : 53130 21 : 12650 22 : 2300 23 : 300 24 : 25 25 : 1 合計 = 33554432 29.2131564617157
実行時間は約 30 秒かかりました。生成した局面数は初期状態を含めて 33554432 通りあります。これは、どんな点灯パターンでも必ず解くことができることを表しています。それから、最長手数は 25 手、つまりすべてのボタンを押した場合になります。この局面は下図のようなパターンになります。
●プログラムリスト
#
# lo1.py : 変形版ライツアウトの解法
#
# Copyright (C) 2022 Makoto Hiroi
#
import time
#
# 反転パターン
#
# + パターン
pattern = [
0x0000023, 0x0000047, 0x000008e, 0x000011c, 0x0000218,
0x0000461, 0x00008e2, 0x00011c4, 0x0002388, 0x0004310,
0x0008c20, 0x0011c40, 0x0023880, 0x0047100, 0x0086200,
0x0118400, 0x0238800, 0x0471000, 0x08e2000, 0x10c4000,
0x0308000, 0x0710000, 0x0e20000, 0x1c40000, 0x1880000
]
# X パターン
pattern_x = [
0x0000041, 0x00000a2, 0x0000144, 0x0000288, 0x0000110,
0x0000822, 0x0001445, 0x000288a, 0x0005114, 0x0002208,
0x0010440, 0x00288a0, 0x0051140, 0x00a2280, 0x0044100,
0x0208800, 0x0511400, 0x0a22800, 0x1445000, 0x0882000,
0x0110000, 0x0228000, 0x0450000, 0x08a0000, 0x1040000
]
# 最長手数を求める
def solver_max(pattern):
table = [False] * 0x2000000
table[0] = True
xs = [0]
move = 1
total = 1
while True:
ys = []
for a in xs:
for i in range(25):
b = a ^ pattern[i]
if not table[b]:
table[b] = True
ys.append(b)
if len(ys) == 0: break
print(move, ":", len(ys))
total += len(ys)
move += 1
xs = ys
print("合計 =", total)
# + -> X の最長手数を求める
def solver_max1():
table = [False] * 0x2000000
table[0] = True
xs = [0]
move = 1
total = 1
while True:
ys = []
for a in xs:
for i in range(25):
# 逆順だから消灯時が Ｘ で点灯時が ＋ になる
if a & (1 << i) == 0:
b = a ^ pattern_x[i]
else:
b = a ^ pattern[i]
if not table[b]:
table[b] = True
ys.append(b)
if len(ys) == 0: break
print(move, ":", len(ys))
total += len(ys)
move += 1
xs = ys
print("合計 =", total)
#
# 菱形ライツアウト
#
#
# 座標
# ０
# １ ２ ３
# ４ ５ ６ ７ ８
#９ 10 11 12 13 14 15
# 16 17 18 19 20
# 21 22 23
# 24
#
pattern_data = [
[0, 2], # 0
[1, 2, 5], # 1
[0, 1, 2, 3, 6], # 2
[2, 3, 7], # 3
[4, 5, 10], # 4
[1, 4, 5, 6, 11], # 5
[2, 5, 6, 7, 12], # 6
[3, 6, 7, 8, 13], # 7
[7, 8, 14], # 8
[9, 10], # 9
[4, 9, 10, 11, 16], # 10
[5, 10, 11, 12, 17], # 11
[6, 11, 12, 13, 18], # 12
[7, 12, 13, 14, 19], # 13
[8, 13, 14, 15, 20], # 14
[14, 15], # 15
[10, 16, 17], # 16
[11, 16, 17, 18, 21], # 17
[12, 17, 18, 19, 22], # 18
[13, 18, 19, 20, 23], # 19
[14, 19, 20], # 20
[17, 21, 22], # 21
[18, 21, 22, 23, 24], # 22
[19, 22, 23], # 23
[22, 24] # 24
]
# 反転パターンを作る
# solver_max(make_pattern()) で最長手数を求める
def make_pattern():
table = []
for i in range(25):
pat = 0
for j in pattern_data[i]:
pat += 1 << j
table.append(pat)
return table
改訂 2022 年 10 月 22 日