Puzzle DE Programming

パズルの説明

今回は ７パズル の駒をひとつ増やした「８パズル」を取り上げます。

            図 : ８パズル

15 パズルは 4 行 4 列の盤ですが、8 パズルは 3 行 3 列と盤を小さくしたパズルです。8 パズルの場合、駒の配置は空き場所がどこでもいいことにすると、9! = 362880 通りあります。ところが 15 パズルや 8 パズルの場合、参考文献 5 によると次のことが証明されているそうです。

『適当な 2 つの駒をつまみ上げて交換する動作を偶数回行った局面にした移行できない』

上図 (2) は 7 と 8 を入れ替えただけの配置です。この場合、交換の回数が奇数回のため完成形に到達することができない、つまり解くことができないのです。このような性質を「偶奇性 (パリティ)」といいます。興味のある方は拙作のページ 偶奇性のお話 をお読みください。したがって、完成形に到達する局面の総数は 9! / 2 = 181440 個となります。

今回は Python3 (ver 3.8.10) を使ってプログラムを作ることにします。

●順列に番号をつける方法

今までにも説明しましたが、幅優先探索でパズルを解く場合、同一局面のチェックが重要になります。単純な線形探索で局面を検索すると、答えが出るまでに時間がかかってしまいます。このような場合の常套手段が、線形探索にかえて高速な探索アルゴリズムを使うことです。ハッシュ法や二分探索木など優秀なアルゴリズムを使うことで、実行時間を大幅に短縮することができます。

Python には辞書が用意されているので、ハッシュ法や二分探索木を実装する必要はないのですが、今回は趣向をこらして「順列に番号をつける方法」を採用します。8 パズルの場合、9! = 362880 のパターンがありますね。このパターンに 0 から 362879 までの番号をつけることができれば、大きさが 362,880 の一次元配列 (Python のリスト) を使って同一局面のチェックを高速に行うことができます。

ただし、盤面を数値に変換する処理を Python でプログラムすると、実行に時間がかかりそうです、実際には Python の辞書を使ったほうが速くなると思います。

それでは、番号の振り方を考えてみましょう。最初が 0 で始まるパターンは 8! = 40320 通りありますね。このパターンには 0 - 40319 までの番号を割り当てます。そして、1 で始まるパターンには 40320 - 80639 までの番号を割り当てます。残りのパターンも同じです。

次に 2 番目の数字を考えましょう。01 で始まるパターンは 7! = 5040 通りあります。したがって、このパターンには 0 - 5039 までの番号を割り当てます。10 で始まるパターンには 40320 - 45359 までの番号を、12 で始まるパターンには 45360 - 50399 までの番号を割り当てます。あとはこれを 9 番目までの数字まで続ければ、すべてパターンに番号を割り当てることができます。

では実際に 867254301 というパターンで試してみましょう。次の図を見てください。

 ８ 8 * 8!
 ６ [0 1 2 3 4 5 6 7] : 8*8! + 6*7!
 ７ [0 1 2 3 4 5 7] : 8*8! + 6*7! + 6*6!
 ２ [0 1 2 3 4 5] : 8*8! + 6*7! + 6*6! + 2*5!
 ５ [0 1 3 4 5] : 8*8! + 6*7! + 6*6! + 2*5! + 4*4!
 ４ [0 1 3 4] : 8*8! + 6*7! + 6*6! + 2*5! + 4*4! + 3*3!
 ３ [0 1 3] : 8*8! + 6*7! + 6*6! + 2*5! + 4*4! + 3*3! + 2*2!
 ０ [0 1] : 8*8! + 6*7! + 6*6! + 2*5! + 4*4! + 3*3! + 2*2! + 0*1!    
 １ [1] :
 番号 : 357478

注意すべき点は、数字をそのまま掛け算してはいけないところです。たとえば、7 に注目してください。このとき、残されている数字は 0, 1, 2, 3, 4, 5, 7 がありますね。番号は順番に振っていくので、867 は 86 で始まるパターンの 6 * 6! 番目から始まるのです。つまり、残っている数字の中で何番目に位置しているのか、を求めなければならないのです。

けっこう面倒だと思ったのですが、参考文献 2 に目からウロコが落ちるようなプログラムがありました。次の図を見てください。

