CIS 579 Machine Problem 2

Summer 2008

            For your second assignment, you are to write a program (using Lisp or some other language) that will allow you to examine the effectiveness of the A* search algorithm compared to that of ordinary branch and bound search. The problem to be solved is a simplified version of the Four Kights puzzle.

            The Four Knights puzzle is played on a 3 by 3 chess board. The opposing knights (black and white) start in the corners opposite each other as shown below. The object of this puzzle to have the opposing knights change sides of the 3 by 3 chess board. The knight are moved one at a time using the usual rule for movements (two squares forward in any direction followed by one square left or right.

Start:                                  End:

            To use A* you will 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 you may use path length. You are left to your own devices to design a measure that uses underestimates of the remaining distance to the goal.

            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. 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 discuss the relative effectiveness on A* to Branch & Bound using quantifiable language.

Assigned: 5/14/08

Due date: 6/02/08