points$)$

Apply the $A^{**}$ algorithm to determine the moves that will take the knight to one of the goal positions specified on the board. The search will terminate whenever the knight reaches to any goal position. Use the Manhattan distance between then knight and the closest goal state on the board. For instance, the heuristic function will return $3$ for the configuration on the board.

a$)$ Draw the search tree that will be generated by $A^{**}$ search. b$)$ Have you found the the optimal solution? Why? Why not?