from heapq import heappush, heappop
from itertools import count
from math import inf

def manhattan(a, b):
    return sum(abs(x-y) for x,y in zip(a,b))

def search(start, goal, neighbours, heuristic, greedy=False):
    """neighbours(state) returns (next_state, edge_cost) pairs. Costs >= 0.
    A*: priority g+h; Greedy: priority h. Return path, actual cost, expansions.
    A* can reopen states when a better path is found; no stale path is expanded.
    """
    serial = count()
    pq = [(heuristic(start), next(serial), 0, start)]
    best, parent, closed = {start: 0}, {start: None}, set()
    explored = 0
    while pq:
        _, _, g, u = heappop(pq)
        if g != best[u] or (greedy and u in closed):
            continue
        explored += 1  # Includes goal when popped; stale queue entries excluded.
        if u == goal:
            path = []
            while u is not None:
                path.append(u)
                u = parent[u]
            return path[::-1], g, explored
        closed.add(u)
        for v, cost in neighbours(u):
            if cost < 0:
                raise ValueError('Search requires nonnegative costs')
            new_g = g + cost
            if (not greedy or v not in closed) and new_g < best.get(v, inf):
                best[v], parent[v] = new_g, u
                priority = heuristic(v) if greedy else new_g + heuristic(v)
                heappush(pq, (priority, next(serial), new_g, v))
    return [], inf, explored

def eight_puzzle(start,goal=(1,2,3,4,5,6,7,8,0)):
    if len(start)!=9 or set(start)!=set(range(9)) or len(goal)!=9 or set(goal)!=set(range(9)):
        raise ValueError('Each state must contain 0..8 exactly once')
    rank={tile:i for i,tile in enumerate(goal) if tile!=0}
    seq=[rank[t] for t in start if t!=0]
    inversions=sum(seq[i]>seq[j] for i in range(8) for j in range(i+1,8))
    if inversions%2: print('Unsolvable: inversion parity mismatch'); return [],inf,0
    target={tile:divmod(i,3) for i,tile in enumerate(goal)}
    def h(state):
        return sum(manhattan(divmod(i,3),target[t]) for i,t in enumerate(state) if t)
    def neighbours(state):
        i=state.index(0); r,c=divmod(i,3); out=[]
        for nr,nc in [(r+1,c),(r-1,c),(r,c+1),(r,c-1)]:
            if 0<=nr<3 and 0<=nc<3:
                j=nr*3+nc; t=list(state); t[i],t[j]=t[j],t[i]; out.append((tuple(t),1))
        return out
    path,cost,explored=search(tuple(start),tuple(goal),neighbours,h)
    for state in path:
        for i in (0,3,6): print(*state[i:i+3])
        print()
    print('Moves:',cost,'States explored:',explored)
    return path,cost,explored



print("Enter puzzle tiles row by row, using 0 for the blank.")
start = tuple(map(int, input("Initial state (9 integers): ").split()))
goal_text = input("Goal state (9 integers; Enter for 1 2 3 4 5 6 7 8 0): ").strip()
goal = tuple(map(int, goal_text.split())) if goal_text else (1, 2, 3, 4, 5, 6, 7, 8, 0)
path, moves, explored = eight_puzzle(start, goal)
