How can I write a code in Python to solve the eight-piece game through the A* algorithm and enable the user to define any initial and final state of the game, and the output will be a diagram of the sequence of arriving at the solution?

import heapq

def get_possible_moves(state):

 possible_moves = []

 zero_index = state.index(0)

 if zero_index not in [0, 1, 2]:

     new_state = state.copy()

     new_state[zero_index], new_state[zero_index - 3] = new_state[zero_index - 3], new_state[zero_index]

     possible_moves.append((new_state, "Up"))

 if zero_index not in [0, 3, 6]:

     new_state = state.copy()

     new_state[zero_index], new_state[zero_index - 1] = new_state[zero_index - 1], new_state[zero_index]

     possible_moves.append((new_state, "Left"))

 if zero_index not in [2, 5, 8]:

     new_state = state.copy()

     new_state[zero_index], new_state[zero_index + 1] = new_state[zero_index + 1], new_state[zero_index]

     possible_moves.append((new_state, "Right"))

 if zero_index not in [6, 7, 8]:

     new_state = state.copy()

     new_state[zero_index], new_state[zero_index + 3] = new_state[zero_index + 3], new_state[zero_index]

     possible_moves.append((new_state, "Down"))

 return possible_moves

def manhattan_distance(state):

 distance = 0

 for i in range(1, 9):

     current_row, current_col = divmod(state.index(i), 3)

     target_row, target_col = divmod(i - 1, 3)

     distance += abs(current_row - target_row) + abs(current_col - target_col)

 return distance

def a_star(initial_state):

 open_list = [(manhattan_distance(initial_state), initial_state, [], [initial_state])]

 closed_set = set()



 while open_list:

     _, current_state, moves, states_sequence = heapq.heappop(open_list)

    

     if current_state == [1, 2, 3, 4, 5, 6, 7, 8, 0]:

         return current_state, moves, states_sequence

    

     closed_set.add(tuple(current_state))

    

     for next_state, move in get_possible_moves(current_state):

         if tuple(next_state) not in closed_set:

             priority = len(closed_set) + manhattan_distance(next_state)

             heapq.heappush(open_list, (priority, next_state, moves + [move], states_sequence + [next_state]))

Test the program

initial_state = [1, 2, 3, 4, 5, 6, 0, 7, 8]

solution, moves, states_sequence = a_star(initial_state)

if solution:

 print("Final solution:")

 for i in range(0, len(solution), 3):

     print(solution[i:i+3])

 print("Movements:")

 print(moves)

 print("Access sequence arrays:")

 for state in states_sequence:

     for i in range(0, len(state), 3):

         print(state[i:i+3])

     print()

else:

 print("There is no solution for this case")