問題の説明
今回は「15 パズルの変形版」を解いてみましょう。
次に示す局面から始めて、最長手数となる配置を求めてください。何手になるでしょうか。
(1) の場合、赤、青、黄色、水色、桃色、空白の場所がひとつずつで、残りが 10 個が黒ですから、駒の配置は 16 * 15 * 14 * 13 * 12 * 11 = 5,765,760 通りあります。(2) の場合は、空白の場所が 16 通りあり、緑の駒の配置は \({}_{15} \mathrm{C}_5\) = 3003 通り、赤の駒の配置は \({}_{10} \mathrm{C}_5\) = 252 通りあるので、駒の配置は 16 * 3003 * 252 = 12,108,096 通りあります。
最近のパソコンは高性能でメモリの搭載量も多いので (M.Hiroi の PC は 8 G byte)、問題 (1) は単純な幅優先探索でも解けそうです。問題 (2) は、もしかするとメモリが足りなくなるかもしれません。そこで、問題 (2) は １１パズル と同じく、盤面に 0 から 12,108,095 までの番号をつけて、無符号バイト配列 (Python の bytearray) を使って同一局面をチェックすることにします。
●問題 (1) の解法
それでは、問題 (1) から解いていきましょう。いつものように、空いている場所を 0 で表し、ほかの駒を 1 から 6 までの数字で表すことにします。そうすると、初期状態は下記リストのようになります。
リスト : 初期状態
start = (
1, 2, 3, 4,
6, 6, 6, 6,
6, 6, 6, 6,
5, 6, 6, 0
)
幅優先探索で最長手数を求める関数 solver_max() は次のようになります。
リスト : 最長手数の局面を求める
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(f'手数 : {move}, 個数 : {len(xs)}')
print('最長手数 =', move, '個数 =', len(xs))
for b in xs: print_board(b[0])
print('状態の総数 =', len(check))
solver_max() は今まで作成した最長手数の局面を求めるプログラムとほとんど同じなので、説明は不要でしょう。詳細は プログラムリスト１ をお読みください。
●実行結果 (1)
それでは実行してみましょう。
>>>> s = time.time(); solver_max(); print(time.time() - s) 手数 : 1, 個数 : 2 手数 : 2, 個数 : 3 手数 : 3, 個数 : 4 手数 : 4, 個数 : 5 手数 : 5, 個数 : 9 手数 : 6, 個数 : 16 手数 : 7, 個数 : 30 手数 : 8, 個数 : 53 手数 : 9, 個数 : 88 手数 : 10, 個数 : 148 手数 : 11, 個数 : 257 手数 : 12, 個数 : 428 手数 : 13, 個数 : 721 手数 : 14, 個数 : 1177 手数 : 15, 個数 : 1905 手数 : 16, 個数 : 3006 手数 : 17, 個数 : 4713 手数 : 18, 個数 : 7101 手数 : 19, 個数 : 10676 手数 : 20, 個数 : 15648 手数 : 21, 個数 : 22718 手数 : 22, 個数 : 31964 手数 : 23, 個数 : 44562 手数 : 24, 個数 : 60335 手数 : 25, 個数 : 80518 手数 : 26, 個数 : 104756 手数 : 27, 個数 : 133863 手数 : 28, 個数 : 167088 手数 : 29, 個数 : 204303 手数 : 30, 個数 : 243989 手数 : 31, 個数 : 284329 手数 : 32, 個数 : 323927 手数 : 33, 個数 : 358730 手数 : 34, 個数 : 387168 手数 : 35, 個数 : 405207 手数 : 36, 個数 : 412001 手数 : 37, 個数 : 405674 手数 : 38, 個数 : 386345 手数 : 39, 個数 : 354788 手数 : 40, 個数 : 312524 手数 : 41, 個数 : 264743 手数 : 42, 個数 : 214554 手数 : 43, 個数 : 166690 手数 : 44, 個数 : 123144 手数 : 45, 個数 : 86432 手数 : 46, 個数 : 57801 手数 : 47, 個数 : 36391 手数 : 48, 個数 : 21682 手数 : 49, 個数 : 11897 手数 : 50, 個数 : 6353 手数 : 51, 個数 : 2999 手数 : 52, 個数 : 1410 手数 : 53, 個数 : 563 手数 : 54, 個数 : 230 手数 : 55, 個数 : 65 手数 : 56, 個数 : 22 手数 : 57, 個数 : 3 手数 : 58, 個数 : 1 最長手数 = 58 個数 = 1 [ 0 6 6 5 6 6 6 6 6 6 6 6 4 2 3 1 ] 状態の総数 = 5765760 26.044363260269165 実行環境 : PyPy3 (ver 7.3.1), Ubunts 20.04 (WSL1), Intel Core i5-6200U 2.30GHz
実行時間は PyPy3 で約 26 秒でした。結果を図で表すと次のようになります。
ちなみに、生成した局面は全部で 5,765,760 個あります。しがたって、このパズルは駒をランダムに配置しても、必ず START に到達できることがわかります。
●組み合わせに番号をつける方法
問題 (2) を解く前に、N 通りある組み合わせに 0 から N - 1 までの番号を付ける方法を簡単に説明しましょう。たとえば、6 個の中から 3 個を選ぶ組み合わせは 20 通りありますが、この組み合わせに 0 から 19 までの番号を付けることができます。1 1 1 0 0 0 を例題に考えてみましょう。次の図を見てください。
図 : 6Ｃ3 の組み合わせ
最初に 5 をチェックします。5 を選ばない場合は \({}_{5} \mathrm{C}_3\) = 10 通りありますね。この組み合わせに 0 から 9 までの番号を割り当てることにすると、5 を選ぶ組み合わせの番号は 10 から 19 までとなります。
次に、4 をチェックします。4 を選ばない場合は、\({}_{4} \mathrm{C}_2\) = 6 通りあります。したがって、5 を選んで 4 を選ばない組み合わせに 10 から 15 までの番号を割り当てることにすると、5 と 4 を選ぶ組み合わせには 16 から 19 までの番号となります。
最後に、3 をチェックします。同様に 3 を選ばない場合は 3 通りあるので、これに 16 から 18 までの番号を割り当て、5, 4, 3 を選ぶ組み合わせには 19 を割り当てます。これで組み合わせ 1 1 1 0 0 0 の番号を求めることができました。
では、0 0 0 1 1 1 はどうなるのでしょうか。左から順番にチェックしていくと、最初の 1 が見つかった時点で、その数字を選ばない組み合わせは存在しません。つまり、残りの数字をすべて選ぶしかないわけです。したがって、これが 0 番目となります。
このように、数字を選ぶときに、数字を選ばない場合の組み合わせの数を足し算していけば、その組み合わせの番号を求めることができるのです。詳しい説明は拙作のページ Algorithms with Python: 再帰定義 の「組み合わせ」をお読みくださいませ。
●パスカルの三角形
ところで、今回のプログラムでは「組み合わせの数」が必要になります。このような場合、公式を使っていちいち計算するよりも、あらかじめ値をテーブルに格納しておいて参照した方がいいでしょう。そこで、「パスカルの三角形」を利用してテーブルを作成することにします。次の図を見てください。
図 : パスカルの三角形
パスカルの三角形は、左側の図のように両側がすべて 1 で、内側の数はその左上と右上の和になっています。これは \((a + b)^n\) を展開したときの各項の係数を表しています。そして、その値は右側の図のように組み合わせの数 \({}_{n} \mathrm{C}_r\) に対応しています。
プログラムはとても簡単です。
リスト : パスカルの三角形
def make_comb_table(n):
table = [[1], [1, 1]]
for i in range(1, n):
buff = [1]
for j in range(i):
buff.append(table[i][j] + table[i][j + 1])
buff.append(1)
table.append(buff)
return table
パスカルの三角形をそのままプログラムしただけなので、とくに難しいところはないと思います。それでは実際に試してみましょう。
>>>> for x in make_comb_table(15): print(x) [1] [1, 1] [1, 2, 1] [1, 3, 3, 1] [1, 4, 6, 4, 1] [1, 5, 10, 10, 5, 1] [1, 6, 15, 20, 15, 6, 1] [1, 7, 21, 35, 35, 21, 7, 1] [1, 8, 28, 56, 70, 56, 28, 8, 1] [1, 9, 36, 84, 126, 126, 84, 36, 9, 1] [1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1] [1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1] [1, 12, 66, 220, 495, 792, 924, 792, 495, 220, 66, 12, 1] [1, 13, 78, 286, 715, 1287, 1716, 1716, 1287, 715, 286, 78, 13, 1] [1, 14, 91, 364, 1001, 2002, 3003, 3432, 3003, 2002, 1001, 364, 91, 14, 1] [1, 15, 105, 455, 1365, 3003, 5005, 6435, 6435, 5005, 3003, 1365, 455, 105, 15, 1]
正常に動作していますね。
●問題 (2) の解法
それでは問題 (2) を解きましょう。空き場所を 0 とし、駒を数値 1, 2, 3 で表すと、初期状態は下記リストのようになります。
リスト : 大域変数の定義
start = (
1, 1, 2, 2,
1, 1, 2, 2,
1, 3, 3, 2,
3, 3, 3, 0
)
# 組み合わせの数
comb_table = make_comb_table(15)
組み合わせの数は大域変数 comb_table に格納します。
盤面を数値に変換する関数 to_num() は「組み合わせに番号をつける方法」の応用です。駒 1 の場合、空き場所は無視して 2 と 3 を同じ駒と考えれば、配置は \({}_{15} \mathrm{C}_5\) = 3003 通りになります。駒 2 の場合、駒 1 と空き場所を無視すると、配置は \({}_{10} \mathrm{C}_5\) = 252 通りとなります。これをプログラムすると、次のようになります。
リスト : 盤面を数値に変換
def to_num(b):
space = value1 = value2 = 0
n1, n2 = 15, 10
r1 = r2 = 5
for i, p in enumerate(b):
if p == 0:
space = i
elif p == 1:
if n1 > r1 and r1 > 0:
value1 += comb_table[n1 - 1][r1]
n1 -= 1
r1 -= 1
elif p == 2:
if n2 > r2 and r2 > 0:
value2 += comb_table[n2 - 1][r2]
n2 -= 1
r2 -= 1
n1 -= 1
else:
n1 -= 1
n2 -= 1
return space * 3003 * 252 + value1 * 252 + value2
n1, r1, value1 が駒 1 用の変数で、n2, r2, value2 が駒 2 用の変数です。配列 comb_table は「パスカルの三角形」を表しています。最初に、空き場所の位置を space にセットします。どちらの駒も空き場所は無視するので、n1 と n2 の値はそのままにします。
駒 1 の場合、駒 2 と 3 を同じ駒として扱うので、n1 の値は駒 2 だけではなく駒 3 の場合も -1 します。駒 2 の場合は駒 1 を無視するので、n2 の値は駒 1 ではそのままとし、駒 3 のときに -1 します。これで、駒 1 と駒 2 の配置を数値に変換することができます。
それでは実際に試してみましょう。
>>>> to_num((0,3,3,3,3,3,2,2,2,2,2,1,1,1,1,1)) 0 >>>> to_num((1,1,1,1,1,2,2,2,2,2,3,3,3,3,3,0)) 12108095 >>>> to_num((1,1,2,2,1,1,2,2,1,3,3,2,3,3,3,0)) 12077097
正常に動作していますね。
●最長手数の局面
最長手数の局面を求める関数 solver_max() は次のようになります。
リスト : 最長手数の局面を求める
def solver_max():
b = bytearray(start)
xs = [b]
check = bytearray(12108096)
check[to_num(b)] = b.index(0) + 1
move = 0
while True:
ys = []
for b in xs:
s = check[to_num(b)] - 1
for n in adjacent[s]:
a = b[:]
a[s] = a[n]
a[n] = 0
v = to_num(a)
if check[v]: continue
ys.append(a)
check[v] = n + 1
if not ys: break
xs = ys
move += 1
print(f'手数 = {move}, 個数 = {len(xs)}')
print(f'最長手数 = {move}, 個数 = {len(xs)}')
for b in xs: print(tuple(b))
print('状態の総数 =', 12108096 - check.count(0))
盤面はタプルではなく bytearray で表します。start を bytearray に変換して変数 b にセットします。xs は move 手の盤面を格納するリストで、[b] に初期化します。check には大きさ 12,108,096 の bytearray をセットします。bytearray の要素は 0 に初期化されます。新しい盤面が生成されたとき、check には 空き場所の位置 + 1 をセットします。
次の while ループで、手数を 1 手ずつ増やしながら幅優先探索を行います。xs から盤面 b を取り出し、check[to_num(b)] から空き場所の位置 s を求めます。2 番目の for ループで駒を動かします。このとき、盤面 b をコピーして変数 a にセットします。bytearray は mutable なデータ構造なので、リストに変換する必要はありません。to_num(a) で a を数値 v に変換し、check[v] が 0 (偽) ならば新しい盤面です。リスト ys に a を追加し、check[v] に n + 1 をセットします。
あとは今まで作成した最長手数を求めるプログラムとほとんど同じです。説明は省略しますので、詳細は プログラムリスト２ をお読みくださいませ。
●実行結果 (2)
それでは実行してみましょう。
>>>> s = time.time(); solver_max1(); print(time.time() - s) 手数 = 1, 個数 = 2 手数 = 2, 個数 = 4 手数 = 3, 個数 = 9 手数 = 4, 個数 = 17 手数 = 5, 個数 = 31 手数 = 6, 個数 = 53 手数 = 7, 個数 = 91 手数 = 8, 個数 = 166 手数 = 9, 個数 = 310 手数 = 10, 個数 = 540 手数 = 11, 個数 = 915 手数 = 12, 個数 = 1542 手数 = 13, 個数 = 2522 手数 = 14, 個数 = 4006 手数 = 15, 個数 = 6333 手数 = 16, 個数 = 9795 手数 = 17, 個数 = 14808 手数 = 18, 個数 = 21860 手数 = 19, 個数 = 31708 手数 = 20, 個数 = 45038 手数 = 21, 個数 = 62808 手数 = 22, 個数 = 86118 手数 = 23, 個数 = 115907 手数 = 24, 個数 = 152799 手数 = 25, 個数 = 197455 手数 = 26, 個数 = 250687 手数 = 27, 個数 = 312167 手数 = 28, 個数 = 380582 手数 = 29, 個数 = 453785 手数 = 30, 個数 = 530437 手数 = 31, 個数 = 605770 手数 = 32, 個数 = 675832 手数 = 33, 個数 = 736970 手数 = 34, 個数 = 784429 手数 = 35, 個数 = 812871 手数 = 36, 個数 = 819168 手数 = 37, 個数 = 802369 手数 = 38, 個数 = 762545 手数 = 39, 個数 = 702108 手数 = 40, 個数 = 624494 手数 = 41, 個数 = 535325 手数 = 42, 個数 = 441749 手数 = 43, 個数 = 349908 手数 = 44, 個数 = 264275 手数 = 45, 個数 = 190116 手数 = 46, 個数 = 129405 手数 = 47, 個数 = 82963 手数 = 48, 個数 = 49902 手数 = 49, 個数 = 28137 手数 = 50, 個数 = 14942 手数 = 51, 個数 = 7306 手数 = 52, 個数 = 3226 手数 = 53, 個数 = 1233 手数 = 54, 個数 = 409 手数 = 55, 個数 = 119 手数 = 56, 個数 = 27 手数 = 57, 個数 = 2 最長手数 = 57, 個数 = 2 (3, 0, 3, 3, 2, 3, 3, 1, 2, 2, 1, 1, 2, 2, 1, 1) (3, 3, 3, 3, 2, 2, 3, 1, 2, 2, 1, 1, 0, 2, 1, 1) 状態の総数 = 12108096 23.243242979049683 実行環境 : PyPy3 (ver 7.3.1), Ubunts 20.04 (WSL1), Intel Core i5-6200U 2.30GHz
実行時間は PyPy3 で約 24 秒でした。bytearray を使うことで、省メモリで解くことができました。結果を図で表すと次のようになります。
ちなみに、生成した局面は全部で 12,108,096 個あります。しがたって、このパズルは駒をランダムに配置しても、必ず START に到達できることがわかります。
なお、メモリがもっと多ければ bytearray を使わずに解くことも可能です。実は M.Hiroi の環境でも今までと同様のプログラムで解くことができたのですが、途中からスワッピングが発生し、実行時間は 1 分以上と遅くなってしまいました。興味のある方はいろいろ試してみてください。
●プログラムリスト１
#
# sllide15a.py : 15 パズル変形版 (駒が六種類)
#
# Copyright (C) 2022 Makoto Hiroi
#
from collections import deque
import time
# 状態の総数
# 5,765,760
# 盤面
# 0 1 2 3
# 4 5 6 7
# 8 9 10 11
# 12 13 14 15
# 隣接リスト
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 = (
1, 2, 3, 4,
6, 6, 6, 6,
6, 6, 6, 6,
5, 6, 6, 0
)
# 駒の移動
def move_piece(b, n, s):
a = list(b)
a[s] = a[n]
a[n] = 0
return tuple(a)
# 盤面の表示
def print_board(b):
print('[', end= ' ')
for i, p in enumerate(b):
print(p, end=' ')
print(']')
# 最長手数の局面を求める
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(f'手数 : {move}, 個数 : {len(xs)}')
print('最長手数 =', move, '個数 =', len(xs))
for b in xs: print_board(b[0])
print('状態の総数 =', len(check))
●プログラムリスト２
#
# sllide15b.py : 15 パズル変形版 (駒が三種類)
#
# Copyright (C) 2022 Makoto Hiroi
#
import time
# 状態の総数
# 12,108,096
# 盤面
# 0 1 2 3
# 4 5 6 7
# 8 9 10 11
# 12 13 14 15
# 隣接リスト
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 = (
1, 1, 2, 2,
1, 1, 2, 2,
1, 3, 3, 2,
3, 3, 3, 0
)
#
# 組み合わせに番号を付ける
#
# 組み合わせの数を生成
def make_comb_table(n):
table = [[1], [1, 1]]
for i in range(1, n):
buff = [1]
for j in range(i):
buff.append(table[i][j] + table[i][j + 1])
buff.append(1)
table.append(buff)
return table
# 組み合わせの数
comb_table = make_comb_table(15)
# 盤面を数値に変換
def to_num(b):
space = value1 = value2 = 0
n1, n2 = 15, 10
r1 = r2 = 5
for i, p in enumerate(b):
if p == 0:
space = i
elif p == 1:
if n1 > r1 and r1 > 0:
value1 += comb_table[n1 - 1][r1]
n1 -= 1
r1 -= 1
elif p == 2:
if n2 > r2 and r2 > 0:
value2 += comb_table[n2 - 1][r2]
n2 -= 1
r2 -= 1
n1 -= 1
else:
n1 -= 1
n2 -= 1
return space * 3003 * 252 + value1 * 252 + value2
# 最長手数の局面を求める
def solver_max():
b = bytearray(start)
xs = [b]
check = bytearray(12108096)
check[to_num(b)] = b.index(0) + 1
move = 0
while True:
ys = []
for b in xs:
s = check[to_num(b)] - 1
for n in adjacent[s]:
a = b[:]
a[s] = a[n]
a[n] = 0
v = to_num(a)
if check[v]: continue
ys.append(a)
check[v] = n + 1
if not ys: break
xs = ys
move += 1
print(f'手数 = {move}, 個数 = {len(xs)}')
print(f'最長手数 = {move}, 個数 = {len(xs)}')
for b in xs: print(tuple(b))
print('状態の総数 =', 12108096 - check.count(0))
改訂 2022 年 11 月 12 日