Date: Mon, 02 Dec 1996 15:59:51 GMT
Server: NCSA/1.4.2
Content-type: text/html
CSE 473 Assignment 5
CSE 473 Assignment 5
Due Monday, April 29 in class.
NOTE: SEE APRIL 26 ANNOUNCEMENT ON HOME PAGE FOR MORE INFO ON WHAT TO TURN IN MONDAY.
Reading
In Chapter 5, read pages 241-250.
In Chapter 6, read pages 271-302.
Part 1: Exercises
At the end of Chapter 6, do exercises 1, 2, 13, and 15.
Part 2: Mini-project
There is a class of puzzles known as pentominoes puzzles that involve
placing pieces (called pentominoes, naturally) into trays of various shapes in
order to fill them without any gaps or overlaps. Each pentomino is
made up of 5 squares attached at their sides. There are 12 distinct
shapes, not counting rotated or flipped versions of these.
The classical pentominoes puzzle is to fill a 6 by 10 rectangle
using each of the 12 pieces exactly once.
In general, pentominoes are the N=5 case of "polyominoes", where
N = 1, N = 2, etc.
- Design a representation for states of a polyominoes puzzle,
where N can easily be changed by the programmer (i.e., N is a
parameter).
- Create a search program that solves polyomino problems, where
the user gets to give the shape of the empty tray to be filled,
together with a list of polyominoes to be used in filling the
tray. You may assume that all polyominoes in a given run have
the same number of squares. However, do not assume that they
necessarily have either the same or different shapes.
- For a reasonably-sized board, how large a value of
N can your program handle in a reasonable
amount of time?
- Create a user interface for your program, so that
a state is shown graphically on the screen, and so the user
can get an idea of how the search is progressing by looking
at some statistics that are updated in real-time on the screen.
- (Optional) Make up one or more heuristics that can be used
to prune or guide the search. Implement the A* algorithm using
your heuristic(s).
tanimoto@cs.washington.edu