The sliding-tile puzzle consists of three black tiles, three white tiles, and an empty space in some order. The goal is to arrive at the goal configuration shown below by legal moves [B- Black tile, W-White tile].

B

B

B

W

W

W

The puzzle has two legal moves with associated costs Move #1: A tile may move into an adjacent empty location. This has a cost of 1. Move #2: A tile can hopover one or two other tiles into the empty position. This has a cost equal to the number of tiles jumped over (2-a) What are measures using which the complexity of a state space can be measured. List each of them and provide the corresponding expression / value for this problem. (2-b) Write down an admissible heuristic function h(n) for this problem with a formal description. Explain why this proposed heuristic is admissible. (2-c) Generate the A* search tree (using tree search) starting with the following start state for depth up to 3 or until the goal state is reached, whichever is earlier.

W

B

W

B

B

W

Annotate each node and edges with appropriate values f(n), h(n) and g(n) for better understanding. A search tree without such annotations will not get full credit here. (2-d) Argue formally the optimality of the solution obtained. (2-e) Will the solution obtained be different if the heuristic is also consistent in addition to being admissible. Why or why not?