今回は盤面を「六芒星」の形にしたスライドパズルを解いてみましょう。
★ ☆
／ ＼ ／ ＼
★───★───★───★ ☆───☆───☆───☆
＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼ ／
★───□───☆ ☆───□───★
／ ＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼
☆───☆───☆───☆ ★───★───★───★
＼ ／ ＼ ／
☆ ★
ＳＴＡＲＴ ＧＯＡＬ
問題 : スライドパズル「六芒星」
駒の種類は白 (☆) と黒 (★) の 2 種類しかありません。□ は空き場所を表しています。駒の動かし方は 15 パズルと同じで、1 回に 1 個の駒を空いている隣の場所に滑らせて移動します。駒を跳び越したり持ち上げたりすることはできません。START から GOAL までの最短手順を求めてください。
それではプログラムを作りましょう。使用するプログラミング言語は Python3 (ver 3.8.10) です。盤面の総数ですが、空き場所の位置が 13 通りで、残り 12 マスに 6 個の黒駒を置くわけですから、13 * 13Ｃ6 = 13 * 924 = 12012 通りあります。盤面の総数はそれほど多くないので、単純な幅優先探索で解くことにします。
最初に大域変数を定義します。
リスト : 大域変数の定義
# 定数
S = 0
B = 1
W = 2
# 隣接リスト
adjacent = [
[2, 3], # 0
[2, 5], # 1
[0, 1, 3, 5, 6], # 2
[0, 2, 4, 6, 7], # 3
[3, 7], # 4
[1, 2, 6, 8, 9], # 5
[2, 3, 5, 7, 9, 10], # 6
[3, 4, 6, 10, 11], # 7
[5, 9], # 8
[5, 6, 8, 10, 12], # 9
[6, 7, 9, 11, 12], # 10
[7, 10], # 11
[9, 10] # 12
]
# 問題
start = (
B,
B,B,B,B,
B,S,W,
W,W,W,W,
W
)
goal = (
W,
W,W,W,W,
W,S,B,
B,B,B,B,
B
)
S が空き場所 (0)、B が黒駒 (1)、W が白駒 (2) を表します。adjacent は隣接リストです。start と goal は START と GOAL の盤面を表します。
幅優先探索で解を求める関数 bfs() は次のようになります。
リスト : 幅優先探索
def bfs(start, goal):
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 = move_piece(b, n, s)
if a in check: continue
queue.append((a, n))
check[a] = b
キューは Python の標準ライブラリ collections のクラス deque を使います。同一局面のチェックには Python の辞書を使います。あとは今まで作成した幅優先探索のプログラムとほとんど同じなので、説明は不要でしょう。詳細はプログラムリストをお読みください。
それでは、スライドパズル「六芒星」の解答を示します。図では黒駒 (★) を B, 白駒 (☆) を W, 空き場所を S で表しています。
>>> bfs(start, goal) [ B B B B B B S W W W W W W ] [ B B B S B B B W W W W W W ] [ B B B B S B B W W W W W W ] [ B B B B W B B S W W W W W ] [ B B B B W B S B W W W W W ] [ B B B B W B W B W S W W W ] [ B B B B W S W B W B W W W ] [ B B S B W B W B W B W W W ] [ B B W B W B S B W B W W W ] [ B B W B W B W B W B S W W ] [ B B W B W B W B W B W S W ] [ B B W B W B W S W B W B W ] [ B B W S W B W B W B W B W ] [ S B W B W B W B W B W B W ] [ W B S B W B W B W B W B W ] [ W B W B W B S B W B W B W ] [ W B W B W B W B W B S B W ] [ W B W B W B W B W B W B S ] [ W B W B W B W B W S W B B ] [ W B W B W S W B W B W B B ] [ W S W B W B W B W B W B B ] [ W W S B W B W B W B W B B ] [ W W W B W B S B W B W B B ] [ W W W B W S B B W B W B B ] [ W W W B W W B B S B W B B ] [ W W W B W W B B B S W B B ] [ W W W B W W S B B B W B B ] [ W W W B W W W B B B S B B ] [ W W W B W W W S B B B B B ] [ W W W S W W W B B B B B B ] [ W W W W W W S B B B B B B ]
B
B B B B
B S W
W W W W
W
- 1 --- - 2 --- - 3 --- - 4 --- - 5 --- - 6 --- - 7 --- - 8 ---
B B B B B B B B
B B S B B B W B B B W B B B W B B B W B B B W B B B W B B S W B
B B W B B S B B W B S W S B W W B W W S W W B W
W W W W W W W W W W S W W W B W W W B W W S B W W B B W W B B W
W W W W W W W W
- 9 --- - 10 -- - 11 -- - 12 -- - 13 -- - 14 -- - 15 -- - 16 --
B B B B B B B B
S B W B W B W B W B W B W B W B W B W B W B W B W B W B W S W B
W B W S B W W B W W B W W B W W B W W S W W B W
W B B W W B B W S B B W B S B W B W B W B W S W B W B W B W B W
W W W W S B B B
- 17 -- - 18 -- - 19 -- - 20 -- - 21 -- - 22 -- - 23 -- - 24 --
S W W W W W W W
W B W B W B S B W B W B W B W B W B W B W B W B W S W B W W W B
W B W W B W W B S W B W W B W W S W W B W S B W
B W B W B W B W B W B W B W B S B W S B B W B B B W B B B W B B
B B B B B B B B
- 25 -- - 26 -- - 27 -- - 28 -- - 29 -- - 30 --
W W W W W W
W W W B W W W B W W W B W W W S W W S W W W W W
W B W W S W W W S W W B W W B W S B
B S B B B B B B B B B B B B B B B B B B B B B B
B B B B B B
図 : スライドパズル「六芒星」の解答
最短手数は 30 手になりました。駒が 2 種類しかないスライドパズルは「スライディングブロックパズル」で 4 行 4 列盤の問題を解きました。そのときの最短手数は 48 手になりましたが、今回のパズルはそれよりも短い手数で解くことができました。
次は START から始めて最長手数となる局面を求めます。プログラムは次のようになります。
リスト : 最長手数の局面を求める
def solver_max():
xs = [(start, start.index(0))]
check = {}
check[start] = True
move = 0
while True:
ys = []
for b, s in xs:
for n in adjacent[s]:
a = move_piece(b, n, s)
if a in check: continue
ys.append((a, n))
check[a] = True
if not ys: break
xs = ys
move += 1
print('最長手数 =', move, '個数 =', len(xs))
for b in xs: print_board(b[0])
print('状態の総数 =', len(check))
関数 solver_max() も今まで作成した最長手数の局面を求めるプログラムとほとんど同じなので、説明は不要でしょう。詳細はプログラムリストをお読みください。
>>> solver_max() 最長手数 = 30 個数 = 7 [ S W W W W W W B B B B B B ] [ W W S W W W W B B B B B B ] [ W W W W W W S B B B B B B ] [ W W W W W W B B B B S B B ] [ W W W W W W B B B B B B S ] [ W S W W W W W B B B B B B ] [ W W W W W W B B B B B S B ] 状態の総数 = 12012
W W W W W W S
W W W W S W W W W W W W W W W W W W W W W S W W W W W W
W B B W W B W B B W B B W S B W W B W W B
B B B S B B B B B B B B B B S B B B B B B B B B B B B B
B B S B B B B
図 : スライドパズル「六芒星」最長手数 (30 手) の局面
実はこの問題、START の局面からの最長手数になっています。つまり、一番難しい問題だったわけです。最長手数の局面は全部で 7 通りあります。ちなみに、生成した局面は全部で 12,012 個あります。しがたって、このパズルは駒をランダムに配置しても、必ず START に到達できることがわかります。
駒の種類を増やすと、たぶん最長手数はもっと長くなると思われます。興味のある方は挑戦してみてください。
#
# slide_star.py : スライドパズル六芒星
#
# Copyright (C) 2022 Makoto Hiroi
#
import time
from collections import deque
# 定数
S = 0
B = 1
W = 2
# 隣接リスト
adjacent = [
[2, 3], # 0
[2, 5], # 1
[0, 1, 3, 5, 6], # 2
[0, 2, 4, 6, 7], # 3
[3, 7], # 4
[1, 2, 6, 8, 9], # 5
[2, 3, 5, 7, 9, 10], # 6
[3, 4, 6, 10, 11], # 7
[5, 9], # 8
[5, 6, 8, 10, 12], # 9
[6, 7, 9, 11, 12], # 10
[7, 10], # 11
[9, 10] # 12
]
# 問題
start = (
B,
B,B,B,B,
B,S,W,
W,W,W,W,
W
)
goal = (
W,
W,W,W,W,
W,S,B,
B,B,B,B,
B
)
# 駒の移動
def move_piece(b, n, s):
a = list(b)
a[s] = a[n]
a[n] = 0
return tuple(a)
# 盤面の表示
def print_board(b):
s = ['S', 'B', 'W']
print('[', end=' ')
for p in b:
print(s[p], end=' ')
print(']')
# 手順の表示
def print_moves(b, table):
if b:
print_moves(table[b], table)
print_board(b)
# 幅優先探索
def bfs(start, goal):
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 = move_piece(b, n, s)
if a in check: continue
queue.append((a, n))
check[a] = b
# 最長手数の局面を求める
def solver_max():
xs = [(start, start.index(0))]
check = {}
check[start] = True
move = 0
while True:
ys = []
for b, s in xs:
for n in adjacent[s]:
a = move_piece(b, n, s)
if a in check: continue
ys.append((a, n))
check[a] = True
if not ys: break
xs = ys
move += 1
print('最長手数 =', move, '個数 =', len(xs))
for b in xs: print_board(b[0])
print('状態の総数 =', len(check))