The 8-Puzzle: Assignment

Warm up first, and then assignment.  Submit Assignment on Thursday 23rd December.

Warm-up

Go to Brian's 8-Puzzle Solver - launch the Java application and use this input: 3 2 0 8 7 4 5 1 6

Now ask the Solver to find a solution with "Number of paths to try" set at 100, and 1000, and 10000.

(Note that he uses A* as the name of his best-first algorithm.)

How many moves away is the final solution from the initial state?

How long was the time it took?

Use breadth-first search instead of A* (best-first) and see how many paths breadth-first needs before it finds the solution to the same puzzle.  Can it solve the puzzle within the 100,000 limit that the programmer has set?  How slow is it by comparison to best-first?

Try different inputs.  What is the worst number number of moves you have found?

Try the Enhanced A*.  See the author's notes as to why it is faster.

In Enhanced A*, what type of modifications to A* has Brian done: (choose one)
1- improved the heuristic evaluation function
2- improved the best-first search algorithm
3- improved the data structures

---

Assignment 1


For an 8-puzzle problem solver (assume that it uses depth-first search, but it doesn't matter), answer these questions:

1. What is the number of possible states of the board?
2. What is the average number of possible moves from a given position of the board?
3. Estimate how many moves might be required for an optimal (minimum number of moves) solution to a ``worst-case'' problem (maximum distance between starting and goal states). Explain how you made your estimate.
4. Assuming the answer to question #2 is the ``average branching factor'' and a depth as in the answer to question #3, estimate the number of nodes that would have to be examined to find an answer by brute force (blind) depth-first search.
5. Assuming that your computer can examine one move per microsecond, how long would such a blind-search solution to the problem require?
6. Should a depth-first search program for this problem check for duplicated states and consider a duplicated state to be a failure node? Calculate the effect such a test would have on the answers to questions #4 and #5.
7. The ``worst'' example problem given below is actually one of the easiest for humans to solve. Why do you think that is the case? What lessons for AI programs are suggested by this difference between human performance and performance of your search program?

Goal:        Easy:        Medium:        Hard:        Worst:

1 2 3        1 3 4        2 8 1          2 8 1        5 6 7
8   4        8 6 2          4 3          4 6 3        4   8
7 6 5        7   5        7 6 5            7 5        3 2 1

Taken from http://www.cs.utexas.edu/~novak/asg-8p.html