今回は「８パズル」の変形バージョンを解いてみましょう。次の図を見てください。
┌┬┬┬┬┬┐ ┌─┬─┬─┐ ┌─┬─┬─┐
├┘│││└┤ │┌┼─┼┐│ │０│１│２│
├─┼┴┼─┤ ├┼┼─┼┼┤ ├─┼─┼─┤
├─┤ ├─┤ │││ │││ │３│４│５│
├─┼┬┼─┤ ├┼┼─┼┼┤ ├─┼─┼─┤
├┐│││┌┤ │└┼─┼┘│ │６│７│８│
└┴┴┴┴┴┘ └─┴─┴─┘ └─┴─┴─┘
ＳＴＡＲＴ ＧＯＡＬ リストと盤面の対応
図 : スライドパズル
このスライドパズルは数字ではなく 6 種類の駒 (┘┐┌└│─) を使います。─と│は 2 個ずつあるので駒は全部で 8 個になります。START から GOAL までの最短手順を求めてください。
それではプログラムを作りましょう。使用するプログラミング言語は Python3 (ver 3.8.10) です。最初は幅優先探索で、次に反復深化を使って解いてみます。最初に駒の置き方が何通りあるか数えましょう。このスライドパズルは数字ではなく 6 種類の駒 (┘┐┌└│─) を使っています。─と│は 2 個ずつあるので、局面の総数は次のようになります。
9 * 8 * 7 * 6 * 5 * 4Ｃ2 * 2Ｃ2 = 9 * 8 * 7 * 6 * 5 * 6 * 1 = 90720
同一局面のチェックに線形探索を使うと時間がかかりそうなので、Python の辞書を使うことにします。スライドパズルの盤面は一次元配列 (Python のリスト) を使って表します。リストと盤面の対応は図 1 を見てください。駒は次のように数値で表すことにします。
0: 空き場所 1: ┌ 2: ─ 3: ┐ 4: │ 5: └ 6: ┘
最初に大域変数を定義します。
リスト : 大域変数の定義
# 隣接リスト
adjacent = [
[1, 3], # 0
[0, 2, 4], # 1
[1, 5], # 2
[0, 4, 6], # 3
[1, 3, 5, 7], # 4
[2, 4, 8], # 5
[3, 7], # 6
[4, 6, 8], # 7
[5, 7] # 8
]
# 問題
start = (6,4,5,2,0,2,3,4,1)
goal = (1,2,3,4,0,4,5,2,6)
# 駒の種類
piece_list = ['□', '┌', '─', '┐', '│', '└', '┘']
幅優先探索を行う関数 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
「７パズル」で作成したプログラムとほとんど同じなので、説明は割愛させていただきます。詳細はプログラムリストをお読みください。
それでは実行結果を示します。空き場所は □ で表しています。
>>> s = time.time(); bfs(start, goal); print(time.time() - s) ┘│└ ─□─ ┐│┌ ┘□└ ─│─ ┐│┌ ・・・省略・・・ ┌─┐ │─│ └□┘ ┌─┐ │□│ └─┘ 0.2289445400238037 実行環境 : Python 3.8.10, Ubuntu 20.04 LTS (WSL1), Intel Core i5-6200U 2.30GHz
┘│└ ─□─ ┐│┌ ┘│└ ┘│└ ┘│└ □│└ │□└ │└□ │└─ │└─ │└─ │└─ ─│─ ─│─ □│─ ┘│─ ┘│─ ┘│─ ┘│□ ┘│┌ ┘│┌ ┘□┌ ┐□┌ □┐┌ ─┐┌ ─┐┌ ─┐┌ ─┐┌ ─┐┌ ─┐□ ─□┐ ─│┐ │□─ │─□ │─┌ │─┌ │─┌ │─┌ │─┌ │─┌ │─┌ │─┌ ┘└┌ ┘└┌ ┘└□ ┘└┐ ┘└┐ ┘□┐ □┘┐ ─┘┐ ─┘┐ ─□┐ ─│┐ ─│┐ ─│┐ ─│□ ─□│ ─└│ ─└│ □└│ └□│ └┘│ │□┌ │┌□ │┌┐ │┌┐ │┌┐ │┌┐ │┌┐ □┌┐ ┌□┐ ┌─┐ ──┐ ──┐ ──□ ──│ ──│ ─□│ □─│ │─│ │─│ │□│ └┘│ └┘│ └┘│ └┘□ └□┘ └─┘ └─┘ └─┘ └─┘ └─┘
最小手数は 30 手になりました。実は、GOAL から最長手数となる局面が START なのです。実行時間は約 0.23 秒でした。
次は最長手数の局面を求める関数 solver_max() を作ります。
リスト : 最長手数の局面を求める
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 = 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))
「７パズル」で作成したプログラムとほとんど同じです。実行結果は次のようになりました。
>>> s = time.time(); solver_max(); print(time.time() - s) 最長手数 = 30 個数 = 6 ┘─└ │□│ ┐─┌ ┘│└ │□─ ┐─┌ ┘│└ ─□─ ┐│┌ ┘│└ ─□│ ┐─┌ ┘─└ ─□│ ┐│┌ ┘─└ │□─ ┐│┌ 状態の総数 = 90720 0.19507503509521484
┘─└ ┘─└ ┘│└ ┘│└ ┘│└ ┘─└ │□─ ─□│ ─□│ ─□─ │□─ │□│ ┐│┌ ┐│┌ ┐─┌ ┐│┌ ┐─┌ ┐─┌
最長手数は 30 手、盤面は 6 通りあります。生成した盤面の総数は 90720 個になりました。しがたって、 このパズルは駒をランダムに配置しても、必ずゴールに到達できることがわかります。実行時間は約 0.2 秒かかりました。
次は反復深化で解いてみましょう。次のリストを見てください。
リスト : 単純な幅優先探索
def dfs(n, board, goal, space, limit, moves):
global cnt
if n == limit:
if board == goal:
print(moves[1:])
cnt += 1
else:
for x in adjacent[space]:
if x == moves[-1][1]: continue
p = board[x]
board[space] = p
board[x] = 0
moves.append((x, space))
dfs(n + 1, board, goal, x, limit, moves)
moves.pop()
board[x] = p
board[space] = 0
def solver_ids(start, goal):
global cnt
cnt = 0
limit = 1
while True:
print(f'---- {limit} -----')
dfs(0, start, goal, start.index(0), limit, [(-1, -1)])
if cnt > 0: break
limit += 1
print('総数 =', cnt)
基本的には「７パズル」と同じです。７パズルでは、1 手前の駒を続けて動かさないようにするため駒の種類をチェックしました。ところが、今回のパズルは同じ駒が複数あるため、この方法を適用することはできません。そこで、駒の移動元と移動先の位置を手順を表す movesに格納して、動かす駒の位置でチェックすることにします。
moves の要素はタプル (移動元の位置, 移動先の位置) です。動かす駒の位置 x が 1 手前の移動先の位置 moves[-1][1] と同じであれば、同じ駒を続けて動かすことになります。この場合は x の駒を動かしません。
実行結果を示します。
>>> s = time.time(); solver_ids(list(start), list(goal)); print(time.time() - s) ---- 1 ----- ---- 2 ----- ---- 3 ----- ・・・省略・・・ ---- 28 ----- ---- 29 ----- ---- 30 ----- [(1, 4), (0, 1), (3, 0), (4, 3), (7, 4), (8, 7), (5, 8), (2, 5), (1, 2), (4, 1), (7, 4), (6, 7), (3, 6), (4, 3), (7, 4), (8, 7), (5, 8), (2, 5), (1, 2), (4, 1), (7, 4), (8, 7), (5, 8), (2, 5), (1, 2), (0, 1), (3, 0), (6, 3), (7, 6), (4, 7)] [(1, 4), (0, 1), (3, 0), (6, 3), (7, 6), (8, 7), (5, 8), (2, 5), (1, 2), (4, 1), (7, 4), (8, 7), (5, 8), (2, 5), (1, 2), (4, 1), (3, 4), (0, 3), (1, 0), (4, 1), (7, 4), (8, 7), (5, 8), (2, 5), (1, 2), (4, 1), (3, 4), (6, 3), (7, 6), (4, 7)] ・・・省略・・・ [(7, 4), (8, 7), (5, 8), (2, 5), (1, 2), (0, 1), (3, 0), (6, 3), (7, 6), (4, 7), (1, 4), (0, 1), (3, 0), (6, 3), (7, 6), (4, 7), (5, 4), (8, 5), (7, 8), (4, 7), (1, 4), (0, 1), (3, 0), (6, 3), (7, 6), (4, 7), (5, 4), (2, 5), (1, 2), (4, 1)] [(7, 4), (8, 7), (5, 8), (4, 5), (1, 4), (0, 1), (3, 0), (6, 3), (7, 6), (4, 7), (1, 4), (2, 1), (5, 2), (4, 5), (1, 4), (0, 1), (3, 0), (6, 3), (7, 6), (4, 7), (1, 4), (0, 1), (3, 0), (6, 3), (7, 6), (8, 7), (5, 8), (2, 5), (1, 2), (4, 1)] 総数 = 16 91.38984990119934
最短手数は 30 手で 16 通りの手順が表示されました。実行時間は約 92 秒かかりました。単純な反復深化なので、時間がかかるのはしかたがありません。そこで、反復深化の常套手段である「下限値枝刈り法」を使うことにしましょう。
下限値を求める方法ですが、「７パズル」と同じ方法 (移動距離) を採用します。ただし、今回のパズルは同じ駒が複数あるので、この方法をそのまま適用することはできません。次の図を見てください。
┌─┬─┬─┐ ┌─┬─┬─┐ ┌─┬─┬─┐
│┌┼─┼┐│ │０│１│２│ │１│２│１│
├┼┼─┼┼┤ ├─┼─┼─┤ ├─┼─┼─┤
│││ │││ │３│４│５│ │０│１│０│
├┼┼─┼┼┤ ├─┼─┼─┤ ├─┼─┼─┤
│└┼─┼┘│ │６│７│８│ │１│２│１│
└─┴─┴─┘ └─┴─┴─┘ └─┴─┴─┘
ＧＯＡＬ 番号 駒 │ の移動手数
図 : 下限値の求め方
駒│に注目してください。3 番と 5 番は正しい位置なので、移動手数は 0 でいいですね。│が 0 番にある場合、3 番に移動すれば 1 手ですが 5 番に移動すれば 3 手かかります。この場合は短い方の手数を移動手数とします。このとき、もうひとつの駒│が 3 番にある場合は 5 番へ移動しなければいけませんが、それでも移動手数は 1 手とします。つまり、もうひとつの駒の位置を考慮しないで移動手数を求めるのです。下限値の精度は低下しますが、そのかわりプログラムは簡単になります。
移動手数は二次元配列 (Python ではリストのリスト) に格納します。
リスト : マンハッタン距離
distance = [
[0, 0, 0, 0, 0, 0, 0, 0, 0], # dummy
[0, 1, 2, 1, 2, 3, 2, 3, 4], # 1
[1, 0, 1, 2, 1, 2, 1, 0, 1], # 2
[2, 1, 0, 3, 2, 1, 4, 3, 2], # 3
[1, 2, 1, 0, 1, 0, 1, 2, 1], # 4
[2, 3, 4, 1, 2, 3, 0, 1, 2], # 5
[4, 3, 2, 3, 2, 1, 2, 1, 0], # 6
]
def get_lower_value(b):
lower = 0
for i, p in enumerate(b):
lower += distance[p][i]
return lower
あとは「７パズル」で作成したプログラムとほとんど同じです。ただし、同じ駒を続けて動かさないようにチェックする処理を修正します。
リスト : 下限値枝刈り法
def dfs1(n, board, goal, space, limit, lower, moves):
global cnt
if n == limit:
if board == goal:
print(moves[1:])
cnt += 1
else:
for x in adjacent[space]:
if x == moves[-1][1]: continue
p = board[x]
newlower = lower - distance[p][x] + distance[p][space]
if n + newlower > limit: continue
board[space] = p
board[x] = 0
moves.append((x, space))
dfs1(n + 1, board, goal, x, limit, newlower, moves)
moves.pop()
board[x] = p
board[space] = 0
def solver_ids1(start, goal):
global cnt
cnt = 0
lower = get_lower_value(start)
limit = lower
while True:
print(f'---- {limit} -----')
dfs1(0, start, goal, start.index(0), limit, lower, [(-1, -1)])
if cnt > 0: break
limit += 1
print('総数 =', cnt)
とくに難しいところはないでしょう。詳細はプログラムリストをお読みくださいませ。
実行結果を示します。
>>> s = time.time(); solver_ids1(list(start), list(goal)); print(time.time() - s) ---- 24 ----- ---- 25 ----- ---- 26 ----- ---- 27 ----- ---- 28 ----- ---- 29 ----- ---- 30 ----- [(1, 4), (0, 1), (3, 0), (4, 3), (7, 4), (8, 7), (5, 8), (2, 5), (1, 2), (4, 1), (7, 4), (6, 7), (3, 6), (4, 3), (7, 4), (8, 7), (5, 8), (2, 5), (1, 2), (4, 1), (7, 4), (8, 7), (5, 8), (2, 5), (1, 2), (0, 1), (3, 0), (6, 3), (7, 6), (4, 7)] [(1, 4), (0, 1), (3, 0), (6, 3), (7, 6), (8, 7), (5, 8), (2, 5), (1, 2), (4, 1), (7, 4), (8, 7), (5, 8), (2, 5), (1, 2), (4, 1), (3, 4), (0, 3), (1, 0), (4, 1), (7, 4), (8, 7), (5, 8), (2, 5), (1, 2), (4, 1), (3, 4), (6, 3), (7, 6), (4, 7)] ・・・省略・・・ [(7, 4), (8, 7), (5, 8), (2, 5), (1, 2), (0, 1), (3, 0), (6, 3), (7, 6), (4, 7), (1, 4), (0, 1), (3, 0), (6, 3), (7, 6), (4, 7), (5, 4), (8, 5), (7, 8), (4, 7), (1, 4), (0, 1), (3, 0), (6, 3), (7, 6), (4, 7), (5, 4), (2, 5), (1, 2), (4, 1)] [(7, 4), (8, 7), (5, 8), (4, 5), (1, 4), (0, 1), (3, 0), (6, 3), (7, 6), (4, 7), (1, 4), (2, 1), (5, 2), (4, 5), (1, 4), (0, 1), (3, 0), (6, 3), (7, 6), (4, 7), (1, 4), (0, 1), (3, 0), (6, 3), (7, 6), (8, 7), (5, 8), (2, 5), (1, 2), (4, 1)] 総数 = 16 0.39739060401916504
当然ですが最短手数は 30 手、実行時間は約 0.4 秒でした。下限値枝刈り法の効果は絶大で、200 倍以上高速化することができました。解をひとつ求めたら探索を終了すると、もう少し速くなるかもしれません。興味のある方は挑戦してみてください。
#
# eight1.py : 変形版８パズル
#
# Copyright (C) 2022 Makoto Hiroi
#
import time
from collections import deque
# 盤面
# 0 1 2
# 3 4 5
# 6 7 8
# 隣接リスト
adjacent = [
[1, 3], # 0
[0, 2, 4], # 1
[1, 5], # 2
[0, 4, 6], # 3
[1, 3, 5, 7], # 4
[2, 4, 8], # 5
[3, 7], # 6
[4, 6, 8], # 7
[5, 7] # 8
]
# 問題
start = (6,4,5,2,0,2,3,4,1)
goal = (1,2,3,4,0,4,5,2,6)
# 駒の種類
piece_list = ['□', '┌', '─', '┐', '│', '└', '┘']
# 盤面の表示
def print_board(b):
for i, p in enumerate(b):
print(piece_list[p], end='')
if (i + 1) % 3 == 0: print()
print()
# 手順の表示
def print_moves(b, table):
if b:
print_moves(table[b], table)
print_board(b)
# 駒の移動
def move_piece(b, n, s):
a = list(b)
a[s] = a[n]
a[n] = 0
return tuple(a)
# 幅優先探索
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 = [(goal, goal.index(0))]
check = {}
check[goal] = 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))
# 反復深化
def dfs(n, board, goal, space, limit, moves):
global cnt
if n == limit:
if board == goal:
print(moves[1:])
cnt += 1
else:
for x in adjacent[space]:
if x == moves[-1][1]: continue
p = board[x]
board[space] = p
board[x] = 0
moves.append((x, space))
dfs(n + 1, board, goal, x, limit, moves)
moves.pop()
board[x] = p
board[space] = 0
def solver_ids(start, goal):
global cnt
cnt = 0
limit = 1
while True:
print(f'---- {limit} -----')
dfs(0, start, goal, start.index(0), limit, [(-1, -1)])
if cnt > 0: break
limit += 1
print('総数 =', cnt)
#
# 下限値枝刈り法
#
# マンハッタン距離
# 1,2,3,
# 4,0,4,
# 5,2,6
distance = [
[0, 0, 0, 0, 0, 0, 0, 0, 0], # dummy
[0, 1, 2, 1, 2, 3, 2, 3, 4], # 1
[1, 0, 1, 2, 1, 2, 1, 0, 1], # 2
[2, 1, 0, 3, 2, 1, 4, 3, 2], # 3
[1, 2, 1, 0, 1, 0, 1, 2, 1], # 4
[2, 3, 4, 1, 2, 3, 0, 1, 2], # 5
[4, 3, 2, 3, 2, 1, 2, 1, 0], # 6
]
def get_lower_value(b):
lower = 0
for i, p in enumerate(b):
lower += distance[p][i]
return lower
def dfs1(n, board, goal, space, limit, lower, moves):
global cnt
if n == limit:
if board == goal:
print(moves[1:])
cnt += 1
else:
for x in adjacent[space]:
if x == moves[-1][1]: continue
p = board[x]
newlower = lower - distance[p][x] + distance[p][space]
if n + newlower > limit: continue
board[space] = p
board[x] = 0
moves.append((x, space))
dfs1(n + 1, board, goal, x, limit, newlower, moves)
moves.pop()
board[x] = p
board[space] = 0
def solver_ids1(start, goal):
global cnt
cnt = 0
lower = get_lower_value(start)
limit = lower
while True:
print(f'---- {limit} -----')
dfs1(0, start, goal, start.index(0), limit, lower, [(-1, -1)])
if cnt > 0: break
limit += 1
print('総数 =', cnt)