8|6 7 2 5 4 3 0 1
  6 7 2 5 4 3 0 1 : 8 より大きな数字を -1 する    

8 6|7 2 5 4 3 0 1
    6 2 5 4 3 0 1 : 6 より大きな数字を -1 する

8 6 6|2 5 4 3 0 1
      2 5 4 3 0 1 : 6 より大きな数字を -1 する

8 6 6 2|5 4 3 0 1
        4 3 2 0 1 : 2 より大きな数字を -1 する

8 6 6 2 4|3 2 0 1
          3 2 0 1 : 4 より大きな数字を -1 する

・・・省略・・・

8 6 6 2 4 3 2 0 0

2 番目の 6 に注目してください。次の数字 7 は 6 より大きいですね。6 が使われたのですから、7 は 7 番目ではなく 6 番目になります。つまり、数字ではなく位置を表していると考えるのです。自分よりも前にある数字を使ったならば、位置を -1 して前に詰めればいいわけです。あとはこれを繰り返すだけです。こんな簡単な方法で求めることができるのですね。

プログラムは次のようになります。

リスト : 順列に番号をつける

# 階乗
fact_table = (40320, 5040, 720, 120, 24, 6, 2, 1, 0)

def to_num(b):
    work = list(b)
    value = 0
    for i in range(SIZE - 1):
        value += fact_table[i] * work[i]
        for j in range(i + 1, SIZE):
            if work[i] < work[j]: work[j] -= 1
    return value

局面を表す引数 b をリストに変換して変数 work にセットし、それを数値に変換します。説明をそのままプログラムしただけなので、難しいところはないと思います。ただし、このプログラムだけだと、理解するのはちょっと難しいかもしれません。M.Hiroi は、最初に 参考文献 2 のプログラムを見たときには、さっぱり理解できませんでした。よく分からない方は、もう一度説明を読み直して考えてみてください。

簡単な実行例を示します。

>>> to_num((0,1,2,3,4,5,6,7,8))
0
>>> to_num((8,7,6,5,4,3,2,1,0))
362879
>>> to_num((1,2,3,4,5,6,7,8,0))
46233
>>> to_num((5,4,6,3,7,2,8,1,0))
225089

●番号を順列に変換

番号を順列に変換することも簡単です。たとえば、0 から 8 までの 9 個の整数の順列で、番号 357478 を順列に変換してみましょう。次の図を見てください。

配列 buffer に 0 から 8 までの数字を昇順にセットします。そして、配列の先頭から数字を決定していきます。変数 i が決定する配列の位置を表します。357478 / 8! は 8 になるので、buffer[0] の数字は buffer[0 + 8] の要素 8 になります。要素 8 を取り出して bufer[0] に挿入します。要素を交換するのではなく、他の要素はひとつ右へ移動することに注意してください。

次は buffer[1] の数字を決定します。値を 357478 % 8! = 34918 に更新し、i をインクリメントします。34918 / 7! は 6 になるので、buffer[1 + 6] の要素 6 を buffer[1] に挿入します。つまり、変数 i から末尾までの要素の中から数字を選んでいくわけです。あとはこれを繰り返すことで順列に変換することができます。

プログラムは次のようになります。

リスト : 番号を順列に変換

def from_num(n):
    buff = list(range(SIZE))
    for i in range(SIZE - 1):
        p = n // fact_table[i]
        x = buff[i + p]
        for j in range(i + p, i, -1):
            buff[j] = buff[j - 1]
        buff[i] = x
        n %= fact_table[i]
    return tuple(buff)

説明したことをそのままプログラムしただけなので、特に難しいところはないと思います。

簡単な実行例を示します。

>>> from_num(0)
(0, 1, 2, 3, 4, 5, 6, 7, 8)
>>> from_num(362879)
(8, 7, 6, 5, 4, 3, 2, 1, 0)
>>> from_num(46233)
(1, 2, 3, 4, 5, 6, 7, 8, 0)
>>> from_num(225089)
(5, 4, 6, 3, 7, 2, 8, 1, 0)

●幅優先探索による解法

それではプログラムを作りましょう。最初に大域変数を定義します。

リスト : グローバル変数の定義

