今回は「８パズル」をひとつ大きくした「9 パズル」を取り上げます。
┌─┬─┬─┬─┬─┐ ┌─┬─┬─┬─┬─┐
│ │９│８│７│６│ │１│２│３│４│５│
├─┼─┼─┼─┼─┤ => ├─┼─┼─┼─┼─┤
│５│４│３│２│１│ │６│７│８│９│ │
└─┴─┴─┴─┴─┘ └─┴─┴─┴─┴─┘
スタート ゴール
図 : ９パズル
8 パズルは 3 行 3 列の盤ですが、9 パズルは 2 行 5 列と盤を大きくしたパズルです。9 パズルは、空き場所がどこでもいいことにすると、駒の配置は 10! = 3,628,800 通りあります。ところが 8 パズルや 9 パズルの場合、参考文献『特集コンピュータパズルへの招待 スライディングブロック編』によると、『適当な 2 つの駒をつまみ上げて交換する動作を偶数回行った局面にした移行できない』 ことが証明されているそうです。
たとえば、上図のゴールで 8 と 9 を入れ替えただけの配置は、交換の回数が奇数回のためゴールに到達することができない、つまり解くことができないのです。このような性質を「偶奇性 (パリティ)」といいます。興味のある方は拙作のページ「偶奇性のお話」をお読みください。したがって、ゴールに到達する局面の総数は 10! / 2 = 1,814,400 通りとなります。
上図の場合、駒を順番に左回り (9, 8, 7, 6, 1, 2, 3, 4, 5) または右回り (5, 4, 3, 2, 1, 6, 7, 8, 9) していくだけで解くことができます。5 回転させるとゴールに到達するので、その手数は 45 手になります。これが最短手数になるのか、Python3 (ver 3.8.10) でプログラムを作って確かめてみましょう。
それではプログラムを作りましょう。スタートからゴールに到達するまでの最短手数を幅優先探索で求めます。盤面は一次元配列 (Python のタプル) を使って表します。隣接リストの定義は次のようになります。
リスト : 隣接リスト
# 盤面
# 0 1 2 3 4
# 5 6 7 8 9
# 隣接リスト
adjacent0 = [
[1, 5], # 0
[0, 2, 6], # 1
[1, 3, 7], # 2
[2, 4, 8], # 3
[3, 9], # 4
[0, 6], # 5
[1, 5, 7], # 6
[2, 6, 8], # 7
[3, 7, 9], # 8
[4, 8] # 9
]
変数 adjacent0 に隣接リストをセットします。あとで 9 パズルの変形版も解きたいので、今回は幅優先探索を行う関数 bfs() に隣接リストを渡すことにします。bfs() は次のようになります。
リスト : 幅優先探索
def bfs(start, goal, adjacent = adjacent0):
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
引数 start, goal はスタートとゴールの盤面、引数 adjacent には隣接リストを渡します。キューは Python の標準ライブラリ collections にあるクラス deque を使います。あとは「７パズル」で作成したプログラムとほとんど同じなので、説明は割愛させていただきます。詳細はプログラムリストをお読みください。
これでプログラムは完成です。それでは実行してみましょう。
>>> s = time.time(); bfs((0,9,8,7,6,5,4,3,2,1), (1,2,3,4,5,6,7,8,9,0)); time.time() - s (0, 9, 8, 7, 6, 5, 4, 3, 2, 1) (9, 0, 8, 7, 6, 5, 4, 3, 2, 1) (9, 8, 0, 7, 6, 5, 4, 3, 2, 1) (9, 8, 7, 0, 6, 5, 4, 3, 2, 1) (9, 8, 7, 6, 0, 5, 4, 3, 2, 1) (9, 8, 7, 6, 1, 5, 4, 3, 2, 0) (9, 8, 7, 6, 1, 5, 4, 3, 0, 2) (9, 8, 7, 6, 1, 5, 4, 0, 3, 2) (9, 8, 7, 6, 1, 5, 0, 4, 3, 2) (9, 8, 7, 6, 1, 0, 5, 4, 3, 2) (0, 8, 7, 6, 1, 9, 5, 4, 3, 2) (8, 0, 7, 6, 1, 9, 5, 4, 3, 2) (8, 7, 0, 6, 1, 9, 5, 4, 3, 2) (8, 7, 6, 0, 1, 9, 5, 4, 3, 2) (8, 7, 6, 1, 0, 9, 5, 4, 3, 2) (8, 7, 6, 1, 2, 9, 5, 4, 3, 0) (8, 7, 6, 1, 2, 9, 5, 4, 0, 3) (8, 7, 6, 1, 2, 9, 5, 0, 4, 3) (8, 7, 6, 1, 2, 9, 0, 5, 4, 3) (8, 7, 6, 1, 2, 0, 9, 5, 4, 3) (0, 7, 6, 1, 2, 8, 9, 5, 4, 3) (7, 0, 6, 1, 2, 8, 9, 5, 4, 3) (7, 6, 0, 1, 2, 8, 9, 5, 4, 3) (7, 6, 1, 0, 2, 8, 9, 5, 4, 3) (7, 6, 1, 2, 0, 8, 9, 5, 4, 3) (7, 6, 1, 2, 3, 8, 9, 5, 4, 0) (7, 6, 1, 2, 3, 8, 9, 5, 0, 4) (7, 6, 1, 2, 3, 8, 9, 0, 5, 4) (7, 6, 1, 2, 3, 8, 0, 9, 5, 4) (7, 6, 1, 2, 3, 0, 8, 9, 5, 4) (0, 6, 1, 2, 3, 7, 8, 9, 5, 4) (6, 0, 1, 2, 3, 7, 8, 9, 5, 4) (6, 1, 0, 2, 3, 7, 8, 9, 5, 4) (6, 1, 2, 0, 3, 7, 8, 9, 5, 4) (6, 1, 2, 3, 0, 7, 8, 9, 5, 4) (6, 1, 2, 3, 4, 7, 8, 9, 5, 0) (6, 1, 2, 3, 4, 7, 8, 9, 0, 5) (6, 1, 2, 3, 4, 7, 8, 0, 9, 5) (6, 1, 2, 3, 4, 7, 0, 8, 9, 5) (6, 1, 2, 3, 4, 0, 7, 8, 9, 5) (0, 1, 2, 3, 4, 6, 7, 8, 9, 5) (1, 0, 2, 3, 4, 6, 7, 8, 9, 5) (1, 2, 0, 3, 4, 6, 7, 8, 9, 5) (1, 2, 3, 0, 4, 6, 7, 8, 9, 5) (1, 2, 3, 4, 0, 6, 7, 8, 9, 5) (1, 2, 3, 4, 5, 6, 7, 8, 9, 0) 4.487512826919556 実行環境 : Python3 (ver 3.8.10), Ubuntu 20.04 LTS (WSL1), Intel Core i5-6200U 2.30GHz
駒を左に 5 回転させる手順 (45 手) で解くことができました。実行時間は約 4.5 秒かかりました。双方向探索にすると、もう少し速くなると思います。調味のある方は挑戦してみてください。
次は最長手数の局面を求めてみましょう。次のリストを見てください。
リスト : 9 パズルの最長手数を求める
def solver_max(adjacent = adjacent0):
start = (1,2,3,4,5,6,7,8,9,0)
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(f'手数: {move}, 個数 = {len(xs)}')
print(f'最長手数 = {move}, 個数 = {len(xs)}')
for b in xs: print(b[0])
print('状態の総数 =', len(check))
引数 adjacent に隣接リストを渡します。あとは「７パズル」で作成したプログラムとほとんど同じなので、説明は割愛させていただきます。詳細はプログラムリストをお読みください。
実行結果は次のようになりました。
>>> s = time.time(); solver_max(); time.time() - s 手数: 1, 個数 = 2 手数: 2, 個数 = 3 手数: 3, 個数 = 6 手数: 4, 個数 = 11 手数: 5, 個数 = 19 手数: 6, 個数 = 30 手数: 7, 個数 = 44 手数: 8, 個数 = 68 手数: 9, 個数 = 112 手数: 10, 個数 = 176 手数: 11, 個数 = 271 手数: 12, 個数 = 411 手数: 13, 個数 = 602 手数: 14, 個数 = 851 手数: 15, 個数 = 1232 手数: 16, 個数 = 1783 手数: 17, 個数 = 2530 手数: 18, 個数 = 3567 手数: 19, 個数 = 4996 手数: 20, 個数 = 6838 手数: 21, 個数 = 9279 手数: 22, 個数 = 12463 手数: 23, 個数 = 16597 手数: 24, 個数 = 21848 手数: 25, 個数 = 28227 手数: 26, 個数 = 35682 手数: 27, 個数 = 44464 手数: 28, 個数 = 54597 手数: 29, 個数 = 65966 手数: 30, 個数 = 78433 手数: 31, 個数 = 91725 手数: 32, 個数 = 104896 手数: 33, 個数 = 116966 手数: 34, 個数 = 126335 手数: 35, 個数 = 131998 手数: 36, 個数 = 133107 手数: 37, 個数 = 128720 手数: 38, 個数 = 119332 手数: 39, 個数 = 106335 手数: 40, 個数 = 91545 手数: 41, 個数 = 75742 手数: 42, 個数 = 60119 手数: 43, 個数 = 45840 手数: 44, 個数 = 33422 手数: 45, 個数 = 23223 手数: 46, 個数 = 15140 手数: 47, 個数 = 9094 手数: 48, 個数 = 5073 手数: 49, 個数 = 2605 手数: 50, 個数 = 1224 手数: 51, 個数 = 528 手数: 52, 個数 = 225 手数: 53, 個数 = 75 手数: 54, 個数 = 20 手数: 55, 個数 = 2 最長手数 = 55, 個数 = 2 (0, 9, 3, 7, 1, 5, 4, 8, 2, 6) (0, 5, 3, 2, 1, 9, 4, 8, 7, 6) 状態の総数 = 1814400 4.4247236251831055
最長手数は 55 手で、局面は 2 通りあります。
┌─┬─┬─┬─┬─┐ ┌─┬─┬─┬─┬─┐
│ │９│３│７│１│ │ │５│３│２│１│
├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤
│５│４│８│２│６│ │９│４│８│７│６│
└─┴─┴─┴─┴─┘ └─┴─┴─┴─┴─┘
図 : 最長手数の局面
次は盤の形を変えた変形版９パズルを解いてみましょう。
[問題] ９パズル
┌─┬─┬─┐ ┌─┬─┬─┐
│ │９│８│ │１│２│３│
├─┼─┼─┼─┐ ├─┼─┼─┼─┐
│７│６│５│４│ │４│５│６│７│
└─┼─┼─┼─┤ └─┼─┼─┼─┤
│３│２│１│ │８│９│ │
└─┴─┴─┘ └─┴─┴─┘
ＳＴＡＲＴ ＧＯＡＬ
図 : ９パズル
START から GOAL までの最短手順を求めてください。
実はこのパズル、駒を左回り (9, 8, 5, 4, 1, 2, 3, 6, 7) または右回り (7, 6, 3, 2, 1, 4, 5, 8, 9) に 5 回転させると、45 手で解くことができます。これが最短手順になるのか、プログラムで確かめてみましょう。
>>> s = time.time(); bfs((0,9,8,7,6,5,4,3,2,1), (1,2,3,4,5,6,7,8,9,0), adjacent1); time.time() - s (0, 9, 8, 7, 6, 5, 4, 3, 2, 1) (9, 0, 8, 7, 6, 5, 4, 3, 2, 1) (9, 8, 0, 7, 6, 5, 4, 3, 2, 1) (9, 8, 5, 7, 6, 0, 4, 3, 2, 1) (9, 8, 5, 7, 6, 4, 0, 3, 2, 1) (9, 8, 5, 7, 6, 4, 1, 3, 2, 0) (9, 8, 5, 7, 6, 4, 1, 3, 0, 2) (9, 8, 5, 7, 6, 4, 1, 0, 3, 2) (9, 8, 5, 7, 0, 4, 1, 6, 3, 2) (9, 8, 5, 0, 7, 4, 1, 6, 3, 2) (0, 8, 5, 9, 7, 4, 1, 6, 3, 2) (8, 0, 5, 9, 7, 4, 1, 6, 3, 2) (8, 5, 0, 9, 7, 4, 1, 6, 3, 2) (8, 5, 4, 9, 7, 0, 1, 6, 3, 2) (8, 5, 4, 9, 7, 1, 0, 6, 3, 2) (8, 5, 4, 9, 7, 1, 2, 6, 3, 0) (8, 5, 4, 9, 7, 1, 2, 6, 0, 3) (8, 5, 4, 9, 7, 1, 2, 0, 6, 3) (8, 5, 4, 9, 0, 1, 2, 7, 6, 3) (8, 5, 4, 0, 9, 1, 2, 7, 6, 3) (0, 5, 4, 8, 9, 1, 2, 7, 6, 3) (5, 0, 4, 8, 9, 1, 2, 7, 6, 3) (5, 4, 0, 8, 9, 1, 2, 7, 6, 3) (5, 4, 1, 8, 9, 0, 2, 7, 6, 3) (5, 4, 1, 8, 9, 2, 0, 7, 6, 3) (5, 4, 1, 8, 9, 2, 3, 7, 6, 0) (5, 4, 1, 8, 9, 2, 3, 7, 0, 6) (5, 4, 1, 8, 9, 2, 3, 0, 7, 6) (5, 4, 1, 8, 0, 2, 3, 9, 7, 6) (5, 4, 1, 0, 8, 2, 3, 9, 7, 6) (0, 4, 1, 5, 8, 2, 3, 9, 7, 6) (4, 0, 1, 5, 8, 2, 3, 9, 7, 6) (4, 1, 0, 5, 8, 2, 3, 9, 7, 6) (4, 1, 2, 5, 8, 0, 3, 9, 7, 6) (4, 1, 2, 5, 8, 3, 0, 9, 7, 6) (4, 1, 2, 5, 8, 3, 6, 9, 7, 0) (4, 1, 2, 5, 8, 3, 6, 9, 0, 7) (4, 1, 2, 5, 8, 3, 6, 0, 9, 7) (4, 1, 2, 5, 0, 3, 6, 8, 9, 7) (4, 1, 2, 0, 5, 3, 6, 8, 9, 7) (0, 1, 2, 4, 5, 3, 6, 8, 9, 7) (1, 0, 2, 4, 5, 3, 6, 8, 9, 7) (1, 2, 0, 4, 5, 3, 6, 8, 9, 7) (1, 2, 3, 4, 5, 0, 6, 8, 9, 7) (1, 2, 3, 4, 5, 6, 0, 8, 9, 7) (1, 2, 3, 4, 5, 6, 7, 8, 9, 0) 4.518330097198486
(0) (1) (2) (3) (4) (5) (6) (7) (8) (9)
0 9 8 9 0 8 9 8 0 9 8 5 9 8 5 9 8 5 9 8 5 9 8 5 9 8 5 9 8 5
7 6 5 4 7 6 5 4 7 6 5 4 7 6 0 4 7 6 4 0 7 6 4 1 7 6 4 1 7 6 4 1 7 0 4 1 0 7 4 1
3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 0 3 0 2 0 3 2 6 3 2 6 3 2
(10) (11) (12) (13) (14) (15) (16) (17) (18) (19)
0 8 5 8 0 5 8 5 0 8 5 4 8 5 4 8 5 4 8 5 4 8 5 4 8 5 4 8 5 4
9 7 4 1 9 7 4 1 9 7 4 1 9 7 0 1 9 7 1 0 9 7 1 2 9 7 1 2 9 7 1 2 9 0 1 2 0 9 1 2
6 3 2 6 3 2 6 3 2 6 3 2 6 3 2 6 3 0 6 0 3 0 6 3 7 6 3 7 6 3
(20) (21) (22) (23) (24) (25) (26) (27) (28) (29)
0 5 4 5 0 4 5 4 0 5 4 1 5 4 1 5 4 1 5 4 1 5 4 1 5 4 1 5 4 1
8 9 1 2 8 9 1 2 8 9 1 2 8 9 0 2 8 9 2 0 8 9 2 3 8 9 2 3 8 9 2 3 8 0 2 3 0 8 2 3
7 6 3 7 6 3 7 6 3 7 6 3 7 6 3 7 6 0 7 0 6 0 7 6 9 7 6 9 7 6
(30) (31) (32) (33) (34) (35) (36) (37) (38) (39)
0 4 1 4 0 1 4 1 0 4 1 2 4 1 2 4 1 2 4 1 2 4 1 2 4 1 2 4 1 2
5 8 2 3 5 8 2 3 5 8 2 3 5 8 0 3 5 8 3 0 5 8 3 6 5 8 3 6 5 8 3 6 5 0 3 6 0 5 3 6
9 7 6 9 7 6 9 7 6 9 7 6 9 7 6 9 7 0 9 0 7 0 9 7 8 9 7 8 9 7
(40) (41) (42) (43) (44) (45)
0 1 2 1 0 2 1 2 0 1 2 3 1 2 3 1 2 3
4 5 3 6 4 5 3 6 4 5 3 6 4 5 0 6 4 5 6 0 4 5 6 7
8 9 7 8 9 7 8 9 7 8 9 7 8 9 7 8 9 0
45 手で解くことができました。
次は最長手数の局面を求めてみましょう。
>>> s = time.time(); solver_max(adjacent1); time.time() - s 手数: 1, 個数 = 2 手数: 2, 個数 = 3 手数: 3, 個数 = 7 手数: 4, 個数 = 14 手数: 5, 個数 = 21 手数: 6, 個数 = 30 手数: 7, 個数 = 51 手数: 8, 個数 = 86 手数: 9, 個数 = 134 手数: 10, 個数 = 199 手数: 11, 個数 = 304 手数: 12, 個数 = 465 手数: 13, 個数 = 698 手数: 14, 個数 = 1046 手数: 15, 個数 = 1581 手数: 16, 個数 = 2369 手数: 17, 個数 = 3509 手数: 18, 個数 = 5070 手数: 19, 個数 = 7285 手数: 20, 個数 = 10313 手数: 21, 個数 = 14443 手数: 22, 個数 = 19763 手数: 23, 個数 = 26625 手数: 24, 個数 = 35239 手数: 25, 個数 = 45747 手数: 26, 個数 = 57805 手数: 27, 個数 = 71726 手数: 28, 個数 = 87104 手数: 29, 個数 = 103063 手数: 30, 個数 = 117843 手数: 31, 個数 = 129952 手数: 32, 個数 = 137795 手数: 33, 個数 = 140144 手数: 34, 個数 = 136771 手数: 35, 個数 = 127838 手数: 36, 個数 = 115010 手数: 37, 個数 = 99301 手数: 38, 個数 = 82786 手数: 39, 個数 = 66422 手数: 40, 個数 = 51773 手数: 41, 個数 = 39135 手数: 42, 個数 = 27999 手数: 43, 個数 = 19164 手数: 44, 個数 = 12442 手数: 45, 個数 = 7571 手数: 46, 個数 = 4234 手数: 47, 個数 = 2130 手数: 48, 個数 = 943 手数: 49, 個数 = 334 手数: 50, 個数 = 96 手数: 51, 個数 = 13 手数: 52, 個数 = 1 最長手数 = 52, 個数 = 1 (7, 6, 3, 9, 8, 2, 1, 5, 4, 0) 状態の総数 = 1814400 4.4859209060668945
┌─┬─┬─┐ ┌─┬─┬─┐
│７│６│３│ │１│２│３│
├─┼─┼─┼─┐ ├─┼─┼─┼─┐
│９│８│２│１│ │４│５│６│７│
└─┼─┼─┼─┤ └─┼─┼─┼─┤
│５│４│ │ │８│９│ │
└─┴─┴─┘ └─┴─┴─┘
最長手数の局面 ＧＯＡＬ
図 : ９パズルの最長手数 (52 手)
最長手数は 52 手で、上図の局面しかありません。
#
# nine.py : ９パズル
#
# Copyright (C) 2022 Makoto Hiroi
#
import time
from collections import deque
# 盤面
# 0 1 2 3 4
# 5 6 7 8 9
# 隣接リスト
adjacent0 = [
[1, 5], # 0
[0, 2, 6], # 1
[1, 3, 7], # 2
[2, 4, 8], # 3
[3, 9], # 4
[0, 6], # 5
[1, 5, 7], # 6
[2, 6, 8], # 7
[3, 7, 9], # 8
[4, 8] # 9
]
#
# 変形版
#
# 盤面
# 0 1 2
# 3 4 5 6
# 7 8 9
# 隣接リスト
adjacent1 = [
[1, 3], # 0
[0, 2, 4], # 1
[1, 5], # 2
[0, 4], # 3
[1, 3, 5, 7], # 4
[2, 4, 6, 8], # 5
[5, 9], # 6
[4, 8], # 7
[5, 7, 9], # 8
[6, 8] # 9
]
# 駒の移動
def move_piece(b, n, s):
a = list(b)
a[s] = a[n]
a[n] = 0
return tuple(a)
# 手順の表示
def print_moves(b, table):
if b:
print_moves(table[b], table)
print(b)
# 幅優先探索
def bfs(start, goal, adjacent = adjacent0):
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(adjacent = adjacent0):
start = (1,2,3,4,5,6,7,8,9,0)
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(f'手数: {move}, 個数 = {len(xs)}')
print(f'最長手数 = {move}, 個数 = {len(xs)}')
for b in xs: print(b[0])
print('状態の総数 =', len(check))