We have two Eight-Puzzle games; Game I and Game 2. Each game has its own initial state and goal state. We apply operators in the order: LEFT, UP, RIGHT, DOWN as we discussed in class. Apply A* algorithm to find a solution. We have g(n) function as the depth of node n in the search graph. As we discussed in class, we have two heuristic functions hi(n) and h2(n) as follows hl(n): total number of misplaced tiles h2(n): total Manhattan distance (Game 1) Initial state: Goal state: 8 1 2 6 5 4 5 x 2 (Game 2) Initial state: Goal state: For each game, first apply hI (n) to find a solution, second apply h2(n) to find a solution. (1) Write the states and operations as you generate states for each heuristic function. (2) Write the number of generated states for each heuristic function. (3) Compare two heuristic functions and explain which heuristic function is better than the other and why. (4) What is the solution? That is, write the sequence of operations to reach the goal state for each heuristic function