Heuristic Search.

Exercise 5: The sliding-tile puzzle. Read the description of the puzzle on page 162. Then do a-c below (and don't do a-c in the book).

a) Analyze the state space with respect to its complexity. (See section 4.5 of the text.) How many states does it have? What is the average branching factor? Assuming that the solution path contains 10 moves, calculate an estimate of the search cost (See section 4.5). Hint: To determine how many states there are, you might reformulate the question into how many ways can you arrange 3b's and 3w's in the puzzle? To calculate branching factor, you should note that not all states are different. For example, you might divide the states into "kinds" based on where the blank occurs and determine how many branches there are for each of these kinds.

b) Does this state space contain loops? Explain in a sentence.

c) Let h(n) be the following heuristic: h(n) = the number of tiles that would have to be moved (by any number of spaces) to achieve a goal state. For example, if we let x stand for the blank space, and b and w stand for the black and white tiles, and if we assume that a goal state is any state in which all of the white tiles are to the left of all of the black tiles -- e.g., wwwxbbb, wwxwbbb, xwwwbbb, and so on.

	h(bbbxwww) = 6, since 3 blacks and 3 whites must be moved to
			achieve the goal state
	h(bbxbwww) = 5, since 1 b could remain where it is in the goal
			state
	h(wwxbbwb) = 1, since only 1 w needs to be moved
	h(wwwxbbb) = 0, since this is the goal state