Description
1. Consider the following initial and goal states for the 8-puzzle problem. In the search algorithms
below, when iterating over possible actions (i.e., moving the blank tile), always consider the
actions in the order: Up, Down, Left, Right. Be sure to use the search algorithms as defined in
the lecture notes.
a. Draw the search tree showing all nodes generated by the Breadth-First Search algorithm to
solve this problem.
b. Draw the search trees showing all nodes generated for each iteration of the IterativeDeepening Search algorithm to solve this problem.
c. Draw the search tree generated by the A* search algorithm to solve this problem using the
city-block distance for the heuristic h. The city-block distance for an 8-puzzle state is the
sum of the city-block distances of each tile in the puzzle (excluding the blank tile). Next to
every node, show the values of f, g and h. If two nodes have the same f value, then prefer
nodes farther to the left in the search tree.
d. Draw the search tree generated by the Hill-Climbing search algorithm to solve this
problem, where a state’s Value = 1 / (h + 1), where h is the heuristic from part (c). Next to
every node, show its Value. Finally, indicate which node is returned. Be careful; note that
the Hill-Climbing algorithm does not employ the goal test, but stops only after none of the
generated neighbor nodes has a strictly better Value.
2. Consider the heuristic which is the average of the city-block distances of each tile, instead of
the sum. Is this heuristic admissible for the 8-puzzle search problem? Justify your answer.
3. CPTS 540 Students Only: Suppose you want to replace the initial state in problem 1 with a
state such that the optimal solution to the 8-puzzle problem is exactly 10 moves. Explain how
you could use one of the search algorithms discussed in class to find such a state.
