ライツアウトは「(株)タカラ」から 1995 年に発売されたパズルゲーム機です。光っているボタンをすべて消すことができればクリアとなります。M.Hiroi は月刊・電脳倶楽部 Vol.94 (1996 年 3 月号) で、このゲームを知りました。
ルールは簡単で、あるボタンを押すと、そのボタンと上下左右のボタンの状態が反転します。つまり、光っているボタンは消灯し、消えていたボタンは点灯します。次の図を見てください。
□□□□□ □□□□□
□□□□□ □□■□□
□□□□□ □■■■□
□□□□□ □□■□□
□□□□□ □□□□□
図 : 中央のボタンを押したときの点灯パターン
ボタンは 5 行 5 列に配置されています。図に示したように、中央のボタンを押すと、そのボタンと上下左右のボタンが反転します。もう一度同じボタンを押すと、再度ボタンの状態が反転するので、元の状態に戻ります。つまり、ライツアウトでは「同じボタンは二度押さなくてよい」ことがわかります。
また、実際にボタンを押してみるとわかりますが、「ボタンを押す順番は関係がない」ことがわかります。たとえば、ボタン A と B を押す場合、A -> B と押すのも、B -> A と押したのも、同じ結果になります。
この 2 つの法則から、ボタンを押す組み合わせは全部で 2 ^ 25 (2 の 25 乗)、約 32 万通りになります。この組み合わせを生成して、ライトが全部消えるかチェックすればいいわけです。
M.Hiroi の昔話で恐縮ですが、当時はＣ言語 (GCC) でプログラムを作り、パソコン X68030 (MC68030 25 MHz) で実行したところ、約 4 分ほどで解を求めることができました。そのプログラムを Windows 95 (Pentium 166 MHz) で実行すると約 7 秒かかりました。
今使っているパソコン (Ubuntu 20.04 LTS (WSL1), Intel Core i5-6200U 2.30GHz) では、スクリプト言語でも短時間で解を求めることができると思います。今回の改訂版では Python3 (PyPy3) を使ってプログラムを作ることにします。
最初は単純な生成検定法でプログラムを作りましょう。n 個から r 個を選ぶ組み合わせを \({}_n \mathrm{C}_r\) とすると、ボタンの押し方は次の式で表すことができます。
つまり、25 個のボタンから i 個を選ぶ組み合わせを求め、選んだボタンを押してライトがすべて消えるかチェックすればいいわけです。これをそのままプログラムすると次のようになります。
リスト : ライツアウトの解法 (単純な生成検定法, lo.py)
# 組み合わせの生成
def combination(func, n, m, a = 0):
if m == 0:
func(a)
elif m == n:
b = a | ((1 << m) - 1)
func(b)
else:
combination(func, n - 1, m, a)
combination(func, n - 1, m - 1, a | (1 << (n - 1)))
# 押すボタンのパターン
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
]
# ライトが全部消えるかチェックする
def check(b, x):
for i in range(25):
if x & (1 << i) != 0:
b ^= pattern[i]
if b == 0:
print_answer(x)
# ライツアウトの解法
def solver0(board):
for i in range(1, 26):
print(f'----- {i} -----')
combination(lambda x: check(board, x), 25, i)
ボタンの状態はビットで表します。1 が点灯で 0 が消灯です。配列 pattern は、ボタンを押したときに状態が変わる位置をビットで示したものです。この値とボタンの状態の排他的論理和 (xor) を取ると、ボタンの状態を反転させることができます。
関数 combination() は n 個の中から m 個を選ぶ組み合わせをビットで返します。拙作のページ Algorithms with Python 「再帰定義: 組み合わせの生成 (2)」で作成した関数 comb3() を高階関数に修正したものです。アルゴリズムの説明はそちらのページをお読みください。
関数 check() は選んだボタンを押してライトが全部消えるかチェックします。引数 b が盤面、x が選んだボタンの位置を表します。for ループで i 番目のビットがオンになっているかチェックして、そうであれば b と pattern[i] の排他的論理和を取ります。これで選択したボタンを押すことができます。b が 0 になったならばボタンは全部消えました。関数 print_answer() で押したボタンの位置を表示します。
関数 solver0() は簡単です。for ループで選ぶボタンの個数 i を 1 から 25 まで順番に増やしていき、combination() で組み合わせを生成して、check() でボタンを押して全部消えるかチェックするだけです。
関数 print_answer() は簡単なので説明は割愛させていただきます。詳細はプログラムリストをお読みください。
それでは、ボタンが全部点灯しているときの解を求めてみましょう。実行環境は PyPy3 (ver 7.3.1), Ubuntu 20.04 LTS (WSL1), Intel Core i5-6200U 2.30GHz です。
>>>> s = time.time(); solver0(0x1ffffff); print(time.time() - s) ----- 1 ----- ----- 2 ----- ----- 3 ----- ----- 4 ----- ----- 5 ----- ----- 6 ----- ----- 7 ----- ----- 8 ----- ----- 9 ----- ----- 10 ----- ----- 11 ----- ----- 12 ----- ----- 13 ----- ----- 14 ----- ----- 15 ----- . O O . O . O O O . . . O O O O O . O O O O . . . . . . O O O O . O O O O O . . . O O O . O . O O . O O . . . O O . O O . . O O O . O O O . . O O . O O . O O . . O O O . O O O . . O O . O O . . . O O ----- 16 ----- ----- 17 ----- ----- 18 ----- ----- 19 ----- ----- 20 ----- ----- 21 ----- ----- 22 ----- ----- 23 ----- ----- 24 ----- ----- 25 ----- 13.286911725997925
最短手数は 15 手で、4 通りの解が表示されました。O が押すボタンの位置です。実行時間は約 13.3 秒かかりました。解を一つ見つけた時点で終了すると、もう少し速くなるでしょう。興味のある方はプログラムを改良してみてください。
月刊・電脳倶楽部 Vol.95 (1996 年 4 月号) では、拙作を含めて 3 つの解法プログラムが発表されました。拙作のプログラムは遅かったのですが、中谷秀洋さんと松本康弘さんのプログラムがメチャクチャ速いのです。
中谷さんのプログラムでは、次の法則を利用して効率的な枝刈りが行われています。
ボタンの回りとは、そのボタン自身も含みます。パズルには、このような奇数と偶数による場合分けができるものがあります。これを「パリティ (偶奇性)」といいます。パリティをチェックすることで、解の有無を簡単に判定できる場合があります。中谷さんのプログラムは 68000 アセンブラで記述されていて、パリティチェックを高速に行っています。
ＡＢＣＤＥ ＡＢＣＤＥ ＡＢＣＤＥ ＡＢＣＤＥ
１□■□■□ １□□□□□ １□□□□□ １□□□□□
２□□□□□ ２■■□■■ ２□□□□□ ２□□□□□
３□□□□□ ３□■□■□ ３□■□■□ ３□□□□□
４□□□□□ ４□□□□□ ４■■□■■ ４□□□□□
５□□□□□ ５□□□□□ ５□□□□□ ５□■□■□
（１） （２） （３） （４）
図 : １行ずつボタンを消灯していく方法
松本康弘さんのプログラムは、ボタンを 1 行ずつ消灯していくという、わかりやすいアルゴリズムです。上の図を見てください。
(1) では、1 行目のボタンが 2 つ点灯しています。このボタンを消すには、真下にある 2 行目の B と D のボタンを押せばいいですね。すると (2) の状態になります。次に、2 行目のボタンを消します。3 行目の A, B, D, E のボタンを押して、(3) の状態になります。
あとはこれを繰り返して、4 行目までのボタンを消したときに 5 行目のボタンも全部消えていれば成功となります。(4) のように、5 行目のボタンが消えない場合は失敗です。この場合は、1 行目のボタンを押して、点灯パターンを変更します。
2 - 5 行目のボタンの押し方は、1 行目の点灯パターンにより決定されるので、けっきょく 1 行目のボタンの押し方により、解けるか否かが決まります。この場合、ボタンの押し方は、2 の 5 乗 (32) 通りしかありせん。つまり、たった 32 通り調べるだけで、ライツアウトの解を求めることができるのです。
これは、とてもわかりやすいアルゴリズムですね。松本さんのほかにも、この解法を見つけた方は多いのではないでしょうか。Web ページでは高橋謙一郎さんの『コンピュータ＆パズル』に、同じアルゴリズムを使った解法プログラムが公開されています。
高橋さんの詳細な考察によると、実際は 8 通り調べるだけで解を見つけることができるそうです。このほかにも、細江万太郎さんが考案されたライツアウトを連立方程式で解く方法が紹介されています。連立方程式による解法は拙作のページでも取り上げています。興味のある方は以下のページをお読みください。
それでは、32 通りをチェックするプログラムを作りましょう。
リスト : ライツアウトの解法 (高速版)
def check1(b, x):
c = 0
for i in range(5):
if x & (1 << i) != 0:
b ^= pattern[i]
c += 1
for i in range(5, 25):
if b & (1 << (i - 5)) != 0:
b ^= pattern[i]
x ^= 1 << i
c += 1
if b == 0:
print("手数", c)
print_answer(x)
def solver1(board):
for i in range(32): check1(board, i)
関数 check1() は、最初の for ループで引数 x が示す 1 行目のボタンを押します。次の for ループで、2 行目から 5 行目のボタンを押して、全部消えるかチェックします。変数 i が押すボタンの位置を表しています。上のボタンの位置は i - 5 で求めることができます。i - 5 番目のボタンが点灯していたならば i 番目のボタンを押します。このとき、押したボタンの位置を変数 x にセットすることをお忘れなく。
最後にボタンが全部消えているかチェックします。そうであれば print_answer() で解を出力します。関数 solver1() は for ループで 0 から 31 までの整数を生成して check1() に渡すだけです。
プログラムはこれで完成です。さっそく試してみましょう。
>>>> s = time.time(); solver1(0x1ffffff); print(time.time() - s) 手数 15 O O . . . O O . O O . . O O O . O O O . . O O . O 手数 15 O . O O . . O O O . O O O . . O O . O O . . . O O 手数 15 . O O . O . O O O . . . O O O O O . O O O O . . . 手数 15 . . . O O O O . O O O O O . . . O O O . O . O O . 0.012207746505737305
一瞬で答えを求めることができました。
これで、ライツアウトを高速に解くことができるようになりました。今度は、いちばん手数のかかるパターンを探してみましょう。つまり、最短手順で解いてもいちばん長い手順となる、いちばん難しい配置を求めるわけです。ライツアウトの場合、ボタンをすべて押して作られたパターン (25 手) が、いちばん長い手数のように思えますが、実は違います。すべてのボタンを押して作られるパターンは、次のようになります。
■□□□■
□■■■□
□■■■□
□■■■□
■□□□■
図 : 25個のボタンを押して作られるパターン
このパターンは、すべてのボタンを押しても解くことができますが、最小 9 手で解くことができます。
このような場合、すべてのパターンについて最小手数をチェックしていたのでは、時間がとてもかかってしまいます。そこで、光がついていない状態（完成形）から始めて、いちばん長い手数の局面を生成することにします。まず、完成形からボタンを押して 1 手で到達するパターンをすべて作ります。次に、これらのパターンからボタンを押して新しいパターンを作れば、完成形から 2 手で到達するパターンとなります。このように、手数を 1 手ずつ延ばしていき、新しいパターンが生成できなくなった時点での手数が求める最長手数となります。
このような問題を解く場合、「幅優先探索」というアルゴリズムが適しています。幅優先探索を使う場合、同一パターンのチェック処理が重要になります。この処理のよしあしによって、実行時間が極端に遅くなることがあるからです。データの検索処理には、「ハッシュ法」や「二分探索木」など定番の高速アルゴリズムがありますが、今回は単純な配列を使うことにします。
プログラムは次のようになります。
リスト : ライツアウト最長手数の探索
def solver_max():
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)
変数 table に大きさ 0x2000000 (32 M) の配列を用意します。table は False で初期化します。変数 move が探索する手数、変数 xs には move - 1 で生成された盤面を格納します。あとは、xs から盤面 a を取り出し、ボタンを順番に押して新しい盤面 b を生成します。table[b] が False ならば b は新しい盤面です。table[b] を true にセットし、b を配列 ys に追加します。
xs にある盤面をすべて調べたとき、ys が空ならば新しい盤面を生成することができませんでした。ここで while ループを脱出して探索を終了します。そうでなければ、print() で手数と盤面数を表示し、ys を xs にセットして探索を続行します。
それでは実行結果を示します。
>>>> s = time.time(); solver_max(); print(time.time() - s) 1 : 25 2 : 300 3 : 2300 4 : 12650 5 : 53130 6 : 176176 7 : 467104 8 : 982335 9 : 1596279 10 : 1935294 11 : 1684446 12 : 1004934 13 : 383670 14 : 82614 15 : 7350 合計 = 8388608 9.223009824752808
最長手数は 15 手で、その盤面は 7350 通りあります。そのうちのひとつがライトが全部点灯しているパターンです。ライツアウトの場合、ライトの点灯パターンは 2 ^ 25 = 33554432 通りありますが、実際に解が存在するパターンは、その 1 / 4 の 8388608 通りしかありません。この結果から、ライツアウトは 15 手あれば解けることがわかります。15 手で解けないときは解がない場合です。
実行時間は約 10 秒でした。M.Hiroi が X68030 (MC68030 25 MHz) で解いた時は、メモリが足りないのでビットでチェックするなどしてプログラムを工夫しました。その結果、実行時間は約 1 時間ほどかかってしまいました。それでも解けたときは、とても嬉しかったことを覚えています。
ハードウェアの進歩はとても速く、低価格の PC でも高速 CPU と大容量メモリを使用できるようになりました。パズルを解くには、よい環境になったものです。
#
# lo.py : ライツアウトの解法
#
# Copyright (C) 2022 Makoto Hiroi
#
# 組み合わせの生成
def combination(func, n, m, a = 0):
if m == 0:
func(a)
elif m == n:
b = a | ((1 << m) - 1)
func(b)
else:
combination(func, n - 1, m, a)
combination(func, n - 1, m - 1, a | (1 << (n - 1)))
# 押すボタンのパターン
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
]
# 解の表示
def print_answer(x):
for i in range(25):
j = 1 << i
if x & j != 0:
print('O', end=' ')
else:
print('.', end=' ')
if (i + 1) % 5 == 0: print()
print()
# ライトが全部消えるかチェックする
def check(b, x):
for i in range(25):
if x & (1 << i) != 0:
b ^= pattern[i]
if b == 0:
print_answer(x)
# ライツアウトの解法 (生成検定法)
def solver0(board):
for i in range(1, 26):
print(f'----- {i} -----')
combination(lambda x: check(board, x), 25, i)
# 高速化
def check1(b, x):
c = 0
for i in range(5):
if x & (1 << i) != 0:
b ^= pattern[i]
c += 1
for i in range(5, 25):
if b & (1 << (i - 5)) != 0:
b ^= pattern[i]
x ^= 1 << i
c += 1
if b == 0:
print("手数", c)
print_answer(x)
def solver1(board):
for i in range(32): check1(board, i)
# 最長手数
def solver_max():
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)