#A* algo 8 puzzle

import heapq

moves = {
'U': -3,
'D': 3,
'L': -1,
'R': 1
}

def heuristic(state, goal):
distance = 0
for i in range(9):
if state[i] != 0:
x1, y1 = divmod(i, 3)
x2, y2 = divmod(goal.index(state[i]), 3)
distance += abs(x1 - x2) + abs(y1 - y2)
return distance

def move(state, direction):
new_state = state[:]
index = new_state.index(0)
target = index + moves[direction]
new_state[index], new_state[target] = new_state[target], new_state[index]
return new_state

def is_valid(index, move):
if move == 'U' and index < 3:
return False
if move == 'D' and index > 5:
return False
if move == 'L' and index % 3 == 0:
return False
if move == 'R' and index % 3 == 2:
return False
return True

def a_star(start, goal):
heap = []
heapq.heappush(heap, (heuristic(start, goal), 0, start, []))
visited = set()

while heap:
    est_cost, depth, state, path = heapq.heappop(heap)

    if state == goal:
        return path

    visited.add(tuple(state))
    index = state.index(0)

    for m in moves:
        if is_valid(index, m):
            new_state = move(state, m)
            if tuple(new_state) not in visited:
                heapq.heappush(heap, (
                    depth + 1 + heuristic(new_state, goal),
                    depth + 1,
                    new_state,
                    path + [m]
                ))

return None

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

def main():
print("Enter the initial state (0 for blank):")
start = list(map(int, input().split()))

print("Enter the goal state (0 for blank):")
goal = list(map(int, input().split()))

result = a_star(start, goal)

if result is None:
    print("No solution found.")
else:
    print("\nSolution found!")
    temp = start[:]
    print_board(temp)
    for move_direction in result:
        temp = move(temp, move_direction)
        print(f"Move: {move_direction}")
        print_board(temp)

if name == "main":
main()