#  盤面
#  0 1 2
#  3 4 5
#  6 7 8

# 定数
SIZE = 9
HSIZE = 362880

# 隣接リスト
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
]

SIZE は盤面の大きさ、HSIZE は同一局面をチェックするための配列の大きさ (9!) です。変数 adjacent に隣接リストをセットします。8 パズルの座標は、左上から右へ 0 から順番に番号を振ります。

幅優先探索で解を求める関数 bfs() は次のようになります。

リスト : 幅優先探索

def bfs(start, goal):
    queue = deque()
    check = [-1] * HSIZE
    v = to_num(start)
    queue.append((start, v, start.index(0)))
    check[v] = HSIZE
    while len(queue) > 0:
        b, pv, s = queue.popleft()
        if b == goal:
            print_moves(pv, check)
            return
        for n in adjacent[s]:
            a = move_piece(b, n, s)
            v = to_num(a)
            if check[v] != -1: continue
            queue.append((a, v, n))
            check[v] = pv

引数 start, goal はスタートとゴールの盤面 (タプル) を表します。キューは Python の標準ライブラリ collections にあるクラス deque を使います。変数 queue にキューをセットします。変数 check には大きさ HSIZE のリストをセットします。リストの要素は -1 に初期化します。

次に、初期状態をキューに登録します。キューの要素はタプル (盤面, 番号, 空き場所の位置) です。to_num(start) で start を番号に変換して変数 v にセットします。check には 1 手前の盤面の番号をセットします。start の 1 手前の盤面は無いので HSIZE をセットします。移動手順は check を使って表示することができます。

while ループで、キューにデータがある間は探索を行います。キューからデータを取り出して、盤面、番号、空き場所の位置を変数 b, pv, s にセットします。b がゴールと等しい場合、ゴールに到達したので関数 print_moves() で移動手順を表示します。そして return で探索を終了します。そうでなければ、関数 move_piece() で駒を動かして次の盤面を生成します。盤面を番号に変換して変数 v にセットします。check[v] が -1 ならば新しい盤面なので、それを queue と check に登録し探索を続行します。

あとのプログラムは簡単なので説明は割愛させていただきます。詳細は プログラムリスト をお読みください。

●実行結果 (1)

それでは実行してみましょう。

>>> s = time.time(); bfs((8,6,7,2,5,4,3,0,1),(1,2,3,4,5,6,7,8,0)); time.time() - s;
(8, 6, 7, 2, 5, 4, 3, 0, 1)
(8, 6, 7, 2, 0, 4, 3, 5, 1)
(8, 0, 7, 2, 6, 4, 3, 5, 1)

    ・・省略・・

(1, 2, 3, 4, 5, 6, 0, 7, 8)
(1, 2, 3, 4, 5, 6, 7, 0, 8)
(1, 2, 3, 4, 5, 6, 7, 8, 0)
3.273693323135376

実行環境 : Python 3.8.10, Ubuntu 20.04 LTS (WSL1), Intel Core i5-6200U 2.30GHz

31 手で解くことができました。実はこれが 8 パズルの最長手数なのです。31 手で解ける局面は次の 2 つです。

      図 : 31 手で解ける局面

実行速度ですが約 3.3 秒かかりました。ちなみに、同一局面のチェックに Python の辞書を使うと約 0.5 秒でした。やっぱり Python のプリミティブな処理を使った方が速いですね。興味のある方は プログラムリスト の関数 bfs1() をお読みください。

●双方向からの探索

ところで、今回の 8 パズルようにゴールの状態が明確な場合、スタートから探索するだけではなくゴールからも探索を行うことで、幅優先探索を高速化することができます。これを「双方向探索 (bi-directional search)」といいます。

その理由を説明するために、簡単なシミュレーションをしてみましょう。たとえば、1 手進むたびに 3 つの局面が生成され、5 手で解けると仮定します。すると、n 手目で生成される局面は 3 の n 乗個になるので、初期状態から単純に探索すると、生成される局面の総数は、3 + 9 + 27 + 81 + 243 = 363 個となります。

これに対し、初期状態と終了状態から同時に探索を始めた場合、お互い 3 手まで探索した時点で同じ局面に到達する、つまり、解を見つけることができます。この場合、生成される局面の総数は 3 手目までの局面数を 2 倍した 78 個となります。

