Pythonで8パズルの最短手数を求めるプログラムを実装する方法

8パズルは、3×3の盤面に0から8までの重複しない数字が配置された古典的なスライディングパズルです。0（空白）は上下左右の隣接マスと入れ替えることができ、すべての数字を昇順に並べ替えた状態（0, 1, 2, ..., 8）を目標とします。本記事では、初期盤面からゴール状態へ到達するまでの最小手数を求めるPythonプログラムを紹介します。

問題の例

例として、次のような盤面が入力された場合を考えます。

この場合の出力は 4 になります。つまり、4回の入れ替え操作でゴール状態に到達できることを意味します。

解法の考え方：幅優先探索（BFS）

この問題は幅優先探索（BFS）を用いることで効率的に解けます。BFSは手数の少ない状態から順番に探索を広げていくため、初めてゴール状態が見つかった時点の手数が必ず最小手数になるという性質があります。

1. find_next()：次に取りうる盤面を生成する

現在の盤面（ノード）を受け取り、0を1手で動かせるすべての盤面パターンを返す関数です。

• moves：各位置において0が移動できる隣接位置の一覧を定義した辞書（例：{0: [1, 3], 1: [0, 2, 4], ...}）。角のマスは2方向、辺のマスは3方向、中央のマスは4方向に移動可能です。
• pos_0：nodeの中で0が存在する位置
• moves[pos_0]の各移動先について、0とその位置の数字を入れ替えた新しい盤面（new_node）を作成し、resultsに追加
• results を返す

2. get_paths()：BFSで最短手数を探索する

• cnt（現在の手数）を0で初期化
• 無限ループの中で、dictの値がcntと一致するノード一覧（current_nodes）を取得
• current_nodesが空の場合は解が存在しないため -1 を返す
• 各ノードについて find_next() で次の盤面を生成し、未探索のものだけ dict[move] = cnt + 1 として登録
• 生成した盤面がゴール状態 (0, 1, 2, ..., 8) と一致したら、cnt + 1 を返す
• cnt を1増やして次の層（手数+1の状態群）へ進む

3. メイン処理（solve）

• 2次元のboardを行ごとに連結して1次元化し、タプル flatten に変換する（辞書のキーとして扱えるようにするため）
• dict[flatten] = 0 として初期状態を手数0で登録
• 初期状態がすでにゴール状態なら 0 を返す
• それ以外は get_paths(dict) の結果を返す

実装コード

以下が実際のPython実装です。処理の流れがわかるようコメントを付けています。

class Solution:
    def solve(self, board):
        # 辞書とフラット化した盤面を準備
        dict = {}
        flatten = []
        for i in range(len(board)):
            flatten += board[i]
        flatten = tuple(flatten)

        # 初期状態を手数0で登録
        dict[flatten] = 0

        # すでにゴール状態なら0を返す
        if flatten == (0, 1, 2, 3, 4, 5, 6, 7, 8):
            return 0

        return self.get_paths(dict)

    def get_paths(self, dict):
        cnt = 0
        while True:
            # 現在の手数cntで到達できるノードを取得
            current_nodes = [x for x in dict if dict[x] == cnt]
            if len(current_nodes) == 0:
                return -1  # 解なし

            for node in current_nodes:
                next_moves = self.find_next(node)
                for move in next_moves:
                    # 未探索の盤面なら手数cnt+1で登録
                    if move not in dict:
                        dict[move] = cnt + 1
                    # ゴール状態に到達したら手数を返す
                    if move == (0, 1, 2, 3, 4, 5, 6, 7, 8):
                        return cnt + 1
            cnt += 1

    def find_next(self, node):
        # 各位置で0が移動できる隣接位置の定義
        moves = {
            0: [1, 3],
            1: [0, 2, 4],
            2: [1, 5],
            3: [0, 4, 6],
            4: [1, 3, 5, 7],
            5: [2, 4, 8],
            6: [3, 7],
            7: [4, 6, 8],
            8: [5, 7],
        }

        results = []
        pos_0 = node.index(0)
        for move in moves[pos_0]:
            new_node = list(node)
            new_node[move], new_node[pos_0] = new_node[pos_0], new_node[move]
            results.append(tuple(new_node))

        return results

ob = Solution()
matrix = [
    [3, 1, 2],
    [4, 7, 5],
    [6, 8, 0]
]
print(ob.solve(matrix))

入力

matrix = [
    [3, 1, 2],
    [4, 7, 5],
    [6, 8, 0]
]

出力

4

まとめ

このプログラムでは、盤面をタプルとして管理することでハッシュ可能なキーとして扱い、訪問済みの状態を辞書で記録することで同じ盤面の再探索を防止しています。BFSの性質上、ゴールに到達した時点の手数が必ず最小手数となる点がポイントです。また、初期配置によっては物理的に解が存在しないケースもあるため、その場合は探索対象が尽きた時点で -1 が返される仕組みになっています。