Consider the $8-$puzzle problem. The start state and end stats are given in the following:

$\backslash$table$[[3,1,2],[4,,5],[6,7,8]]$

$\backslash$table$[[,1,2],[3,4,5],[6,7,8]]$

Start state

End state

Assume the evaluation function $f(n)=g(n)+h(n).$ Here, $g(n)=-2**d^2+3^{**}n+17,$ where $n$ is the node number, $d$ is the depth of the node $n$ and $h(n)$ is given in the following.

a$)$ If $h(n)=$ misplaced tiles, trace the operation of $A^{**}$ search. You have to calculate $f,g$ and $h$ for each node $n.(20$ points$)$

b$)$ If $h(n)=$ Manhattan distance, trace the operation of $A^{**}$ search. You have to calculate $f,g$ and $h$ for each node $n.(20$ points$)$