$(1).$ We have Eight$-$Puzzle game. We have four operations of moving blank as discussed in

class. We apply operators in the order: LEFT, UP$,$ RIGHT, DOWN. Apply A$*$ algorithm to find

a solution.

Initial state:

Goal state:

We have

$g(n)$ : the depth of node $n$ in the search graph, and

h$1($n$)$: total number of misplaced tiles.

$(1-1)$ You need to show the process of each action step by step. Write the states and operations

as you generate states during this search. You need to construct the search tree for each

selection with $f(n)$ value.

$(1-2)$ How many states are generated $($including repeated states$)?$

$(1-3)$ What is the solution? That is$,$ write the sequence of operations to reach the goal state from

the initial state.

$(2).$ We have Eight$-$Puzzle game. We have four operations of moving blank as discussed in

class. We apply operators in the order: LEFT, UP$,$ RIGHT, DOWN as we discussed in class.

Apply A$*$ algorithm to find a solution.

Initial state:

Goal state:

We have

$g(n)$ : the depth of node $n$ in the search graph, and

h$2($n$)$: total Manhattan distance

$(2-1)$ You need to show the process of each action step by step. Write the states and operations

as you generate states during this search. You need to construct the search tree for each

selection with $f(n)$ value.

$(2-2)$ How many states are generated $($including repeated states$)?$

$(2-3)$ What is the solution? That is$,$ write the sequence of operations to reach the goal state from

the initial state.

$(3)$ Compare two heuristic functions above, h$1($n$)$ and h$2($n$),$ and explain which heuristic

function is better than the other and why.