Question $4$ In this question, you will be asked to prove and design admissible and mono$-$

tonic $($consistent$)$ heuristics for varying problems.

$($a$)$ An example of an $8-$puzzle is given in the figure below. The goal is to

move the tiles one at a time until the goal is reached, in which the tiles are

ordered. Given a state $n,$ prove that the following heuristic for the $8-$puzzle

is admissible:

$h(n)={\displaystyle \underset{i=1}{\overset{8}{}}}$Manh$(T_{i,n},T_{i,g})$

where $T_{i,n}$ is position of tile $i$ in state $n,T_{i,g}$ is the position of tile $i$ in the

goal state, and Manh$(T_{i,n},T_{i,g})$ is the Manhattan Distance between tiles

$T_{i,n}$ and $T_{i,g}.$