from collections import deque

def print_board(board):
    print()
    for i in range(0, 9, 3):
        print(board[i:i+3])

def solve_8_puzzle(start, goal):
    moves = [(-1, 0, "Up"), (1, 0, "Down"), (0, -1, "Left"), (0, 1, "Right")]
    queue = deque([(start, [])])  # (current state, path)
    visited = set()

    while queue:
        board, path = queue.popleft()
        if board == goal:
            print("Solution found!")
            for step in path + [board]:
                print_board(step)
            return

        visited.add(tuple(board))
        zero_pos = board.index(0)
        x, y = zero_pos // 3, zero_pos % 3

        for dx, dy, direction in moves:
            new_x, new_y = x + dx, y + dy
            if 0 <= new_x < 3 and 0 <= new_y < 3:
                new_zero_pos = new_x * 3 + new_y
                new_board = board[:]
                new_board[zero_pos], new_board[new_zero_pos] = new_board[new_zero_pos], new_board[zero_pos]
                if tuple(new_board) not in visited:
                    queue.append((new_board, path + [board]))

start = [1, 2, 3, 4, 0, 5, 6, 7, 8]
goal = [1, 2, 3, 4, 5, 6, 7, 8, 0]
solve_8_puzzle(start, goal)