Description
1. Solve the 5-queens problem (place 5 queens on a 5×5 board so that none is attacked) using DFStree search. The initial state is an empty board. Available actions at each state is to put a queen
at the left-most empty column (use only legal actions). (This is a similar setup to the 4-queens
problem we solved in class). Show the search tree.
For questions 2, 3, 4, 5, and 6, please use the following figure. We want to travel from S to G,
where some of the roads allow only one-way traffic. The distances between two locations are
given on the figure. The estimates, h, from a location to G are given on the side.
2. Hand-trace breadth-first tree search. What is the solution path found and what is its cost? Show
your work.
3. Hand trace uniform-cost graph search. What is the solution path found and what is its cost?
Show your work.
4. Hand trace greedy best-first tree search, where best is defined as the node that has the smallest
h(n). What is the solution path found and what is its cost? Show your work.
5. Hand trace A* tree search. What is the solution path found and what is its cost? Show your
work.
6. Come up with an admissible heuristic function h* that dominates every possible admissible
heuristic for this map; specify h*(n) for all n. Remember the definition of dominates: h1
dominates h2 if h1(n) h2(n) for all n.
