To implement the A$*$ algorithm to solve the $8-$puzzle problems $($i$.$e$.$ find the goal$).$

$8-$Puzzle Problem:

$8-$puzzle is a problem where you have total $9$ blocks as shown in the figure below. $8-$blocks$/$cells are

marked with a number from $1$ to $8$ and one cell is blank$/$empty$,$ the goal is to organize numbered

block in clockwise in an ascending order $($shown in the final state$).$

Given an initial state and final state below. Write an A$*$ algorithm to solve the following $8-$puzzle

problem. You$$re A$*$ algorithm should create all intermediate states until it reaches the final states.

Your code should be executable and print all the states while executing. Examples of such A$*$

algorithm is shown below.

The program is to start from an initial configuration to find the goal configuration. A solution to the

problem is an appropriate sequence of moves, such as $$move tiles $5$ to the right, move tile $7$ to the left,

move tile $6$ to the down, etc$.$ You should always start with an initial random state $($do not hard$-$coded

in your program$).$ Your program should be able to deal with any initial configuration.

Your A$*$ algorithm uses following cost function:

f$($n$)=$ g$($n$)+$ h$($n$)$

f$($n$)=$ estimated cost of the cheapest solution through n

g$($n$)=$ the cost to reach the node $($from the start$)$

h$($n$)=$ the Manhattan Distance of each tile from its proper position

Send a code in python language