問題の説明
15 パズルの変形版です。下図を見てください。
駒の種類は白と黒の 2 種類しかありません。駒の動かし方も 15 パズルと同じで、1 回に 1 個の駒を空いている隣の場所に滑らせて移動します。駒を跳び越したり持ち上げたりすることはできません。START から GOAL までの最短手順を求めてください。
●幅優先探索
それではプログラムを作ります。使用するプログラミング言語は Python3 (ver 3.8.10) です。今回はオーソドックスに幅優先探索を使いましょう。盤面の総数ですが、空き場所の位置が 16 通りで、残り 15 マスに 8 個の黒駒を置くわけですから、次のようになります。
16 * 15Ｃ8 = 16 * 6435 = 102960 通り
最近のパソコンは高性能なので、この程度であれば単純な幅優先探索で解を求めることができます。最初に大域変数を定義します。
リスト : 大域変数の定義
# 盤面
# 0 1 2 3
# 4 5 6 7
# 8 9 10 11
# 12 13 14 15
# 定数
S = 0
B = 1
W = 2
# 隣接リスト
adjacent = [
[1, 4], # 0
[0, 2, 5], # 1
[1, 3, 6], # 2
[2, 7], # 3
[0, 5, 8], # 4
[1, 4, 6, 9], # 5
[2, 5, 7, 10], # 6
[3, 6, 11], # 7
[4, 9, 12], # 8
[5, 8, 10, 13], # 9
[6, 9, 11, 14], # 10
[7, 10, 15], # 11
[8, 13], # 12
[9, 12, 14], # 13
[10, 13, 15], # 14
[11, 14] # 15
]
# 問題
start = (
B, B, B, B,
B, B, B, B,
W, W, W, W,
W, W, W, S
)
goal = (
S, W, W, W,
W, W, W, W,
B, B, 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 の辞書を使います。あとは今まで作成した幅優先探索のプログラムとほとんど同じなので、説明は不要でしょう。詳細は プログラムリスト をお読みください。
●実行結果
実行結果は次のようになりました。
>>> s = time.time(); bfs(start, goal); print(time.time() - s) B B B B B B B B W W W W W W W S B B B B B B B B W W W S W W W W B B B B B B B S W W W B W W W W ・・・省略・・・ W W W W W S W W B B B B B B B B W S W W W W W W B B B B B B B B S W W W W W W W B B B B B B B B 0.3855752944946289 実行環境 : Python3 (ver 3.8.10), Ubunts 20.04 (WSL1), Intel Core i5-6200U 2.30GHz
[START] 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 B B B B B B B B B B B B B B B S B B S B B B W B B B W B B S W B S B W B W W W W W W W S W W W B W W W B W W S B W S W B W B W B W B W B W W W S W W W W W W W W W W W W W W W W W W W W W W W W W W W W B B B B B B B B B B B B B B B B B B B B B S B B S B B B W B B B W B W B W B W B W B W B W B W B W S W B W B W B W B W B S B W B S B W B W B W B W B W B W S W B W B W B W B W B W B W B W B W B W W W W S W W W W S W W W B W W W B W W W B W W W B W W W B W W W B B B W B B B W B B B W B B B W B B B W S B B W B S 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 B W B W B W B S B S B W B W B W B W B W B W S W B W B W B W B W B W B W B W B W B W B W W S B W W B S W W B B W W B B W W B B W W B B W W B B W W 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 S W W B W W 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 B W B W B S B W B S B W B W B W B W B W B W S W B W B W B W B W B W B W B W B B B W W B B S W B B W S B B W B B B W B B B W B B B W B B B W B W B W W W B W W W B W W W B W W W B W W W B W W W B W W W B W W W B W B W B W B W B W B W B W B W B W S W B S W W B W W W B W W W B S B W B W B W B W B W B W S W B W B W B W B W B S B W S B B B B W B B B S B B B B S B B B B B B B B B B B B B B B B B B B B W B W W W S W W S W W W W W W W W W W W W W W W W W W W W S W W W S W W W B W W W B W W S B W W W B W W W B W W W S W W W W W W W B B B W B B B W B B B W B B B S B B 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 B B B B B B B B B B B B B B [GOAL1] [GOAL2] S W W W W W S W W W W W W W W W B B B B B B B B B B B B B B B B
最短手順は 48 手、実行時間は Python3 で約 0.4 秒でした。
●最長手数の局面
次は 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() も今まで作成した最長手数の局面を求めるプログラムとほとんど同じなので、説明は不要でしょう。詳細は プログラムリスト をお読みください。
●実行結果 (2)
実行結果は次のようになりました。
>>> s = time.time(); solver_max(); print(time.time() - s) 最長手数 = 48 個数 = 2 W W S W W W W W B B B B B B B B S W W W W W W W B B B B B B B B 状態の総数 = 102960 0.2750413417816162
最長手数は 48 手で、その盤面は全部で 2 通りありました。実行時間は約 0.3 秒かかりました。ちなみに、生成した局面は全部で 102,960 個あります。しがたって、このパズルは駒をランダムに配置しても、必ず START に到達できることがわかります。
●プログラムリスト
#
# sllide15.py : 15 パズル変形版 (駒が白黒の二種類)
#
# Copyright (C) 2022 Makoto Hiroi
#
from collections import deque
import time
# 状態の総数
# 16 * 15Ｃ8 = 16 * 6435 = 102960
# 盤面
# 0 1 2 3
# 4 5 6 7
# 8 9 10 11
# 12 13 14 15
# 定数
S = 0
B = 1
W = 2
# 隣接リスト
adjacent = [
[1, 4], # 0
[0, 2, 5], # 1
[1, 3, 6], # 2
[2, 7], # 3
[0, 5, 8], # 4
[1, 4, 6, 9], # 5
[2, 5, 7, 10], # 6
[3, 6, 11], # 7
[4, 9, 12], # 8
[5, 8, 10, 13], # 9
[6, 9, 11, 14], # 10
[7, 10, 15], # 11
[8, 13], # 12
[9, 12, 14], # 13
[10, 13, 15], # 14
[11, 14] # 15
]
# 問題
start = (
B, B, B, B,
B, B, B, B,
W, W, W, W,
W, W, W, S
)
goal = (
S, W, W, W,
W, W, W, W,
B, B, 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']
for i, p in enumerate(b):
print(s[p], end=' ')
if (i + 1) % 4 == 0: print()
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))
初版 2001 年 5 月 2 日
改訂 2022 年 11 月 12 日
改訂 2022 年 11 月 12 日