Program 3: The Eight Puzzle

Sample Solution and Test Data

• Mike Schuld's and Nick Coomb's eight.l solution.
• The file used to test the programs - test.l

Due Date

This assignment is due at the beginning of the lecture on Friday, November 9th.

Partners

Everyone is required to complete this assignment with one partner. Submit one solution with both of your names on it.

Purpose

The purpose of this assignment is to introduce you to the uninformed search technique, iterative deepening, in the context of solving the eight puzzle.

Coding Requirements

• The solution should appear in a file named eight.l.
• The solution should be able to integrate with a file such as analyze.l. Thus, you will need to have a main function named solve that is passed two arguments.
• The file analyze.l specifies the format of the eight puzzle. Your solve function may assume that the start state and the goal state are both legal configurations of the symbols 0, 1, 2, 3, 4, 5, 6, 7 and b.
• The problem must be solved using iterative deepening. Your iterative deepening solution is not allowed to keep track of states that have already been visited. Thus, your solution will visit some states more than once if it searches deeper than depth 1.

Sample Output

When the program is run by calling (test) in the analyze.l mentioned above, the output produced should be:

Start state: (0 1 2 3 4 5 6 B 7)
Goal state: (0 1 2 3 4 5 6 7 B)
Depth of nearest solution: 1

If I want to time your solution, I can modify the analyze.l file to call the solve function as follows: (time (solve start-state goal-state)). Sample output from this call might look like this:

Real time: 3.4E-5 sec.
Run time: 0.0 sec.
Space: 0 Bytes
Start state: (0 1 2 3 4 5 6 B 7)
Goal state: (0 1 2 3 4 5 6 7 B)
Depth of nearest solution: 1

The time of interest is the Run time as that measures the CPU time used. The Run time will typically be less than the Real time.

What to Submit

The following materials must be received no later than Friday, November 9th at 12:00 noon.

1. A printout (not an e-mail) of the eight.l file.
2. An e-mail of the eight.l file to John at paxton@cs.montana.edu

Grading

• 10%. The eight.l file compiles with no errors and no warnings. The solution is commented appropriately.
• 50%. Correctness. I will test your solution file on undisclosed sample test sets. Thus, it is very important that you anticipate and test your solution thoroughly before submitting it. Also, you will want to make extra sure that no run-time errors can occur.
• 20%. The quality of the solution. Does your solution use Common Lisp appropriately? Does the solution avoid duplicated code? Is the solution elegant? Is the solution easy to read and maintain? etc.
• 20%. Efficiency. I will test your compiled solution on eight puzzles that are 0, 1, 2, 3, ... n steps away from a solution. I will be interested in learning what the largest value of n is, for which the Run time is 10 seconds or less. The larger n is, the better!