from collections import deque
def solve_8_puzzle(initial, goal):
    queue, visited = deque([(initial, [])]), set()
    while queue:
        state, path = queue.popleft()
        if state == goal: return path + [state]
        visited.add(tuple(map(tuple, state)))
        empty = [(i, j) for i in range(3) for j in range(3) if state[i][j] == 0][0]
        for move in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            new_i, new_j = empty[0] + move[0], empty[1] + move[1]
            if 0 <= new_i < 3 and 0 <= new_j < 3:
                new_state = [row[:] for row in state]
                new_state[empty[0]][empty[1]], new_state[new_i][new_j] = new_state[new_i][new_j], new_state[empty[0]][empty[1]]
                if tuple(map(tuple, new_state)) not in visited:
                    queue.append((new_state, path + [state]))
    return None

initial = [
    [1, 2, 3],
    [5, 6, 0],
    [7, 8, 4]]
goal = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 0]]
solution = solve_8_puzzle(initial, goal)
if solution:
    for step, state in enumerate(solution):
        print(f"Step {step}:")
        for row in state: print(" ".join(map(str, row)))
else:
    print("No solution exists.")