Project 1
Fall 1998
Due: October 8
5 points
Consider the 8-puzzle problem, a variant of the 15-puzzle problem. There are eight numbered, movable tiles arranged in a 3 x 3 grid with one empty grid position. The empty position lets us rearrange one of the adjacent tiles. The goal is to move the tiles so they are ordered consecutively, as pictured below:
Determine a suitable representation for the 8-puzzle problem and develop a heuristic evaluation function to judge the ``goodness'' of a state, or board configuration. Select an appropriate search algorithm and, using the programming language of your choice, write a program that randomly generates an initial board configuration and heuristically searchs the state space using generate and test until it reaches the goal state.
After experimenting with the program, write a brief report (one page is sufficient) describing the implementation, successes or failures, the possible reasons for any failures, and ways in which to improve the program to remedy these problems.
As I said in class, you may, if desired, work in groups of two.
Turn in a copy of your code, two sample runs, and the brief report by the start of class on the due date. This can be a hard copy or an electronic copy submitted on a disk or via email (maloof@cs).