Puzzle DE Programming

パズルの説明

今回は 15 パズルでお馴染みの「スライディングブロックパズル (スライドパズル)」を Python3 で解いてみましょう。参考文献『世界のパズル百科イラストパズルワンダーランド』によると、15 パズルはアメリカのサム・ロイドが 1870 年代に考案したパズルで、彼はパズルの神様と呼ばれるほど有名なパズル作家だそうです。

 ┌─┬─┬─┬─┐
 │１│２│３│４│
 ├─┼─┼─┼─┤
 │５│６│７│８│
 ├─┼─┼─┼─┤
 │９│10│11│12│
 ├─┼─┼─┼─┤
 │13│14│15│  │
 └─┴─┴─┴─┘

  図 1 : 15 パズル

15 パズルは図 1 に示すように、1 から 15 までの駒を並べるパズルです。駒の動かし方は、1 回に 1 個の駒を空いている隣の場所に滑らせる、というものです。駒を跳び越したり持ち上げたりすることはできません。

15 パズルの場合、駒の配置は空き場所がどこでもいいことにすると、16! (約 2e13) 通りもあります。実際には、15 パズルの性質からその半分になるのですが、それでもパソコンで扱うにはあまりにも大きすぎる数です。そこで、盤面を一回り小さくした、1 から 7 までの数字を並べる「7 パズル」を考えることにします。

  ┌─┬─┬─┬─┐    ┌─┬─┬─┬─┐
  │  │７│２│１│    │１│２│３│４│
  ├─┼─┼─┼─┤ => ├─┼─┼─┼─┤
  │４│３│６│５│    │５│６│７│  │
  └─┴─┴─┴─┘    └─┴─┴─┴─┘
       スタート              ゴール

              図 2 : ７パズル

15 パズルは 4 行 4 列の盤ですが、7 パズルは 2 行 4 列と盤を小さくしたパズルです。7 パズルの場合、駒の配置は空き場所がどこでもいいことにすると、8! = 40,320 通りあります。ところが 15 パズルや 7 パズルの場合、参考文献『特集コンピュータパズルへの招待 スライディングブロック編』によると、『適当な 2 つの駒をつまみ上げて交換する動作を偶数回行った局面にした移行できない』 ことが証明されているそうです。

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

上図の７パズルで、スタートからゴールまでの最短手数とその手順を求めてください。

●幅優先探索による解法

それではプログラムを作りましょう。スタートからゴールに到達するまでの最短手数を幅優先探索で求めます。7 パズルの盤面は一次元配列 (Python のタプル) を使って表します。隣接リストの定義は次のようになります。

リスト : 隣接リスト

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

