Given a puzzle state like the one above, where the numbers are in the wrong places, we want

to search for a series of moves that ends in the solution below. The number of moves required

could be calculated as a path cost.

Start State

Goal State

$($i$)$ Write down a heuristic function, $h,$ for this game $($remember that this estimates the path

cost from a particular state to the solution$).$

$[2$ Marks$]$

$($ii$)$ What is the value of $h$ for the above board state?

$[1$ Marks$]$

$($iii$)$In a greedy search, what move would be chosen next? $($i$.$e$.,$ move the $3,$ the $4$ or the $6$

into the gap?$)$

$[2$ Marks$]$

$($iv$)$Is this heuristic admissible?

$[2$ Marks$]$

$($v$)$ Can you suggest a better heuristic measure?

$[2$ Marks$]$