# 2025s スライドパズル
from collections import deque

# 盤面サイズ
N = 3
GOAL = (1, 2, 3, 4, 5, 6, 7, 8, 9)  # 9が空白

# 上下左右の移動
MOVES = [(-1, 0), (1, 0), (0, -1), (0, 1)]


# 1次元→2次元座標
def index_to_xy(index):
    return index // N, index % N


# 2次元→1次元
def xy_to_index(x, y):
    return x * N + y


# 子ノード生成（駒移動）
def get_next_states(board):
    next_states = []

    blank_index = board.index(9)
    x, y = index_to_xy(blank_index)

    for dx, dy in MOVES:
        nx, ny = x + dx, y + dy
        if 0 <= nx < N and 0 <= ny < N:
            new_index = xy_to_index(nx, ny)

            new_board = list(board)
            # 空白と交換
            new_board[blank_index], new_board[new_index] = \
                new_board[new_index], new_board[blank_index]

            next_states.append(tuple(new_board))

    return next_states


# BFSで最小解を求める
def solve(start):
    queue = deque()
    queue.append(start)

    # 探索済み
    visited = set()
    visited.add(start)

    # 親ノード（経路復元用）
    parent = {}
    parent[start] = None

    while queue:
        current = queue.popleft()

        # ゴール判定
        if current == GOAL:
            return reconstruct_path(parent, current)

        # 子ノード生成
        for next_state in get_next_states(current):
            if next_state not in visited:
                visited.add(next_state)
                parent[next_state] = current
                queue.append(next_state)

    return None  # 解なし


# 経路復元
def reconstruct_path(parent, goal):
    path = []
    current = goal

    while current is not None:
        path.append(current)
        current = parent[current]

    path.reverse()
    return path


# 表示用
def print_board(board):
    for i in range(N):
        print(board[i*N:(i+1)*N])
    print()


# 実行例
if __name__ == "__main__":
    start = (8, 6, 7,
             2, 5, 4,
             3, 9, 1)  # 初期状態（9が空白）

    path = solve(start)

    if path:
        print("手数:", len(path) - 1)
        for step in path:
            print_board(step)
    else:
        print("解なし")