CIS 579 Machine Problem 2

Summer 2002

For your second assignment, you are to write a program that uses one of the branch and bound algorithms to solve a puzzle. My preference is that your program should use A* to solve the eight puzzle, but you may use any other branch and bound algorithm if you wish.

Your A* function should accept one argument which has as its value some representation of the initial state of the puzzle and returns the shortest sequence of moves required to solve the puzzle. One move consists of the movement of one tile, either horizontally or vertically, to an adjacent empty cell. The initial and final puzzle states are given below.

2 | 8 | 3 1 | 2 | 3

----------- -----------

1 | 6 | 4 8 | | 4

----------- -----------

7 | | 5 7 | 6 | 5

Initial Final

To use A* you need an estimate of the cost of traversing each path and an underestimate of the distance remaining to the goal state. For cost of path traversal, use the sum of the number of vertical and horizontal moves required to reach the state at the end of the path. For an underestimate of the remaining distance to the goal, use the number of misplaced tiles or some better measure of your own design (but you will need to justify that it is an underestimate).

You will need to devise an expand function that does not rely on hard coded problem state relations. You will also need to devise a data structure for the nodes in the problem state space

(an ordered list might be helpful, but a string or array might also work). It may also prove to be helpful to rethink the structure of the elements in the queue of partial paths (it may be wise to store the accumulated cost and the underestimate as part of the path stored in the queue).

You will need to turn in a well-commented program listing, sample runs (with neatly organized output), and a memo discussing your solution. In your memo you should describe your rationale for choosing the particular branch and bound algorithm variation that you did (including the operational definitions of your measures).

Assigned: 5/16/01

Due date: 5/30/01