# 隣接リスト
adjacent = [
    [1, 4],     # 0
    [0, 2, 5],  # 1
    [1, 6, 3],  # 2
    [2, 7],     # 3
    [0, 5],     # 4
    [1, 4, 6],  # 5
    [2, 5, 7],  # 6
    [3, 6]

次は駒を動かして新しい盤面を生成する関数 move_piece() を作ります。

リスト : 駒の移動

def move_piece(b, n, s):
    a = list(b)
    a[s] = a[n]
    a[n] = 0
    return tuple(a)

引数 b は盤面を表すタプル、n は動かす駒の位置、s は空き場所の位置を表します。Python のタプルは immutable なデータ型なので、関数 list() でリスト a に変換してから、a の要素を書き換えます。最後に関数 tuple() で a をタプルに変換してから返します。

次は幅優先探索で解を求める関数 bfs() を作ります。

リスト : 幅優先探索

def bfs(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_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

キューは Python の標準ライブラリ collections にあるクラス deque を使います。これを変数 queue にセットします。キューの要素はタプル (盤面, 空き場所の位置) です。同一局面のチェックは Python の辞書を使います。変数 check を空の辞書で初期化して、start の局面を登録します。今回は check に 1 手前の盤面をセットし、これを使って移動手順を表示します。start の 1 手前の盤面は無いので、空のタプルをセットします。

次の while ループで、ゴール (goal) に到達するまで探索を繰り返します。キューから盤面と空き場所の位置を取り出して変数 b, s にセットします。b が goal と等しければ、解を求めることができました。関数 print_moves() で移動手順を表示します。

そうでなければ、move_piece() で駒を動かして盤面 a を生成します。演算子 in で同一局面が無いことを確認したら、キューと check に a を登録して探索を続けます。キューが空になり while ループが終了する場合、start は goal に到達できない、つまり解くことができなかったことになります。

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

●実行結果 (1)

これでプログラムは完成です。それでは実行してみましょう。

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

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

36 手で解くことができました。実行時間は 50 msec でした。7 パズルの場合、最長手数は 36 手で、スタートが最長手数の盤面になります。

●最長手数の求め方

次は最長手数の局面を求めてみましょう。最長手数の求め方ですが、20160 通りの配置の最短手数がすべてわかれば、最長の手数となる配置を求めることができます。しかし、この方法では時間がかかりそうです。そこで、完成形から始めていちばん長い手数の局面を生成することにします。

まず、完成形から駒を動かして 1 手で到達する局面をすべて作ります。次に、これらの局面から駒を動かして新しい局面を作れば、完成形から 2 手で到達する局面となります。このように、手数を 1 手ずつ伸ばしていき、新しい局面が生成できなくなった時点での手数が求める最長手数となります。この処理は幅優先探索を使えばぴったりです。なお、このプログラムの目的は、一番長い手数となる配置を求めることなので、その手順を表示することはしません。

●プログラムの作成

それではプログラムを作ります。次のリストを見てください。

リスト : 8 パズルの最長手数を求める

def solver_max():
    start = (1,2,3,4,5,6,7,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('最長手数 =', move, '個数 =', len(xs))
    for b in xs: print(b[0])
    print('状態の総数 =', len(check))

リスト 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 して探索を続けます。

●実行結果 (2)

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

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

最長手数は 36 手で、その配置は 1 通りしかありません。

●反復深化による解法

次は「反復深化」で 7 パズルを解いてみましょう。反復深化は局面を保存する必要が無いため、必要となるメモリは深さ優先探索と同程度で済みます。また、プログラムも深さ優先探索と同じくらい簡単に作成することができます。ただし、同じ探索を何度も繰り返すため実行時間が増大する、という欠点があります。ようするに、使用するメモリは少ないが実行時間が長くなるアルゴリズムなのです。実行時間が長くなるといっても、枝刈りを工夫することでパズルを高速に解くことができます。

盤面はリストで表して、深さ優先探索を行う関数 dfs() の引数 board に渡します。駒の移動は board を書き換えて、バックトラックする時は元に戻すことにします。動かした駒はリスト moves に格納します。動かした駒がわかれば局面を再現できるので、それで移動手順を表すことにしましょう。

それでは、深さ優先探索を行う関数 dfs() を作ります。次のリストを見てください。

リスト : 単純な反復深化による解法

def dfs(n, board, goal, space, limit, moves):
    global cnt
    if n == limit:
        if board == goal:
            print(moves[1:])
            cnt += 1
    else:
        for x in adjacent[space]:
            p = board[x]
            if p == moves[-1]: continue
            board[space] = p
            board[x] = 0
            moves.append(p)
            dfs(n + 1, board, goal, x, limit, moves)
            moves.pop()
            board[x] = p
            board[space] = 0

dfs() の引数 n が手数、board が探索中の盤面、goal がゴールの盤面、space が空き場所の位置、limit が上限値、moves が動かした駒を格納するリスト (手順) を表します。手数が上限値に達したら、パズルが解けたかチェックします。goal に到達したら、解の総数をカウントする変数 cnt をインクリメントし、print() で手順を表示します。上限値に達していない場合は、駒を移動して新しい盤面を作ります。

7 パズルのように、元の局面に戻すことが可能 (可逆的) なパズルの場合、単純な深さ優先探索では同じ移動手順を何度も繰り返すことがあります。そうなると、とんでもない解を出力するだけではなく、再帰呼び出しが深くなるとスタックがオーバーフローしてプログラムの実行が停止してしまいます。

このような場合、局面の履歴を保存しておいて同じ局面がないかチェックすることで、解を求めることができるようになります。ただし、同一局面をチェックする分だけ時間が余分にかかりますし、最初に見つかる解が最短手数とは限りません。

反復深化では深さが制限されているため、同一局面のチェックを行わなくてもスタックオーバーフローが発生することはありません。そのかわり、無駄な探索はどうしても避けることができません。7 パズルの場合、1 手前に動かした駒を再度動かすと 2 手前の局面に戻ります。完全ではありませんが、このチェックを入れるだけでもかなりの無駄を省くことができます。

プログラムでは、リスト moves に移動した駒を格納しているので、1 手前と同じ駒は動かさないようにチェックしています。moves[0] はダミーデータで駒以外の値 (-1) をセットします。moves[1] 以降のデータが実際に動かした駒になります。

次は dfs() を呼び出すプログラムを作ります。

リスト : 反復深化の実行

def solver_ids(start, goal):
    global cnt
    cnt = 0
    limit = 1
    while True:
        print(f'---- {limit} -----')
        dfs(0, start, goal, start.index(0), limit, [-1])
        if cnt > 0: break
        limit += 1
    print('総数 =', cnt)

変数 limit が上限値を表します。limit を 1 手ずつ増やして dfs() を呼び出します。グローバル変数 cnt が 0 より大きくなれば解が見つかったのでループを脱出します。プログラムはこれで完成です。

●実行結果 (3)

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

>>> s = time.time(); solver_ids([0,7,2,1,4,3,6,5],[1,2,3,4,5,6,7,0]); time.time() - s
---- 1 -----
---- 2 -----
---- 3 -----

・・・省略・・・

---- 34 -----
---- 35 -----
---- 36 -----
[7, 2, 6, 3, 2, 6, 3, 5, 1, 3, 5, 2, 4, 7, 6, 5, 2, 1, 3, 2, 1, 4, 7, 6, 5, 1, 2, 3, 4, 
 7, 6, 5, 1, 2, 3, 4]
[7, 2, 6, 3, 4, 7, 2, 6, 1, 5, 3, 4, 7, 2, 6, 1, 5, 3, 4, 7, 1, 6, 2, 1, 6, 5, 7, 6, 5, 
 2, 1, 5, 6, 7, 3, 4]
[7, 2, 6, 3, 4, 7, 2, 6, 1, 5, 3, 4, 7, 2, 6, 1, 5, 3, 4, 7, 1, 6, 2, 1, 6, 5, 3, 4, 7, 
 6, 5, 2, 1, 5, 6, 7]

・・・省略・・・

[4, 3, 6, 5, 1, 2, 7, 4, 3, 6, 5, 1, 2, 7, 4, 5, 6, 3, 5, 6, 1, 2, 7, 4, 6, 1, 3, 5, 1,
 6, 2, 3, 6, 2, 3, 7]
[4, 3, 6, 5, 1, 2, 7, 4, 3, 6, 5, 1, 2, 7, 4, 5, 6, 3, 5, 6, 1, 2, 7, 4, 6, 1, 3, 5, 1,
 3, 2, 6, 3, 2, 6, 7]
[4, 3, 6, 5, 1, 2, 7, 4, 3, 6, 5, 1, 2, 7, 4, 5, 1, 2, 7, 4, 5, 3, 6, 1, 3, 5, 2, 3, 5,
 6, 1, 5, 6, 2, 3, 7]
総数 = 24
38.2415337562561

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

最短手数は 36 手で 24 通りの手順が表示されました。実行時間は約 38.3 秒かかりました。単純な反復深化なので、時間がかかるのはしかたがありません。そこで、反復深化の常套手段である「下限値枝刈り法」を使うことにしましょう。

●下限値枝刈り法

下限値枝刈り法は難しいアルゴリズムではありません。たとえば、5 手進めた局面を考えてみます。探索の上限値が 10 手とすると、あと 5 手だけ動かすことができますね。この時、パズルを解くのに 6 手以上かかることがわかれば、ここで探索を打ち切ることができます。

このように、必要となる最低限の手数が明確にわかる場合、この値を「下限値 (Lower Bound)」と呼びます。この下限値を求めることができれば、「今の移動手数＋下限値」が探索手数を超えた時点で、枝刈りすることが可能になります。これが下限値枝刈り法の基本的な考え方です。

下限値を求める方法ですが、これにはいろいろな方法が考えられます。今回は、各駒が正しい位置へ移動するまでの手数 (移動距離) ^[*1] を下限値として利用することにしましょう。次の図を見てください。

  1  2  3  4  |  0(0)  7(2)  2(1)  1(3) 
  5  6  7  0  |  4(4)  3(2)  6(1)  5(3)

    完成形         初期状態 : 合計 16

        図 : 下限値の求め方

たとえば、右下にある 5 の駒を左上の正しい位置に移動するには、最低でも 3 手必要です。もちろん、ほかの駒との関連で、それ以上の手数が必要になる場合もあるでしょうが、3 手より少なくなることは絶対にありません。同じように、各駒について最低限必要な手数を求めることができます。そして、その合計値はパズルを解くのに最低限必要な手数となります。これを下限値として利用することができます。ちなみに、上図の初期状態の下限値は 16 手になります。

下限値枝刈り法を使う場合、下限値の計算を間違えると正しい解を求めることができなくなります。たとえば、10 手で解ける問題の下限値を 11 手と計算すれば、最短手数を求めることができなくなります。それどころか、10 手の解しかない場合は、答えを求めることすらできなくなります。下限値の計算には十分に注意してください。

●下限値枝刈り法のプログラム

それでは、プログラムを作りましょう。下限値の求め方ですが、駒を動かすたびに各駒の移動距離を計算していたのでは時間がかかります。7 パズルの場合、1 回に一つの駒しか移動しないので、初期状態の下限値を求めておいて、動かした駒の差分だけ計算すればいいでしょう。また、駒の移動距離はいちいち計算するのではなく、あらかじめ計算した結果をリストに格納しておきます。このリストを distance とすると、盤面から移動距離を求めるプログラムは次のようになります。

リスト : 移動距離を求める

distance = [
    [0, 0, 0, 0, 0, 0, 0, 0], # dummy
    [0, 1, 2, 3, 1, 2, 3, 4], # 1
    [1, 0, 1, 2, 2, 1, 2, 3], # 2
    [2, 1, 0, 1, 3, 2, 1, 2], # 3
    [3, 2, 1, 0, 4, 3, 2, 1], # 4
    [1, 2, 3, 4, 0, 1, 2, 3], # 5
    [2, 1, 2, 3, 1, 0, 1, 2], # 6
    [3, 2, 1, 2, 2, 1, 0, 1]  # 7
]

def get_lower_value(b):
    lower = 0
    for i, p in enumerate(b):
        lower += distance[p][i]
    return lower

distance は 2 次元配列 (リスト) で「駒の種類×駒の位置」を表しています。空き場所は関係ないので、distance[0] はダミーとなります。関数 get_lower_value() は盤面 b にある駒と位置から移動距離を求めます。変数 lower を 0 に初期化して、駒の移動距離を distance から求めて lower に足し算するだけです。

次は、下限値枝刈り法による反復深化を行う関数 dfs1() を作ります。次のリストを見てください。

リスト : 下限値枝刈り法

def dfs1(n, board, goal, space, limit, lower, moves):
    global cnt
    if n == limit:
        if board == goal:
            print(moves[1:])
            cnt += 1
    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)
            dfs1(n + 1, board, goal, x, limit, newlower, moves)
            moves.pop()
            board[x] = p
            board[space] = 0

dfs1() の引数 lower は現在の盤面 board の下限値を表しています。駒を動かしたら差分を計算して、新しい下限値 newlower を求めます。そして、newlower + n が上限値 limit を越えたら枝刈りを行います。limit 以下であれば dfs1() を再帰呼び出しします。追加する処理はこれだけで、あとは反復深化のプログラムと同じです。とても簡単ですね。

最後に dfs1() を呼び出す処理を修正します。次のリストを見てください。

リスト : dfs1() の呼び出し

def solver_ids1(start, goal):
    global cnt
    cnt = 0
    lower = get_lower_value(start)
    limit = lower
    while True:
        print(f'---- {limit} -----')
        dfs1(0, start, goal, start.index(0), limit, lower, [-1])
        if cnt > 0: break
        limit += 1
    print('総数 =', cnt)

get_lower_value() で初期状態の下限値 lower を求めます。下限値がわかるのですから、上限値 limit は 1 手からではなく下限値 lower からスタートします。あとは dfs1() に下限値 lower を渡して呼び出すだけです。プログラムの主な修正はこれだけです。

●実行結果 (4)

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

>>> s = time.time(); solver_ids1([0,7,2,1,4,3,6,5],[1,2,3,4,5,6,7,0]); time.time() - s
---- 16 -----
---- 17 -----
---- 18 -----

・・・省略・・・

---- 34 -----
---- 35 -----
---- 36 -----
[7, 2, 6, 3, 2, 6, 3, 5, 1, 3, 5, 2, 4, 7, 6, 5, 2, 1, 3, 2, 1, 4, 7, 6, 5, 1, 2, 3, 4,
 7, 6, 5, 1, 2, 3, 4]
[7, 2, 6, 3, 4, 7, 2, 6, 1, 5, 3, 4, 7, 2, 6, 1, 5, 3, 4, 7, 1, 6, 2, 1, 6, 5, 7, 6, 5,
 2, 1, 5, 6, 7, 3, 4]
[7, 2, 6, 3, 4, 7, 2, 6, 1, 5, 3, 4, 7, 2, 6, 1, 5, 3, 4, 7, 1, 6, 2, 1, 6, 5, 3, 4, 7,
 6, 5, 2, 1, 5, 6, 7]

・・・省略・・・

[4, 3, 6, 5, 1, 2, 7, 4, 3, 6, 5, 1, 2, 7, 4, 5, 6, 3, 5, 6, 1, 2, 7, 4, 6, 1, 3, 5, 1,
 6, 2, 3, 6, 2, 3, 7]
[4, 3, 6, 5, 1, 2, 7, 4, 3, 6, 5, 1, 2, 7, 4, 5, 6, 3, 5, 6, 1, 2, 7, 4, 6, 1, 3, 5, 1,
 3, 2, 6, 3, 2, 6, 7]
[4, 3, 6, 5, 1, 2, 7, 4, 3, 6, 5, 1, 2, 7, 4, 5, 1, 2, 7, 4, 5, 3, 6, 1, 3, 5, 2, 3, 5,
 6, 1, 5, 6, 2, 3, 7]
総数 = 24
0.5249433517456055

実行時間は 0.53 秒でした。下限値枝刈り法の効果はとても高いことがわかります。

●プログラムリスト

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

#  盤面
# 0 1 2 3
# 4 5 6 7
#
# 状態の総数は 8! / 2 = 20160

# 隣接リスト
adjacent = [
    [1, 4],     # 0
    [0, 2, 5],  # 1
    [1, 6, 3],  # 2
    [2, 7],     # 3
    [0, 5],     # 4
    [1, 4, 6],  # 5
    [2, 5, 7],  # 6
    [3, 6]
]

# 駒の移動
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):
    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():
    start = (1,2,3,4,5,6,7,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('最長手数 =', move, '個数 =', len(xs))
    for b in xs: print(b[0])
    print('状態の総数 =', len(check))

# 反復深化
def dfs(n, board, goal, space, limit, moves):
    global cnt
    if n == limit:
        if board == goal:
            print(moves[1:])
            cnt += 1
    else:
        for x in adjacent[space]:
            p = board[x]
            if p == moves[-1]: continue
            board[space] = p
            board[x] = 0
            moves.append(p)
            dfs(n + 1, board, goal, x, limit, moves)
            moves.pop()
            board[x] = p
            board[space] = 0

def solver_ids(start, goal):
    global cnt
    cnt = 0
    limit = 1
    while True:
        print(f'---- {limit} -----')
        dfs(0, start, goal, start.index(0), limit, [-1])
        if cnt > 0: break
        limit += 1
    print('総数 =', cnt)

#
# 下限値枝刈り法
#

# マンハッタン距離
# 1 2 3 4
# 5 6 7 0

distance = [
    [0, 0, 0, 0, 0, 0, 0, 0], # dummy
    [0, 1, 2, 3, 1, 2, 3, 4], # 1
    [1, 0, 1, 2, 2, 1, 2, 3], # 2
    [2, 1, 0, 1, 3, 2, 1, 2], # 3
    [3, 2, 1, 0, 4, 3, 2, 1], # 4
    [1, 2, 3, 4, 0, 1, 2, 3], # 5
    [2, 1, 2, 3, 1, 0, 1, 2], # 6
    [3, 2, 1, 2, 2, 1, 0, 1]  # 7
]

def get_lower_value(b):
    lower = 0
    for i, p in enumerate(b):
        lower += distance[p][i]
    return lower

def dfs1(n, board, goal, space, limit, lower, moves):
    global cnt
    if n == limit:
        if board == goal:
            print(moves[1:])
            cnt += 1
    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)
            dfs1(n + 1, board, goal, x, limit, newlower, moves)
            moves.pop()
            board[x] = p
            board[space] = 0

def solver_ids1(start, goal):
    global cnt
    cnt = 0
    lower = get_lower_value(start)
    limit = lower
    while True:
        print(f'---- {limit} -----')
        dfs1(0, start, goal, start.index(0), limit, lower, [-1])
        if cnt > 0: break
        limit += 1
    print('総数 =', cnt)