問題の説明
今回はスライドパズル Goat を解いてみましょう。
[問題] スライドパズル Goat
∥ は扉を表します。当然ですが、大きな駒 (2 マス) は左右に動かすことができます。START から羊を囲いの中に入れる GOAL までの最短手順を求めてください。
このパズルは Goat や Get My Goat と呼ばれていて、スライドパズルではよく知られている問題です。今回のパズルは駒の種類と配置をちょっと変更しているので、最短手順はオリジナルの Goat とは異なります。ご注意ください。オリジナルの Goat は、下記のページでプレイすることができます。
●単純な反復深化
このパズルの場合、大きな駒の置き方は 3 通りしかありません。残りの場所は 10 か所ありますが、7 種類の駒 (┘ ┌ └ │ ∥ 羊 狼) と空き場所を配置して残り 2 か所に駒 ─ を配置すると 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 = 1,814,400 通りの置き方があります。したがって、局面の総数は 3 * 1814400 = 5,443,200 通りになります。ちょっと大きな数なので、今回は反復深化で解くことにしましょう。使用するプログラミング言語は Python3 (ver 3.8.10) です。
盤面は一次元配列 (Python のリスト) で表します。配列の添字と盤面の対応は下図のようになります。
駒の定義ですが、いつものように空き場所を 0 で表し、小さな駒を 1 から 8 までの数字で、大きな駒を B1 (9) と B2 (10) の 2 つに分けて表します。大きな駒を移動するときは、B1 と B2 をいっしょに動かすようにします。この処理がちょっとだけ複雑になりますが、あとのプログラムは単純な反復深化なので簡単です。
次は大域変数を定義します。
リスト : 大域変数の定義
# 定数
S = 0
B1 = 9
B2 = 10
# 隣接リスト
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], # 8
[5, 8, 10], # 9
[6, 9, 11], # 10
[7, 10] # 11
]
# スタート
start = (
1, 8,B1,B2,
2, S, 7, 5,
3, 8, 4, 6
)
# ゴール
goal = (
1, 8,B1,B2,
2, 5, 7, S,
3, 8, 4, 6
)
S は空き場所 (0) を、B1 (9) と B2 (10) は大駒を表します。リスト adjacent に隣接リストをセットします。start は START の局面、goal は GOAL の局面を表します。
次は駒を動かす関数 move_piece() を作ります。
リスト : 駒の移動
def move_piece(b, n, s):
if b[n] == B1:
if s > n: return -1, -1
b[s] = b[n]
b[n] = b[n + 1]
b[n + 1] = S
s1 = (n, n + 1)
elif b[n] == B2:
if s > 3: return -1, -1
b[s] = b[n]
b[n] = b[n - 1]
b[n - 1] = S
s1 = (n, n - 1)
else:
b[s] = b[n]
b[n] = 0
s1 = (s, n)
return s1
move_piece() の引数 b が盤面、n は動かす駒の位置、s が空き場所の位置を表します。move_piece() は移動先の位置と移動元の位置を返します。移動元の位置が空き場所になります。駒を動かせない場合は (-1, -1) を返します。大きな駒以外の場合、駒と空き場所を交換するだけなので簡単です。
大きな駒は左から B1 (9), B2 (10) と並んでいるので、b[n] が B1 (9) ならば大きな駒を左へ動かすことになります。次の図を見てください。
s の位置に B1 を、n の位置に B2 を移動し、S は n + 1 の位置に移動します。B2 を動かす場合は、s の位置に B2 を、n の位置に B1 を移動し、S は n - 1 の位置に移動します。
B1 を動かすときの返り値は、B2 を動かす (n + 1 -> n) と考えて (n, n + 1) とします。逆に、B2 を動かすときは B1 を動かす (n - 1 -> n) と考えて (n, n - 1) とします。こうすると、同じ駒を続けて動かすときのチェックや盤面を元に戻すときの処理が簡単になります。
次は、反復深化で解を探索するプログラムを作ります。次のリストを見てください。
リスト : 反復深化による探索
def dfs(n, board, goal, space, limit, moves):
if n == limit:
if board == goal:
print_moves(board, moves[1:])
return True
else:
for x in adjacent[space]:
if x == moves[-1][1]: continue
x1, s1 = move_piece(board, x, space)
if s1 != -1:
moves.append((s1, x1))
if dfs(n + 1, board, goal, s1, limit, moves):
return True
moves.pop()
move_piece(board, x1, s1)
return False
関数 dfs() の引数 n が手数、board が盤面、goal がゴールの盤面、space が空き場所の位置、limit が反復深化の上限値、move が移動手順を表します。このパズルは駒 ─ が 2 つあるので、移動手順は動かす駒の位置で表すことにします。移動手順 moves の要素はタプル (from, to) で、from が移動する駒の位置、to が移動先の位置です。
n が limit と等しくなったら、goal に到達したかチェックします。そうでなければ、駒を動かして次の局面を生成します。動かす駒の位置 x が moves[-1][1] と等しい場合、元の局面に戻るので x にある駒は動かしません。このチェックを入れないと、実行速度はかなり遅くなるので注意してください。
次に、move_piece() で駒を移動します。返り値を変数 x1, s1 にセットします。駒を移動できる場合、moves に (s1, x1) を追加します。たとえば、大きな駒の移動図で 2 にある駒 B1 を 1 へ移動した場合、空き場所は 1 から 3 へ移動します。move_piece() の返り値は (2, 3) になります。このあと、2 の位置にある駒 B2 を 3 へ動かせば元の局面に戻りますね。したがって、moves には (3, 2) をセットします。
そのあと dfs() を再帰呼び出しして、戻ってきたら盤面を元に戻します。空き場所 s1 の隣に x1 があるので、move_piece() に x1 と s1 を渡して呼び出せば、元の盤面に戻すことができます。
あとはとくに難しいところはないと思います。詳細は プログラムリスト をお読みくださいませ。
●実行結果
それでは実行結果を示します。図では空き場所を □ で表しています。
>>> s = time.time(); solver_ids(list(start), list(goal)); print(time.time() - s) ---- 1 ----- ---- 2 ----- ---- 3 ----- ・・・省略・・・ ---- 18 ----- ---- 19 ----- ---- 20 ----- ┌ ─ ┐ │ □ ∥ 羊 └ ─ ┘ 狼 ┌ □ ┐ │ ─ ∥ 羊 └ ─ ┘ 狼 ┌ ┐ □ │ ─ ∥ 羊 └ ─ ┘ 狼 ・・・省略・・・ ┌ ─ ┐ │ □ 羊 ∥ └ ─ ┘ 狼 ┌ ─ ┐ │ 羊 □ ∥ └ ─ ┘ 狼 ┌ ─ ┐ │ 羊 ∥ □ └ ─ ┘ 狼 0.584336519241333 実行環境 : Python3 (ver 3.8.10), Ubunts 20.04 (WSL1), Intel Core i5-6200U 2.30GHz
最短手数は 20 手になります。これは Memorandum 2002 年 9 月 30 日 で Y. N. さんが求めた手順と同じです。手数が短いので単純な反復深化でも 1 秒未満で解くことができました。
●最長手数の局面
次は GOAL から始めて最長手数となる局面を幅優先探索で求めてみましょう。盤面の総数は 5,443,200 通りあるのですが、最近のパソコンはメモリの搭載量が多いので (M.Hiroi のパソコンは 8 G byte)、単純な幅優先探索でも解を求めることが可能です。
プログラムは次のようになります。
リスト : 最長手数の局面
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 = list(b)
_, s1 = move_piece(a, n, s)
c = tuple(a)
if c in check: continue
ys.append((c, s1))
check[c] = True
if not ys: break
xs = ys
move += 1
print(f'手数 {move}, 個数 {len(xs)}')
print('最長手数 =', move, '個数 =', len(xs))
for b in xs: print_board(b[0])
print('状態の総数 =', len(check))
今まで作成した最長手数を求めるプログラムとほとんど同じなので、とくに難しいところはないと思います。
●実行結果 (2)
それでは実行結果を示します。Python3 では時間がかかるので PyPy3 を使いました。
>>>> s = time.time(); solver_max(); print(time.time() - s) 手数 1, 個数 2 手数 2, 個数 3 手数 3, 個数 7 手数 4, 個数 13 手数 5, 個数 20 手数 6, 個数 37 手数 7, 個数 57 手数 8, 個数 103 手数 9, 個数 161 手数 10, 個数 273 手数 11, 個数 414 手数 12, 個数 693 手数 13, 個数 1057 手数 14, 個数 1737 手数 15, 個数 2584 手数 16, 個数 4162 手数 17, 個数 6181 手数 18, 個数 9774 手数 19, 個数 14242 手数 20, 個数 21637 手数 21, 個数 30774 手数 22, 個数 45069 手数 23, 個数 61806 手数 24, 個数 86121 手数 25, 個数 113434 手数 26, 個数 149621 手数 27, 個数 187650 手数 28, 個数 232743 手数 29, 個数 276099 手数 30, 個数 321314 手数 31, 個数 360502 手数 32, 個数 392621 手数 33, 個数 413094 手数 34, 個数 417811 手数 35, 個数 409576 手数 36, 個数 382164 手数 37, 個数 346339 手数 38, 個数 297291 手数 39, 個数 247704 手数 40, 個数 194081 手数 41, 個数 147352 手数 42, 個数 104416 手数 43, 個数 70454 手数 44, 個数 43976 手数 45, 個数 25441 手数 46, 個数 13330 手数 47, 個数 5904 手数 48, 個数 2408 手数 49, 個数 717 手数 50, 個数 194 手数 51, 個数 29 手数 52, 個数 7 最長手数 = 52 個数 = 7 狼 ∥ ┐ ┘ 羊 └ ┌ □ ─ │ ─ 狼 ┐ ┌ ∥ 羊 │ ─ ┘ ─ └ □ ∥ 狼 ┐ ┘ 羊 ┌ □ ─ └ │ ─ □ ∥ ┐ 狼 ┘ │ ─ ─ 羊 └ ┌ 狼 ∥ ┐ ┘ 羊 │ ─ □ ─ └ ┌ □ ∥ ┐ 狼 ┘ │ ┌ 羊 ─ └ ─ ∥ 狼 ┐ ┘ 羊 │ ┌ □ ─ └ ─ 状態の総数 = 5443200 20.930742502212524 実行環境 : PyPy3 (ver 7.3.1), Ubunts 20.04 (WSL1), Intel Core i5-6200U 2.30GHz
最長手数は 52 手で、その局面は全部で 7 通りありました。実行時間は約 21 秒かかりました。ちなみに、生成した局面は全部で 5,443,200 個あります。しがたって、このパズルは小さな駒をランダムに配置しても、必ず GOAL に到達できることがわかります。
●最長手数の局面を反復深化で解く
次は最長手数の局面を「反復深化」で解いてみましょう。
手数が 52 手と長いので、今回は １１パズル で用いた「手数の偶奇性」と「下限値枝刈り法」を使います。下限値は駒の「移動手数」で求めることにします。駒 ─ は 2 つありますが、その移動手数を求める方法がポイントです。次の図を見てください。
駒 ─ に注目してください。1 番と 9 番は正しい位置なので、移動手数は 0 でいいですね。─ が 0 番にある場合、1 番に移動すれば 1 手ですが 9 番に移動すれば 3 手かかります。この場合は短い方の手数を移動手数とします。
このとき、もうひとつの駒 ─ が 1 番にある場合は 9 番へ移動しなければいけませんが、それでも移動手数は 1 手とします。つまり、もうひとつの駒の位置を考慮しないで移動手数を求めるのです。下限値の精度は低下しますが、そのかわりプログラムは簡単になります。
移動手数は二次元配列 distance に格納します。
リスト : 移動手数
# 移動手数
distance = [
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], # dummy
[0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5], # 1
[1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4], # 2
[2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3], # 3
[4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1], # 4
[2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3], # 5
[5, 4, 3, 2, 4, 3, 2, 1, 3, 2, 1, 0], # 6
[3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2], # 7
[1, 0, 1, 2, 2, 1, 2, 3, 1, 0, 1, 2], # 8
[2, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0], # 9
[3, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0] # 10
]
# 下限値を求める
def get_lower_value(board):
lower = 0
for i, p in enumerate(board):
if p > 0 and p != B2: lower += distance[p][i];
return lower
大きな駒は B1 と B2 に分けて表しているので、下限値を求めるときは移動手数を重複してカウントしないように注意してください。
次は、下限値枝刈り法のプログラムを作ります。
リスト : 反復深化＋下限値枝刈り法
def dfs1(n, board, goal, space, limit, lower, moves):
if n == limit:
if board == goal:
print_moves(board, moves[1:])
return True
else:
for x in adjacent[space]:
if x == moves[-1][1]: continue
x1, s1 = move_piece(board, x, space)
if s1 != -1:
p = board[x1]
if p == B1:
newlower = lower - 1
elif p == B2:
newlower = lower + 1
else:
newlower = lower - distance[p][s1] + distance[p][x1]
if n + newlower <= limit:
moves.append((s1, x1))
if dfs1(n + 1, board, goal, s1, limit, newlower, moves):
return True
moves.pop()
move_piece(board, x1, s1)
return False
関数 dfs1() の引数 lower が下限値を表します。駒を動かしたら差分を計算して、新しい下限値 newlower を求めます。大きな駒を動かす場合、移動手数表 distance を使わなくても新しい下限値を簡単に求めることができます。大きな駒を左へ動かすと下限値 lower は 1 つ増加し、右へ動かすと 1 つ減少します。新しい下限値を newlower にセットして、n + newlower が上限値 limit を越えたら枝刈りを行います。limit 以下であれば dfs1() を再帰呼び出しします。
あとは START (大域変数 start1) の局面の下限値を求め、その手数から反復深化を実行するだけです。詳細は プログラムリスト をお読みくださいませ。
●実行結果 (3)
実行結果は次のようになりました。
>>>> s = time.time(); solver_ids1(list(start1), list(goal)); print(time.time() - s) ---- 22 ----- ---- 24 ----- ---- 26 ----- ・・・省略・・・ ---- 48 ----- ---- 50 ----- ---- 52 ----- 狼 ∥ ┐ ┘ 羊 │ ─ □ ─ └ ┌ 狼 ∥ ┐ □ 羊 │ ─ ┘ ─ └ ┌ □ ∥ ┐ 狼 羊 │ ─ ┘ ─ └ ┌ ・・・省略・・・ ┌ ─ ┐ │ 羊 ∥ 狼 └ ─ □ ┘ ┌ ─ ┐ │ 羊 ∥ 狼 └ ─ ┘ □ ┌ ─ ┐ │ 羊 ∥ □ └ ─ ┘ 狼 52.063156604766846
当然ですが手数は 52 手で、実行時間は PyPy3 で約 52 秒かかりました。下限値の精度が低いので、長い手数の問題は PyPy3 でも少々時間がかかります。それでも 1 分かからずに解を求めることができたので、手数の偶奇性と下限値枝刈り法の効果は十分に出ていると思います。下限値の精度を改善すると、もう少し速くなるかもしれません。興味のある方は挑戦してみてください。
●プログラムリスト
#
# goat.py : スライドパズル Goat
#
# Copyright (C) 2022 Makoto Hiroi
#
import time
# 定数
S = 0
B1 = 9
B2 = 10
# 駒の名前
piece_name = ('□', '┌', '│', '└', '┘', '羊', '狼', '∥', '─', '┐', ' ')
# 盤面
# 0 1 2 3
# 4 5 6 7
# 8 9 10 11
# 隣接リスト
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], # 8
[5, 8, 10], # 9
[6, 9, 11], # 10
[7, 10] # 11
]
# スタート
start = (
1, 8,B1,B2,
2, S, 7, 5,
3, 8, 4, 6
)
start1 = (
6, 7,B1,B2,
4, 5, 2, 8,
S, 8, 3, 1
)
# ゴール
goal = (
1, 8,B1,B2,
2, 5, 7, S,
3, 8, 4, 6
)
# 駒の移動
def move_piece(b, n, s):
if b[n] == B1:
if s > n: return -1, -1
b[s] = b[n]
b[n] = b[n + 1]
b[n + 1] = S
s1 = (n, n + 1)
elif b[n] == B2:
if s > 3: return -1, -1
b[s] = b[n]
b[n] = b[n - 1]
b[n - 1] = S
s1 = (n, n - 1)
else:
b[s] = b[n]
b[n] = 0
s1 = (s, n)
return s1
def print_board(board):
for i, p in enumerate(board):
print(piece_name[p], end=' ')
if (i + 1) % 4 == 0: print()
print()
def print_moves(board, moves):
if len(moves) > 0:
b = board[:]
s, d = moves[-1]
move_piece(b, d, s)
print_moves(b, moves[:-1])
print_board(board)
# 反復深化
def dfs(n, board, goal, space, limit, moves):
if n == limit:
if board == goal:
print_moves(board, moves[1:])
return True
else:
for x in adjacent[space]:
if x == moves[-1][1]: continue
x1, s1 = move_piece(board, x, space)
if s1 != -1:
moves.append((s1, x1))
if dfs(n + 1, board, goal, s1, limit, moves):
return True
moves.pop()
move_piece(board, x1, s1)
return False
def solver_ids(start, goal):
limit = 1
while True:
print(f'---- {limit} -----')
if dfs(0, start, goal, start.index(0), limit, [(-1, -1)]):
break
limit += 1
# 最長手数の局面
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 = list(b)
_, s1 = move_piece(a, n, s)
c = tuple(a)
if c in check: continue
ys.append((c, s1))
check[c] = True
if not ys: break
xs = ys
move += 1
print(f'手数 {move}, 個数 {len(xs)}')
print('最長手数 =', move, '個数 =', len(xs))
for b in xs: print_board(b[0])
print('状態の総数 =', len(check))
#
# 下限値枝刈り法
#
# 手数の偶奇性
parity = (
1, 0, 1, 0,
0, 1, 0, 1,
1, 0, 1, 0
)
# 移動手数
distance = [
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], # dummy
[0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5], # 1
[1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4], # 2
[2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3], # 3
[4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1], # 4
[2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3], # 5
[5, 4, 3, 2, 4, 3, 2, 1, 3, 2, 1, 0], # 6
[3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2], # 7
[1, 0, 1, 2, 2, 1, 2, 3, 1, 0, 1, 2], # 8
[2, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0], # 9
[3, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0] # 10
]
# 下限値を求める
def get_lower_value(board):
lower = 0
for i, p in enumerate(board):
if p > 0 and p != B2: lower += distance[p][i];
return lower
# 反復深化＋下限値枝刈り法
def dfs1(n, board, goal, space, limit, lower, moves):
if n == limit:
if board == goal:
print_moves(board, moves[1:])
return True
else:
for x in adjacent[space]:
if x == moves[-1][1]: continue
x1, s1 = move_piece(board, x, space)
if s1 != -1:
p = board[x1]
if p == B1:
newlower = lower - 1
elif p == B2:
newlower = lower + 1
else:
newlower = lower - distance[p][s1] + distance[p][x1]
if n + newlower <= limit:
moves.append((s1, x1))
if dfs1(n + 1, board, goal, s1, limit, newlower, moves):
return True
moves.pop()
move_piece(board, x1, s1)
return False
def solver_ids1(start, goal):
lower = get_lower_value(start)
ss = start.index(0)
gs = goal.index(0)
if parity[ss] != parity[gs]:
if lower % 2 == 0: lower += 1
elif lower % 2 == 1:
lower += 1
limit = lower
while True:
print(f'---- {limit} -----')
if dfs1(0, start, goal, start.index(0), limit, lower, [(-1, -1)]):
break
limit += 2
改訂 2022 年 11 月 12 日