1. Draw the search tree that is generated by a breadth-first search in an attempt to solve the eight-puzzle from the following start state without using the assistance of any heuristic information.

_	1	3
4	2	5
7	8	6

_13

425

786

2. Draw the search tree that is generated by the algorithm of an attempt to solve the eight-puzzle from the start state if the number of tiles out of place is used as a heuristic [the first heuristic]

3. Draw the search tree that is generated by the algorithm of an attempt to solve the eight-puzzle from the following start state, assuming the heuristic used is the same as that developed in [the second heuristic]

1	2	3
5	7	6
4	_	8

123

576

4_8

4. When solving the eight-puzzle, why would the number of tiles out of place [the first heuristic] not be as good a heuristic as the one used in [the second heuristic]?