「15 パズル」でお馴染みのスライドパズルです。それでは問題です。
┌───┬─┬─┐ ┌─┬─┬───┐ ┌───┬─┬─┐
│ 電球 │Ｏ│Ｎ│ │Ｎ│Ｏ│ 電球 │ │ 電球 │Ｎ│Ｏ│
├─┬─┼─┼─┤ ├─┼─┼─┬─┤ ├─┬─┼─┼─┤
│Ｏ│Ｆ│Ｆ│ │ │Ｆ│Ｏ│Ｆ│ │ │Ｏ│Ｆ│Ｆ│ │
└─┴─┴─┴─┘ └─┴─┴─┴─┘ └─┴─┴─┴─┘
問題Ａ 問題Ｂ ＧＯＡＬ
図 : NO-OFF
問題 A, B から GOAL までの最短手順を求めてください。
スライドパズル NO-OFF は、問題 A の "ON-OFF" を GOAL のように "NO-OFF" にチェンジするパズルです。NO-OFF は芦ヶ原伸之氏が考案されたパズルで、C MAGAZINE 1991 年 1 月号の「Ｃマガ電脳クラブ」でも出題されています。問題 B は GOAL からの最長手数の局面のひとつです。このパズルは局面の総数が少ないにもかかわらず、手数がけっこうかかる面白いパズルです。
このパズルは局面の総数が 540 通りしかありません。
電球(3 通り) * 空き場所(6 通り) * N (5 通り) * O (4C2 = 6 通り) = 540 通り
プログラムを作る場合、幅優先探索で簡単に解を求めることができます。ちなみに、GOAL までの最長手数は 56 手で、局面は全部で 3 通りあります。問題 B はその中の 1 つです。
>>> solver_max() 最長手数 = 56 個数 = 3 F N L L O O F S N O L L F O F S O F L L N O F S 状態の総数 = 540
┌─┬─┬───┐ ┌─┬─┬───┐ ┌─┬─┬───┐
│Ｆ│Ｎ│ 電球 │ │Ｎ│Ｏ│ 電球 │ │Ｏ│Ｆ│ 電球 │
├─┼─┼─┬─┤ ├─┼─┼─┬─┤ ├─┼─┼─┬─┤
│Ｏ│Ｏ│Ｆ│ │ │Ｆ│Ｏ│Ｆ│ │ │Ｎ│Ｏ│Ｆ│ │
└─┴─┴─┴─┘ └─┴─┴─┴─┘ └─┴─┴─┴─┘
図 : 最長手数の局面
生成された状態数は 540 通りあるので、電球を上段に配置しておけば、あとの駒はランダムに配置しても解けることがわかります。
#
# no_off.py : NO-OFF パズル
#
# Copyright (C) 2022 Makoto Hiroi
#
import time
from collections import deque
# 駒
S = 0
L1 = 1
L2 = 2
N = 3
F = 4
O = 5
# 盤面
# 0 1 2 3
# 4 5 6 7
# 問題
qa = (
L1, L2, O, N,
O, F, F, S
)
qb = (
N, O, L1, L2,
F, O, F, S
)
# ゴール
goal = (
L1, L2, N, O,
O, F, F, S
)
# 隣接リスト
adjacent = [
[1, 4], # 0
[0, 2, 5], # 1
[1, 6, 3], # 2
[2, 7], # 3
[0, 5], # 4
[1, 4, 6], # 5
[2, 5, 7], # 6
[3, 6]
]
# 盤面の表示
def print_board(b):
s = ['S', 'L', 'L', 'N', 'F', 'O']
for i, p in enumerate(b):
print(s[p], end=' ')
if (i + 1) % 4 == 0: print()
# 駒の移動
def move_piece(b, n, s):
a = list(b)
if b[n] == L1:
if s > n: return None, -1
a[s] = a[n]
a[n] = a[n + 1]
a[n + 1] = S
s1 = n + 1
elif b[n] == L2:
if s > 3: return None, -1
a[s] = a[n]
a[n] = a[n - 1]
a[n - 1] = S
s1 = n - 1
else:
a[s] = a[n]
a[n] = 0
s1 = n
return tuple(a), s1
# 手順の表示
def print_moves(b, table):
if b:
print_moves(table[b], table)
print_board(b)
print()
# 幅優先探索
def bfs(start):
queue = deque()
queue.append((start, start.index(0)))
check = {}
check[start] = ()
while len(queue) > 0:
b, s = queue.popleft()
if b == goal:
print_moves(b, check)
return
for n in adjacent[s]:
a, s1 = move_piece(b, n, s)
if a is None or a in check: continue
queue.append((a, s1))
check[a] = b
# 最長手数の局面を求める
def solver_max():
xs = [(goal, goal.index(0))]
check = {}
check[goal] = True
move = 0
while True:
ys = []
for b, s in xs:
for n in adjacent[s]:
a, s1 = move_piece(b, n, s)
if a is None or a in check: continue
ys.append((a, s1))
check[a] = True
if not ys: break
xs = ys
move += 1
print('最長手数 =', move, '個数 =', len(xs))
for b in xs:
print_board(b[0])
print()
print('状態の総数 =', len(check))
L L が電球を表し、_ が空き場所を表します。
(0) (1) (2) (3) (4) (5) (6) (7) L L O N L L O _ L L _ O _ L L O O L L O O L L O O L L O O L L O O F F _ O F F N O F F N O F F N _ F F N F _ F N F F _ N F F N _ (8) (9) (10) (11) (12) (13) (14) (15) O L L _ O _ L L _ O L L F O L L F O L L F _ L L F L L _ F L L O F F N O F F N O F F N O _ F N O F _ N O F O N O F O N O F O N _ (16) (17) (18) (19) (20) (21) (22) (23) F L L O F L L O F L L O _ L L O L L _ O L L O _ L L O N L L O N F O _ N F _ O N _ F O N F F O N F F O N F F O N F F O _ F F _ O (24) (25) (26) (27) (28) (29) (30) (31) L L _ N _ L L N F L L N F L L N F L L N F L L N F L L _ F _ L L F F O O F F O O _ F O O F _ O O F O _ O F O O _ F O O N F O O N (32) (33) (34) (35) (36) (37) (38) (39) F O L L F O L L _ O L L O _ L L O L L _ O L L N O L L N O L L N F _ O N _ F O N F F O N F F O N F F O N F F O _ F F _ O F _ F O (40) (41) (42) (43) (44) O L L N _ L L N L L _ N L L N _ L L N O _ F F O O F F O O F F O O F F O O F F _
L L が電球を表し、_ が空き場所を表します。
(0) (1) (2) (3) (4) (5) (6) (7) N O L L N O L L N O L L N _ L L N L L _ N L L F N L L F N L L F F O F _ F O _ F F _ O F F O O F F O O F F O O _ F O _ O F _ O O (8) (9) (10) (11) (12) (13) (14) (15) N L L F _ L L F L L _ F L L F _ L L F O L L F O L L _ O _ L L O _ F O O N F O O N F O O N F O O N F O _ N F _ O N F F O N F F O (16) (17) (18) (19) (20) (21) (22) (23) N L L O N L L O N L L O N L L O N L L _ N _ L L _ N L L F N L L _ F F O F _ F O F F _ O F F O _ F F O O F F O O F F O O _ F O O (24) (25) (26) (27) (28) (29) (30) (31) F N L L F _ L L F L L _ F L L O F L L O F L L O F L L O _ L L O F _ O O F N O O F N O O F N O _ F N _ O F _ N O _ F N O F F N O (32) (33) (34) (35) (36) (37) (38) (39) L L _ O L L N O L L N O L L N _ L L _ N _ L L N F L L N F L L N F F N O F F _ O F F O _ F F O O F F O O F F O O _ F O O F _ O O (40) (41) (42) (43) (44) (45) (46) (47) F L L N F L L N F L L _ F _ L L F O L L F O L L _ O L L O _ L L F O _ O F O O _ F O O N F O O N F _ O N _ F O N F F O N F F O N (48) (49) (50) (51) (52) (53) (54) (55) O L L _ O L L N O L L N O L L N O L L N _ L L N L L _ N L L N _ F F O N F F O _ F F _ O F _ F O _ F F O O F F O O F F O O F F O (56) L L N O O F F _