M.Hiroi's Home Page

Puzzle DE Programming

変形版「ライツアウト」

[ Home | Puzzle ]

問題の説明

ライツアウトは「(株)タカラ」から1995年に発売されたパズルゲーム機で、光っているボタンをすべて消すことができればクリアとなります。ライツアウトのルールは拙作の ライツアウトの解法 をお読みください。

ところで、ライツアウトの変形バージョンではボタンの色を増やした N 色ライツアウトが有名ですが、このほかにもボタンを押したときの反転パターンや盤面の形を変えたバージョンを考えることができます。ここでは 3 つの変形版「ライツアウト」を取り上げてみましょう。使用するプログラミング言語は Python3 (PyPy3) です。

●反転パターンをXに変更

最初にボタンを押したときの反転パターンを変更してみましょう。反転パターンは次のような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 色ライツアウトと同じようですが、ライトの状態はオン・オフの 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

初版 2002 年 7 月 5 日
改訂 2022 年 10 月 22 日

Copyright (C) 2002-2022 Makoto Hiroi
All rights reserved.

[ Home | Puzzle ]