ライツアウトは「(株)タカラ」から1995年に発売されたパズルゲーム機で、光っているボタンをすべて消すことができればクリアとなります。ライツアウトのルールは拙作のページ「ライツアウトの解法」をお読みください。
ところで、ライツアウトの変形バージョンではボタンの色を増やした N 色ライツアウトが有名ですが、このほかにもボタンを押したときの反転パターンや盤面の形を変えたバージョンを考えることができます。ここでは 3 つの変形版「ライツアウト」を取り上げてみましょう。使用するプログラミング言語は Python3 (PyPy3) です。
最初にボタンを押したときの反転パターンを変更してみましょう。反転パターンは次のようなXの形にしてみました。
□□□□□ □□□□□ □□□□□ □■□■□ □□□□□ ─→ □□■□□ □□□□□ □■□■□ □□□□□ □□□□□ 中央のボタンを押した場合 図 : 反転パターンの変更
基本的な法則はライツアウトと同じなので、ボタンを押す組み合わせは全部で 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 行ずつ消していく方法が使えないので、ライツアウトよりも難しく感じるかもしれませんね。
次はボタンの点灯と消灯で反転パターンが異なるライツアウトを考えてみましょう。次の図を見てください。
□□□ □■□ ■■■ □■□ □□□ ─→ ■■■ ■■■ ─→ ■□■ □□□ □■□ ■■■ □■□ 消灯時のパターン 点灯時のパターン (どちらも中央のボタンを押した場合) 図 : 変形版ライツアウト
上図に示すように、消灯しているボタンを押したときは今までと同じですが、点灯しているボタンを押すとXの形(押したボタンと斜め 4 方向のボタン)に反転します。このパターンの面白いところは、同じボタンを 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): # 逆順だから消灯時が X で点灯時が + になる 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) # # 菱形ライツアウト # # # 座標 # 0 # 1 2 3 # 4 5 6 7 8 #9 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