3) Consider a 9x9 game board, with 10 identical pieces, as shown below. Pieces can move in two different ways: move to an empty adjacent square in the 4 cardinal directions (up, left, right, down), or jump over an adjacent piece (up, left, right, down) to the square directly opposite of that piece (assuming that square was empty). The goal is to move all of your pieces from one corner to the other corner, using as few moves as possible.

1. Describe a state space for this puzzle. How many states are there? If necessary, give an upper bound.
2. What is the branching factor for this problem? Give the maximum branching for any state and explain your solution.
3. Give an upper bound (as tight as possible) for the number of moves in the optimal solution path. Explain your solution.
4. Identify a suitable uninformed search algorithm for this task and justify your choice based on the properties of the problem domain.
5. Assume the operators have unit cost. Which of the following possible heuristics are admissible (yes or no) and justify your answer.

   i) h(n) = 0 ii) h(n) = # pieces on cells in the goal zone (lower right corner).

6. 3. h(n) = _i h_i(n), where h_i(n) = Manhattan distance between a piece is current position to the closest cell in the goal zone.
   4. h(n) = maxi {h_i}, where h_i is defined as in (iii) above. Now consider the case where moves to an adjacent cell are half the cost of jumping over another piece (i.e. moving costs 0.5, jumping costs 1). For each of the heuristics in (e), say under what conditions it is admissible and justify your answer.

o o 0 oo olololo O 0 0 (i) Start configuration (ii) goal configuration (iii) Example move o o 0 oo olololo O 0 0 (i) Start configuration (ii) goal configuration (iii) Example move