Date: Mon, 02 Dec 1996 15:59:40 GMT Server: NCSA/1.4.2 Content-type: text/html CSE 473 Assignment 6

CSE 473 Assignment 6

Due Monday, May 13 in class.

Reading

In Chapter 7, read pages 329-347. In Chapter 8, read pages 375-394.

Part 1: Exercises

At the end of Chapter 7, do exercises 3, 5, 8, and 12.

At the end of Chapter 8, do exercises 1, 2, and 3.

Part 2: Mini-project (Continued)

Complete your Polyominoes/Pentominoes interactive puzzle solver.

Make up at least two different heuristics that can be used to prune or guide the search. Implement the A* algorithm using your heuristic(s), in such a way that the user gets to choose among the choices: no heuristics, heuristic number 1, heuristic number 2.

Make the user interface tidy and clear, but let the user feel in control to define not only the instance of the problem, but also the search strategy and the viewing policy (show every state, show every kth state, show only solution states, etc). It would be a good idea to display various items of information as the search progresses -- number of states on OPEN, on CLOSED, elapsed time, number of solutions found so far, f'(n) for the current state, etc.

There should also be an option for the user to stop the current search (and see the current state), resume the search, or cancel.

Use your own program to compare the heuristics you are using against each other and against the blind search with no heuristics. Do your heuristics work just as well for different values of N? For different shapes of boards? What are your results?


tanimoto@cs.washington.edu