Assignment 1
(Due Thursday, April 10, 1:30pm)

Write a program that solves 8-puzzles.

Extra Credit: Write a program that solves 15-puzzles.

The input to your program will be an ascii file with the following format:

3
2
6
5
1
0
7
8
4

which indicates a puzzle with the initial state:

3 2 6
5 1 _
7 8 4 

The output of your program should be an ascii file that gives a sequence of moves (by indicating the number written on the piece moved, not the position the piece is moved from) that solve the puzzle as quickly as possible. A solved puzzle looks like this:

1 2 3
4 5 6
7 8 _

The sequence of moves for the given starting configuration might look like:

1
2
3
5
7
and so on.

We will test your program on a test suite of initial puzzle states.

I encourage you to work together on this assignment, and to try to find publicly available code on the net. If you submit such code or base your solution on other's code, make sure to clearly indicate this. There is no limit on how many people can work together as a group, but it is important that each member of the group participate fully.

Instructions on how to turn this in will be announced.

When you have done this assignment, you will have covered most of the intellectual content of AI. The rest is details (subtle details, but details nevertheless).

Relevant exercises in the book include exercises 4.9 and 4.17.