今回は「８パズル」の列をひとつ増やした「１１パズル」を取り上げます。高橋謙一郎さんの「１１パズルの最適解が最長手数となる面の探索」によると、11 パズルの最長手数は 53 手で、局面は全部で 18 通りあるそうです。そのうちの一つを下図に示します。
┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐
│ │３│２│１│ │１│２│３│４│
├─┼─┼─┼─┤ ├─┼─┼─┼─┤
│８│７│６│５│ │５│６│７│８│
├─┼─┼─┼─┤ ├─┼─┼─┼─┤
│４│11│10│９│ │９│10│11│ │
└─┴─┴─┴─┘ └─┴─┴─┴─┘
完成形
図 : 11 パズル (最長手数局面)
(出典 : １１パズルの最適解が最長手数となる面の探索)
左図から右図の完成形までの最短手順を求めてください。
プログラムは基本的に「7 パズル」の「反復深化＋下限値枝刈り法」と同じです。ただし、そのままでは時間がかかるので、「手数の偶奇性」というパズルの性質を使って、探索の上限値を 2 手ずつ増やすことにします。
8 パズルや 15 パズルの場合、スタートの空き場所の位置とゴールの空き場所の位置から、解の手数が偶数になるのか奇数になるのか簡単に判定することができます。この場合、探索の上限値を 1 手ずつではなく 2 手ずつ増やすことができるので、実行時間を短縮することが可能です。
判定は簡単です。次の図を見てください。
┌─┬─┬─┐ ┌─┬─┬─┐ ┌─┬─┬─┐
│１│０│１│ │８│６│７│ │１│２│３│
├─┼─┼─┤ ├─┼─┼─┤ ├─┼─┼─┤
│０│１│０│ │２│５│４│ │４│５│６│
├─┼─┼─┤ ├─┼─┼─┤ ├─┼─┼─┤
│１│０│１│ │３│ │１│ │７│８│ │
└─┴─┴─┘ └─┴─┴─┘ └─┴─┴─┘
パリティ スタート ゴール
空場所のパリティ : 0 空場所のパリティ : 1
パリティが異なる場合 : 手数は奇数回
パリティが同じ場合 : 手数は偶数回
図 : 手数の偶奇性
盤面を市松模様に塗り分けます。上図のパリティでは 0 と 1 で表しています。スタートからゴールに到達するまで、空き場所はいろいろな位置に移動しますが、同じパリティの位置に移動する場合は偶数回かかり、異なるパリティの位置に移動する場合は奇数回かかります。
たとえば、スタートで駒 5 を 1 回動かすと、空き場所は上の位置に移動します。この場合、移動回数は奇数でパリティの値は 0 から 1 に変わります。スタートから駒 5 と 6 を動かすと、移動回数は偶数でパリティの値は 0 のままです。このように、同じパリティの位置に移動する場合は偶数回、異なるパリティの位置に移動する場合は奇数回となります。上図のスタートとゴールの場合、空き場所のパリティが異なるので、奇数回かかることがわかります。
プログラムは７パズルの「反復深化＋下限値枝刈り法」に「手数の偶奇性」の処理を追加しただけです。説明は割愛するので、詳細は「プログラムリスト」をお読みください。
実行結果は次のようになりました。
>>>> import time >>>> s = time.time(); solver_ids(list(start), list(goal)); print(time.time() - s) ---- 23 ----- ---- 25 ----- ---- 27 ----- ---- 29 ----- ---- 31 ----- ---- 33 ----- ---- 35 ----- ---- 37 ----- ---- 39 ----- ---- 41 ----- ---- 43 ----- ---- 45 ----- ---- 47 ----- ---- 49 ----- ---- 51 ----- ---- 53 ----- [3, 2, 6, 5, 1, 6, 2, 7, 5, 1, 9, 10, 11, 4, 8, 5, 1, 9, 10, 11, 4, 8, 5, 1, 9, 10, 11, 4, 8, 9, 10, 2, 7, 3, 1, 5, 9, 10, 2, 11, 4, 8, 11, 7, 6, 4, 7, 6, 3, 2, 6, 7, 8] 102.41609978675842 実行環境 : PyPy3 (ver 7.3.1), Ubunts 20.04 (WSL1), Intel Core i5-6200U 2.30GHz
当然ですが手数は 53 手、実行時間は約 103 秒でした。
11 パズルの場合、駒の配置は 12! / 2 = 239,500,800 通りあります。これに 0 から 239,500,799 までの番号をつけることを考えます。基本的には、「８パズル」の「順列に番号をつける方法」と同じですが、空き場所 (0) と駒 (1 - 9) がある場所 (添字) を基準に考えるところが異なります。つまり、数字の並びで考えるのではなく、12 個 (0 - 11) の場所から 10 個の数字 (0 - 9) を格納する場所を選ぶ順列として考えるのです。
n 個の中から k 個を選ぶ順列を \(P(n, k)\) とすると、次の公式で順列の個数を求めることができます。
P(12, 10) = 12! / 2! = 12 * 11 * ... * 3 = 239,500,800 になります。なお、数値から盤面を求めるとき、空き場所 (0) と駒 (1 - 9) を配置する場所はわかりますが、残りの二カ所に配置される駒 (10, 11) を決めることができません。スライドパズルの「偶奇性」を使うと、10 と 11 の場所を決定することができます。これはあとで説明します。
プログラムは次のようになります。
リスト : N!/2 に番号をつける
fact_table = [
19958400, # 11 * ... * 3
1814400, # 10 * ... * 3
181440, # 9 * ... * 3
20160, # 8 * ... * 3
2520, # 7 * ... * 3
360, # 6 * ... * 3
60, # 5 * 4 * 3
12, # 4 * 3
3, # 3
1
]
def to_num(b):
buff = [0] * 10
value = 0
for i, p in enumerate(b):
if p < 10: buff[p] = i
for i in range(10):
value += fact_table[i] * buff[i];
for j in range(i + 1, 10):
if buff[i] < buff[j]: buff[j] -= 1
return value;
関数 to_num() の最初の for ループで、0 から 9 までの位置を求めてリスト buff に格納します。次の for ループで値 value を計算します。やっていることは「順列に番号をつける方法」と同じです。これで盤面を 0 から 239,500,799 までの数値に変換することができます。
簡単な実行例を示します。
>>> to_num((0,1,2,3,4,5,6,7,8,9,10,11)) 0 >>> to_num((0,1,2,3,4,5,6,7,8,9,11,10)) 0 >>> to_num((11,10,9,8,7,6,5,4,3,2,1,0)) 239500799 >>> to_num((10,11,9,8,7,6,5,4,3,2,1,0)) 239500799 >>> to_num((1,2,3,4,5,6,7,8,9,10,11,0)) 219542400 >>> to_num((1,2,3,4,5,6,7,8,9,11,10,0)) 219542400 >>> to_num((0,3,2,1,8,7,6,5,4,11,10,9)) 3821534 >>> to_num((0,3,2,1,8,7,6,5,4,10,11,9)) 3821534
このように、駒 10 と 11 を入れ替えても同じ値になることがわかります。
スライドパズルの偶奇性は「転倒数」を使って判定します。下図を見てください。
1 2 3 4 A - B - C - D
|
5 6 7 8 E - F - G - H
|
9 10 11 _ I - J - K - L
完成形 経路 (A,B,C,D,H,G,F,E,I,J,K,L)
ここで、数字は位置 A から始まって経路 (A, B, C, D, H, G, F, E, I, J, K, L) に沿って並んでいると定義します。このとき、空き場所は無視してください。すると、完成形の並びは [1 2 3 4 8 7 6 5 9 10 11] となります。ここで、数字の順番が逆になっているところに注目してください。
数字が順番に並んでいる場合、各数字の右側には自分より小さな数字はありません。ところが、完成形では 8 の右側に 7, 6, 5 があり、7 の右側には 6, 5 があり、6 の右側に 5 があります。このように、数字の順番が逆になっている個数を数え、それを合計した値を「転倒数」と呼びます。そして、転倒数が奇数の場合を「奇順列」、偶数の場合を「偶順列」といいます。完成形の場合、転倒数は 3 + 2 + 1 = 6 ですから偶順列になります。
スライドパズルの場合、何回駒を動かしても奇順列は奇順列のまま、偶順列は偶順列のままであり、奇順列から偶順列へ、逆に偶順列から奇順列へ移行することはできません。詳しい説明は拙作のページ「偶奇性のお話」をお読みください。
偶奇性を求める関数 perm_type() は次のようになります。
リスト : 盤面の偶奇性を求める
# 偶順列 : 1
# 奇順列 : 2 を返す
def perm_type(b):
xs = (0,1,2,3,7,6,5,4,8,9,10,11)
cnt = 0
for i in range(len(b)):
x = b[xs[i]]
if x == 0: continue
elif x == 10: x10 = i
elif x == 11: x11 = i
for j in range(i, len(b)):
y = b[xs[j]]
if y != 0 and x > y: cnt += 1
cnt1 = cnt if x10 < x11 else cnt - 1
return cnt % 2 + 1, cnt1 % 2 + 1
perm_type() は 11 パズルの偶奇性と駒 10 が 2 つある盤面の偶奇性を返します。1 が偶順列、2 が奇順列です。リスト xs が経路を表します。あとは二重の for ループで転倒数 cnt を数えますが、このとき、10 の順番と 11 の順番を変数 x10, x11 にセットします。駒 10 が 2 つある盤面の転倒数は、10 が 11 よりも前にあれば cnt と同じ、そうでなければ cnt - 1 になります。
簡単な実行例を示します。
>>> perm_type((0,1,2,3,4,5,6,7,8,9,10,11)) (1, 1) >>> perm_type((0,1,2,3,4,5,6,7,8,9,11,10)) (2, 1) >>> perm_type((11,10,9,8,7,6,5,4,3,2,1,0)) (2, 1) >>> perm_type((10,11,9,8,7,6,5,4,3,2,1,0)) (1, 1) >>> perm_type((1,2,3,4,5,6,7,8,9,10,11,0)) (1, 1) >>> perm_type((1,2,3,4,5,6,7,8,9,11,10,0)) (2, 1) >>> perm_type((2,1,3,4,5,6,7,8,9,11,10,0)) (1, 2) >>> perm_type((2,1,3,4,5,6,7,8,9,10,11,0)) (2, 2)
数値から復元される盤面は駒 10 が 2 つある状態です。この盤面が奇順列の場合、完成形とは異なるので、転倒数を 1 つ増やして偶順列にします。つまり、2 つある 10 のうち、前のほうにある 10 を 11 にするわけです。偶順列の場合、転倒数を増やす必要はありません。後方にある 10 を 11 にします。これで数値から盤面を復元することができます。
プログラムは次のようになります。
リスト : 数値を盤面に変換する
def from_num(n, flag):
buff = [0] * 10
board = [10] * 12
for i, j in enumerate(fact_table):
buff[i] = n // j
n %= j
for i in range(8, -1, -1):
for j in range(i + 1, 10):
if buff[i] <= buff[j]: buff[j] += 1
for i, j in enumerate(buff):
board[j] = i
if flag:
for i in range(11, -1, -1):
if board[i] == 10:
board[i] = 11
break
else:
board[ board.index(10) ] = 11
return board, buff[0]
関数 from_num() は盤面と空き場所の位置を返します。まず最初のループで、数値を 10 個の数字へ分解します。この段階では、数字はまだ駒の位置を表していません。次のループで、to_num() と逆の操作を行うことで、駒の位置を求めます。逆方向から数字をチェックし、数字が大きいか等しい場合は、その数字に 1 を加えます。これで駒の位置を復元することができます。あとは、盤面に駒をセットすればいいわけです。
引数 n が表す盤面の偶奇性が完成形と等しい場合、引数 flag には True を、そうでなければ False を渡します。flag が True の場合は末尾から 10 を探して、それを 11 に書き換えます。True の場合は先頭から 10 を探して、それを 11 に書き換えます。最後に盤面 board と空き場所の位置 buff[0] を返します。
簡単な実行例を示します。
>>> from_num(0, True) ([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11], 0) >>> from_num(0, False) ([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 10], 0) >>> from_num(239500799, True) ([10, 11, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0], 11) >>> from_num(239500799, False) ([11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0], 11) >>> from_num(219542400, True) ([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 0], 11) >>> from_num(219542400, False) ([1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 10, 0], 11)
最後に、最長手数の局面を求める関数 solver_max() を作ります。
リスト : 最長手数の局面
def solver_max():
check = bytearray(239500800)
start = (1,2,3,4,5,6,7,8,9,10,11,0)
pt0, pt1 = perm_type(start)
num = to_num(start)
check[num] = pt1
xs = [num]
move = 0
while True:
ys = []
for num in xs:
b, s = from_num(num, pt0 == check[num])
for x in adjacent[s]:
b[s] = b[x]
b[x] = 0
v = to_num(b)
if check[v] == 0:
ys.append(v)
_, pt1 = perm_type(b)
check[v] = pt1
b[x] = b[s]
b[s] = 0
if not ys: break
xs = ys
move = move + 1
print(f'手数 = {move}, 個数 = {len(xs)}')
print('最長手数 =', move, '個数 =', len(xs))
for num in xs:
a, _ = from_num(num, pt0 == check[num])
print(a)
同一局面のチェックには Ptyhon の bytearray を使います。bytearray は要素が無符号 8 bit 整数 (0 - 255) の一次元配列です。要素は 0 で初期化されます。大きさ 239,500,800 の bytearray を変数 check にセットします。新しい盤面を生成したら、ここに番号 (添字) が表す盤面 (駒 10 が 2 個ある状態) の偶奇性 (1 or 2) をセットします。
start は完成形を表します。変数 pt0 に start の偶奇性を、pt1 に駒 10 が 2 個ある盤面の偶奇性をセットします。それから、to_num() で start を番号に変換して変数 num にセットし、move 手の盤面を格納するリスト xs に num を追加し、check[num] に pt1 をセットします。
次の while ループで幅優先探索を行います。xs から盤面を表す数値を順番に取り出し、from_num() で盤面に変換します。このとき、start の偶奇性 pt0 と check[num] が等しければ True を、そうでなければ False を from_num() に渡します。その次の for ループで、駒を動かして盤面 b を生成し、to_num() で数値 v に変換します。check[v] が 0 ならば新しい盤面です。ys に num を、check[v] に偶奇性をセットします。
あとは今まで作成した「最長手数の局面」を求めるプログラムとほとんど同じです。説明は省略するので、詳細はプログラムリストをお読みください。
実行結果を示します。
>>>> s = time.time(); solver_max(); print(time.time() - s) 手数 = 1, 個数 = 2 手数 = 2, 個数 = 4 手数 = 3, 個数 = 9 手数 = 4, 個数 = 20 手数 = 5, 個数 = 37 手数 = 6, 個数 = 63 手数 = 7, 個数 = 122 手数 = 8, 個数 = 232 手数 = 9, 個数 = 431 手数 = 10, 個数 = 781 手数 = 11, 個数 = 1392 手数 = 12, 個数 = 2494 手数 = 13, 個数 = 4442 手数 = 14, 個数 = 7854 手数 = 15, 個数 = 13899 手数 = 16, 個数 = 24215 手数 = 17, 個数 = 41802 手数 = 18, 個数 = 71167 手数 = 19, 個数 = 119888 手数 = 20, 個数 = 198363 手数 = 21, 個数 = 323206 手数 = 22, 個数 = 515778 手数 = 23, 個数 = 811000 手数 = 24, 個数 = 1248011 手数 = 25, 個数 = 1885279 手数 = 26, 個数 = 2782396 手数 = 27, 個数 = 4009722 手数 = 28, 個数 = 5621354 手数 = 29, 個数 = 7647872 手数 = 30, 個数 = 10065800 手数 = 31, 個数 = 12760413 手数 = 32, 個数 = 15570786 手数 = 33, 個数 = 18171606 手数 = 34, 個数 = 20299876 手数 = 35, 個数 = 21587248 手数 = 36, 個数 = 21841159 手数 = 37, 個数 = 20906905 手数 = 38, 個数 = 18899357 手数 = 39, 個数 = 16058335 手数 = 40, 個数 = 12772603 手数 = 41, 個数 = 9515217 手数 = 42, 個数 = 6583181 手数 = 43, 個数 = 4242753 手数 = 44, 個数 = 2503873 手数 = 45, 個数 = 1350268 手数 = 46, 個数 = 643245 手数 = 47, 個数 = 270303 手数 = 48, 個数 = 92311 手数 = 49, 個数 = 27116 手数 = 50, 個数 = 5390 手数 = 51, 個数 = 1115 手数 = 52, 個数 = 86 手数 = 53, 個数 = 18 最長手数 = 53 個数 = 18 [8, 7, 5, 9, 4, 3, 10, 2, 0, 11, 6, 1] [0, 8, 6, 1, 11, 3, 2, 5, 4, 7, 10, 9] [0, 8, 6, 9, 11, 7, 2, 5, 4, 3, 10, 1] [0, 8, 2, 9, 11, 3, 6, 5, 4, 7, 10, 1] [0, 8, 6, 9, 10, 7, 11, 1, 4, 3, 2, 5] [4, 3, 2, 5, 8, 7, 6, 1, 0, 11, 10, 9] [0, 8, 2, 1, 10, 3, 11, 5, 4, 7, 6, 9] [0, 11, 2, 1, 3, 7, 6, 5, 4, 8, 10, 9] [4, 3, 2, 1, 8, 11, 6, 5, 0, 7, 10, 9] [0, 8, 2, 9, 10, 7, 11, 5, 4, 3, 6, 1] [11, 8, 2, 1, 3, 7, 10, 5, 0, 4, 6, 9] [4, 3, 6, 1, 8, 7, 2, 5, 0, 11, 10, 9] [4, 3, 2, 1, 8, 7, 6, 9, 0, 11, 10, 5] [4, 3, 2, 1, 11, 7, 6, 5, 0, 8, 10, 9] [8, 3, 2, 9, 4, 7, 6, 10, 0, 11, 5, 1] [8, 3, 6, 9, 4, 7, 2, 5, 0, 11, 10, 1] [0, 3, 2, 1, 8, 7, 6, 5, 4, 11, 10, 9] [8, 3, 2, 1, 4, 7, 6, 5, 0, 11, 10, 9] 974.5243532657623 実行環境 : PyPy3 (ver 7.3.1), Ubunts 20.04 (WSL1), Intel Core i5-6200U 2.30GHz
最長手数は 53 手、盤面は 18 通りになりました。これは高橋謙一郎さんの結果と同じです。時間は約 16 分 15 秒、PyPy3 でも時間がかかりますね。ネイティブコードにコンパイルするプログラミング言語を使うと、もっと速くなるでしょう。興味のある方は挑戦してみてください。
#
# eleven.py : 11 パズル
#
# Copyright (C) 2022 Makoto Hiroi
#
# 盤面
# 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
]
# 手数の偶奇性
parity = [
1, 0, 1, 0,
0, 1, 0, 1,
1, 0, 1, 0
]
# 問題
start = (0,3,2,1,8,7,6,5,4,11,10,9)
goal = (1,2,3,4,5,6,7,8,9,10,11,0)
# 距離
distance =[
[0, 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, 0, 1, 2, 2, 1, 2, 3, 3, 2, 3, 4], # 2
[2, 1, 0, 1, 3, 2, 1, 2, 4, 3, 2, 3], # 3
[3, 2, 1, 0, 4, 3, 2, 1, 5, 4, 3, 2], # 4
[1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4], # 5
[2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3], # 6
[3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2], # 7
[4, 3, 2, 1, 3, 2, 1, 0, 4, 3, 2, 1], # 8
[2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3], # 9
[3, 2, 3, 4, 2, 1, 2, 3, 1, 0, 1, 2], # 10
[4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1] # 11
]
# 下限値を求める
def get_lower_value(b):
lower = 0
for i, p in enumerate(b):
lower += distance[p][i]
return lower
# 反復深化＋下限値枝刈り法
def dfs(n, board, goal, space, limit, lower, moves):
if n == limit:
if board == goal:
print(moves[1:])
return True
else:
for x in adjacent[space]:
p = board[x]
if p == moves[-1]: continue
newlower = lower - distance[p][x] + distance[p][space]
if n + newlower > limit: continue
board[space] = p
board[x] = 0
moves.append(p)
if dfs(n + 1, board, goal, x, limit, newlower, moves):
return True
moves.pop()
board[x] = p
board[space] = 0
return False
def solver_ids(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 dfs(0, start, goal, start.index(0), limit, lower, [-1]):
break
limit += 2
#
# 12! / 2 = 239,500,800 に番号を付ける
#
fact_table = [
19958400, # 11 * ... * 3
1814400, # 10 * ... * 3
181440, # 9 * ... * 3
20160, # 8 * ... * 3
2520, # 7 * ... * 3
360, # 6 * ... * 3
60, # 5 * 4 * 3
12, # 4 * 3
3, # 3
1
]
def to_num(b):
buff = [0] * 10
value = 0
for i, p in enumerate(b):
if p < 10: buff[p] = i
for i in range(10):
value += fact_table[i] * buff[i];
for j in range(i + 1, 10):
if buff[i] < buff[j]: buff[j] -= 1
return value;
# 偶順列 : 1, 奇順列 : 2 を返す
def perm_type(b):
xs = (0,1,2,3,7,6,5,4,8,9,10,11)
cnt = 0
for i in range(len(b)):
x = b[xs[i]]
if x == 0: continue
elif x == 10: x10 = i
elif x == 11: x11 = i
for j in range(i, len(b)):
y = b[xs[j]]
if y != 0 and x > y: cnt += 1
cnt1 = cnt if x10 < x11 else cnt - 1
return cnt % 2 + 1, cnt1 % 2 + 1
def from_num(n, flag):
buff = [0] * 10
board = [10] * 12
for i, j in enumerate(fact_table):
buff[i] = n // j
n %= j
for i in range(8, -1, -1):
for j in range(i + 1, 10):
if buff[i] <= buff[j]: buff[j] += 1
for i, j in enumerate(buff):
board[j] = i
if flag:
for i in range(11, -1, -1):
if board[i] == 10:
board[i] = 11
break
else:
board[ board.index(10) ] = 11
return board, buff[0]
# 最長手数の局面
def solver_max():
check = bytearray(239500800)
start = (1,2,3,4,5,6,7,8,9,10,11,0)
pt0, pt1 = perm_type(start)
num = to_num(start)
check[num] = pt1
xs = [num]
move = 0
while True:
ys = []
for num in xs:
b, s = from_num(num, pt0 == check[num])
for x in adjacent[s]:
b[s] = b[x]
b[x] = 0
v = to_num(b)
if check[v] == 0:
ys.append(v)
_, pt1 = perm_type(b)
check[v] = pt1
b[x] = b[s]
b[s] = 0
if not ys: break
xs = ys
move = move + 1
print(f'手数 = {move}, 個数 = {len(xs)}')
print('最長手数 =', move, '個数 =', len(xs))
for num in xs:
a, _ = from_num(num, pt0 == check[num])
print(a)