生成される局面数はぐっと少なくなりますね。局面数が減少すると同一局面の探索処理に有利なだけではなく、「キューからデータを取り出して新しい局面を作る」という根本的な処理のループ回数を減らすことになるので、処理速度は大幅に向上するのです。

●プログラムの改造

それではプログラムを改造しましょう。単純に考えると、2 つの探索処理を交互に行うことになりますが、そうするとプログラムの大幅な改造が必要になります。ここは、探索方向を示すフラグを用意することで、ひとつのキューだけで処理することにしましょう。

プログラムは次のようになります

リスト : 双方向探索

def bi_bfs(start, goal):
    queue = deque()
    check = [None] * HSIZE
    v = to_num(start)
    queue.append((start, v, FORE, start.index(0)))
    check[v] = (HSIZE, FORE)
    v = to_num(goal)
    queue.append((goal, v, BACK, goal.index(0)))
    check[v] = (HSIZE, BACK)
    while len(queue) > 0:
        b, pv, d, s = queue.popleft()
        for n in adjacent[s]:
            a = move_piece(b, n, s)
            v = to_num(a)
            if check[v] is None:
                queue.append((a, v, d, n))
                check[v] = (pv, d)
            elif check[v][1] != d:
                print_bi_moves(v, pv, check)
                return

キューに格納するタプルに方向を表すデータ (FORE, BACK) を追加します。check もタプル (番号, 方向) を格納するように変更します。check は None で初期化します。そして、start と goal を queue と check に登録します。最初に start から 1 手目の局面が生成され、次に goal から 1 手目の局面が生成されます。あとは交互に探索が行われます。

駒を移動して盤面を作る処理は同じです。そして check をチェックして、新しい局面ならば登録します。同じ局面を見つけたとき、探索方向 d と check[v][1] が異なっていれば、2 方向の探索で同一局面に到達したことがわかります。見つけた最短手順を関数 print_bi_moves() で出力します。同じ探索方向であれば、キューへの追加は行いません。

あとのプログラムは簡単なので説明は割愛させていただきます。詳細は プログラムリスト をお読みください。

●実行結果 (2)

それでは結果を示します。

前回 : 状態数 181440 個 時間 3.274 秒 
今回 : 状態数  16088 個 時間 0.247 秒

生成した局面数は 1/11 に激減し、実行速度も約 13 倍速くなりました。双方向からの探索は、本当に効果が高いですね。

●最長手数の局面

最後に最長手数の局面を求める関数 solver_max() を作ります。

リスト : 最長手数の局面を求める

def solver_max():
    start = (1,2,3,4,5,6,7,8,0)
    xs = [(start, start.index(0))]
    check = [False] * HSIZE
    check[to_num(start)] = True
    move = 0
    while True:
        ys = []
        for b, s in xs:
            for n in adjacent[s]:
                a = move_piece(b, n, s)
                v = to_num(a)
                if check[v]: continue
                ys.append((a, n))
                check[v] = True
        if not ys: break
        xs = ys
        move += 1
    print('最長手数 = ', move, '個数 =', len(xs))
    for b in xs: print(b[0])
    print('状態の総数 =', check.count(True))

リスト xs は move 手で生成した盤面と空き場所の位置を格納します。リスト check は同一局面のチェックに使用します。最初に盤面 start を xs と check に追加します。移動手順は求めないので、check には True をセットします。あとは while ループで move + 1 手の盤面を生成します。

リスト ys に move + 1 手の盤面を格納します。for ループで xs から盤面を一つずつ取り出し、move_piece() で盤面 a を生成します。同一局面がなければ、ys と check に a を追加します。for ループを終了したら、ys にデータがあるかチェックします。ys が空リストならば xs が最長手数の盤面になります。break で while ループを脱出して、最長手数と個数、盤面、状態の総数を出力します。そうでなければ、xs を ys にセットし、move を +1 して探索を続けます。

●実行結果 (3)

実行結果は次のようになりました。

>>> s = time.time(); solver_max(); time.time() - s;
最長手数 =  31 個数 = 2
(6, 4, 7, 8, 5, 0, 3, 2, 1)
(8, 6, 7, 2, 5, 4, 3, 0, 1)
状態の総数 = 181440
3.325092315673828

