Question $4$

For the $9-$tile scoring problem, assume that you start from this initial state

$724$

$56$ #

$831$

Final state

$123$

$456$

$78$ #

The cost of moving any tile is $1.$

Let the heuristic function h$($n$)=$ number of misplaced tiles.

For the shown configuration, there are four options for the next move:

Move $5$ to the right

Move $6$ to the left

Move $2$ down

Move $3$ up

Each of these moves has a value f$($n$)=$ h$($n$)+$ g$($n$).$

If we choose to Move $5$ to the right, then

g$($n$)=1.$ That is$,$ it took us one step to reach this state from the initial state.

h$($n$)=$ number of misplaced tiles. The misplaced tiles are $\{7,4,8,3,1\}.$ So the number of misplaced tiles $=$ h$($n$)=5.$

If we choose to Move $6$ to the left, g$($n$)$ is still $=1,$ but h$($n$)$ will change because the number of misplaced tiles is different.

A$*$ works by computing f$($n$)=$ h$($n$)+$ g$($n$)$ for each of these possible moves. Then it chooses the move with the lowest f$($n$).$

Apply A$*$ to generate $3$ states starting at the initial state above. That is$,$ show the next three moves that will be chosen by A$*.$ Show your calculations to compute g$($n$),$ h$($n$)$ and f$($n$)$ for all the possible moves $($states$).$