from heapq import heappop, heappush
from itertools import count

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


def manhattan(board):
    distance = 0
    for index, tile in enumerate(board):
        if tile:
            row, col = divmod(index, 3)
            target_row, target_col = divmod(tile - 1, 3)
            distance += abs(row - target_row) + abs(col - target_col)
    return distance


def neighbors(board):
    blank = board.index(0)
    row, col = divmod(blank, 3)
    for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        nr, nc = row + dr, col + dc
        if 0 <= nr < 3 and 0 <= nc < 3:
            other = nr * 3 + nc
            candidate = list(board)
            candidate[blank], candidate[other] = candidate[other], candidate[blank]
            yield tuple(candidate)


def solve(start):
    start = tuple(start)
    if (len(start) != 9 or any(type(x) is not int for x in start)
            or set(start) != set(range(9))):
        raise ValueError("Use each integer 0 through 8 exactly once")
    tiles = [tile for tile in start if tile]
    inversions = sum(a > b for i, a in enumerate(tiles) for b in tiles[i + 1:])
    if inversions % 2:
        return None  # For this odd-width board and fixed goal only.

    serial = count()
    frontier = [(manhattan(start), next(serial), 0, start)]
    best_cost = {start: 0}
    previous = {start: None}
    while frontier:
        _, _, cost, board = heappop(frontier)
        if cost != best_cost[board]:
            continue  # An older, more expensive entry for this board.
        if board == GOAL:
            path = []
            while board is not None:
                path.append(board)
                board = previous[board]
            return path[::-1]
        for candidate in neighbors(board):
            new_cost = cost + 1
            if new_cost < best_cost.get(candidate, float("inf")):
                best_cost[candidate] = new_cost
                previous[candidate] = board
                heappush(frontier, (new_cost + manhattan(candidate),
                                    next(serial), new_cost, candidate))
    return None


if __name__ == "__main__":
    path = solve((1, 2, 3, 4, 5, 6, 0, 7, 8))
    print("Moves:", len(path) - 1)
    for board in path:
        for row in range(0, 9, 3):
            print(board[row:row + 3])
        print()