最長手数は 31 手で、その配置は全部で 2 通りになります。実行時間は 3.33 秒になりました。同一局面のチェックに Python の辞書を使うと、実行速度はもっと速くなります。興味のある方はいろいろ試してみてください。

●プログラムリスト

#
# eight.py : ８パズル
#
#            Copyright (C) 2022 Makoto Hiroi
#
import time
from collections import deque

#  盤面
#  0 1 2
#  3 4 5
#  6 7 8

# 定数
SIZE = 9
HSIZE = 362880

# 隣接リスト
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
]

# 階乗
fact_table = (40320, 5040, 720, 120, 24, 6, 2, 1, 0)

# 順列に番号をつける (完全ハッシュ関数)
def to_num(b):

    work = list(b)
    value = 0
    for i in range(SIZE - 1):
        value += fact_table[i] * work[i]
        for j in range(i + 1, SIZE):
            if work[i] < work[j]: work[j] -= 1
    return value

# 番号を順列に変換
def from_num(n):
    buff = list(range(SIZE))
    for i in range(SIZE - 1):
        p = n // fact_table[i]
        x = buff[i + p]
        for j in range(i + p, i, -1):
            buff[j] = buff[j - 1]
        buff[i] = x
        n %= fact_table[i]
    return tuple(buff)

# 駒の移動
def move_piece(b, n, s):
    a = list(b)
    a[s] = a[n]
    a[n] = 0
    return tuple(a)

# 手順の表示
def print_moves(n, table):
    if n != HSIZE:
        print_moves(table[n], table)
        print(from_num(n))

# 幅優先探索
def bfs(start, goal):
    queue = deque()
    v = to_num(start)
    queue.append((start, v, start.index(0)))
    check = [-1] * HSIZE
    check[v] = HSIZE
    while len(queue) > 0:
        b, pv, s = queue.popleft()
        if b == goal:
            print_moves(pv, check)
            return
        for n in adjacent[s]:
            a = move_piece(b, n, s)
            v = to_num(a)
            if check[v] != -1: continue
            queue.append((a, v, n))
            check[v] = pv

#
# Python の辞書を使う場合
#
def print_moves1(b, table):
    if b:
        print_moves1(table[b], table)
        print(b)

def bfs1(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_moves1(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

#
# 双方向探索
#
FORE = 0
BACK = 1

def print_moves_f(n, check):
    if n != HSIZE:
        print_moves_f(check[n][0], check)
        print(from_num(n))

def print_moves_b(n, check):
    while n != HSIZE:
        print(from_num(n))
        n = check[n][0]

def print_bi_moves(n, m, check):
    if check[n][1] == FORE:
        print_moves_f(n, check)
        print_moves_b(m, check)
    else:
        print_moves_f(m, check)
        print_moves_b(n, check)

def bi_bfs(start, goal):
    queue = deque()
    check = [None] * HSIZE
    v = to_num(start)
    queue.append((start, v, FORE, start.index(0)))
    check[v] = (HSIZE, FORE)
    v = to_num(goal)
    queue.append((goal, v, BACK, goal.index(0)))
    check[v] = (HSIZE, BACK)
    while len(queue) > 0:
        b, pv, d, s = queue.popleft()
        for n in adjacent[s]:
            a = move_piece(b, n, s)
            v = to_num(a)
            if check[v] is None:
                queue.append((a, v, d, n))
                check[v] = (pv, d)
            elif check[v][1] != d:
                print_bi_moves(v, pv, check)
                return

# 最長手数の局面
def solver_max():
    start = (1,2,3,4,5,6,7,8,0)
    xs = [(start, start.index(0))]
    check = [False] * HSIZE
    check[to_num(start)] = True
    move = 0
    while True:
        ys = []
        for b, s in xs:
            for n in adjacent[s]:
                a = move_piece(b, n, s)
                v = to_num(a)
                if check[v]: continue
                ys.append((a, n))
                check[v] = True
        if not ys: break
        xs = ys
        move += 1
    print('最長手数 = ', move, '個数 =', len(xs))
    for b in xs: print(b[0])
    print('状態の総数 =', check.count(True))