## CPSC 453, Spring 2005 Assignment 3

Assignment 3 is a programming assignment based on Chapter 3. For this assignment, you should write a program that uses breadth-first search to find solutions to the Eight Puzzle. You can base your solution on either the Java version or the Lisp version of my solution to the missionaries and cannibals program. The basic outline of the program will be the same, but you have to change the problem formulation (the State and Action classes in the Java version).

This program is due on Friday, February 18. For the next programming assignment, I will ask you to modify your program to use a heuristic function and measure the effect that that has on the performance.

### About my Version of the Program

My program is based on the Java version of the missionaries and cannibals program. It generates a random initial state by starting from a solved board and working backwards by applying 50 randomly selected moves. This produces a puzzle that can definitely be solved in 50 moves or fewer. Most of the initial states generated in this way can be solved in much less than 50 moves. In fact, 20 moves is the longest example that I encountered.

In your program, you are not required to generate a board in the same way I do. You can just code the initial state into the program. But be sure that the initial state is one that has a solution. Here are some example initial states from my program, with data on how long it took to solve them (the 0 represents the blank square):

```        ---------
To find a solution for initial state

4 1 0
5 3 2
7 8 6

8 moves, 1/8 second compute time, fewer than 1000 visited states

----------
To find a solution for initial state

3 2 6
1 0 5
4 8 7

16 moves, 24 seconds compute time, 11000 visited states

----------
To find a solution for initial state

8 6 0
5 1 4
2 3 7

20 moves, 8 minutes compute time, 51000 visited states
```

### Sample Output from My Program

Here is some sample output from my version of the program. To let me know that it's still working, it prints out some information every time it encounters 1000 new states. When it finds a solution, it prints out the complete sequence of moves.

```       Start position:

4 8 2
7 3 6
5 1 0

1000 visited states; 374 states on fringe; working at depth 11
2000 visited states; 798 states on fringe; working at depth 13
3000 visited states; 1082 states on fringe; working at depth 14
4000 visited states; 1538 states on fringe; working at depth 14
5000 visited states; 1954 states on fringe; working at depth 15
6000 visited states; 2204 states on fringe; working at depth 15
7000 visited states; 2446 states on fringe; working at depth 15
8000 visited states; 2840 states on fringe; working at depth 16
9000 visited states; 3282 states on fringe; working at depth 16
10000 visited states; 3721 states on fringe; working at depth 16
11000 visited states; 4158 states on fringe; working at depth 16
12000 visited states; 4534 states on fringe; working at depth 17
13000 visited states; 4766 states on fringe; working at depth 17
14000 visited states; 4975 states on fringe; working at depth 17
15000 visited states; 5153 states on fringe; working at depth 17
16000 visited states; 5369 states on fringe; working at depth 17
17000 visited states; 5561 states on fringe; working at depth 17
18000 visited states; 5899 states on fringe; working at depth 18
19000 visited states; 6323 states on fringe; working at depth 18
20000 visited states; 6752 states on fringe; working at depth 18
21000 visited states; 7174 states on fringe; working at depth 18
22000 visited states; 7590 states on fringe; working at depth 18
23000 visited states; 8011 states on fringe; working at depth 18
24000 visited states; 8408 states on fringe; working at depth 18
25000 visited states; 8805 states on fringe; working at depth 18
26000 visited states; 9189 states on fringe; working at depth 18
27000 visited states; 9544 states on fringe; working at depth 19
28000 visited states; 9707 states on fringe; working at depth 19
29000 visited states; 9829 states on fringe; working at depth 19
30000 visited states; 9964 states on fringe; working at depth 19
31000 visited states; 10091 states on fringe; working at depth 19
32000 visited states; 10206 states on fringe; working at depth 19
33000 visited states; 10293 states on fringe; working at depth 19
34000 visited states; 10474 states on fringe; working at depth 19
35000 visited states; 10611 states on fringe; working at depth 19
36000 visited states; 10706 states on fringe; working at depth 19
37000 visited states; 10774 states on fringe; working at depth 19
38000 visited states; 10958 states on fringe; working at depth 20
39000 visited states; 11358 states on fringe; working at depth 20
40000 visited states; 11765 states on fringe; working at depth 20
41000 visited states; 12151 states on fringe; working at depth 20
42000 visited states; 12545 states on fringe; working at depth 20

The solution is:

0. Initial State --->
4 8 2
7 3 6
5 1 0

1. Blank square moves UP --->
4 8 2
7 3 0
5 1 6

2. Blank square moves LEFT --->
4 8 2
7 0 3
5 1 6

3. Blank square moves UP --->
4 0 2
7 8 3
5 1 6

4. Blank square moves LEFT --->
0 4 2
7 8 3
5 1 6

5. Blank square moves DOWN --->
7 4 2
0 8 3
5 1 6

6. Blank square moves RIGHT --->
7 4 2
8 0 3
5 1 6

7. Blank square moves DOWN --->
7 4 2
8 1 3
5 0 6

8. Blank square moves LEFT --->
7 4 2
8 1 3
0 5 6

9. Blank square moves UP --->
7 4 2
0 1 3
8 5 6

10. Blank square moves UP --->
0 4 2
7 1 3
8 5 6

11. Blank square moves RIGHT --->
4 0 2
7 1 3
8 5 6

12. Blank square moves DOWN --->
4 1 2
7 0 3
8 5 6

13. Blank square moves DOWN --->
4 1 2
7 5 3
8 0 6

14. Blank square moves LEFT --->
4 1 2
7 5 3
0 8 6

15. Blank square moves UP --->
4 1 2
0 5 3
7 8 6

16. Blank square moves UP --->
0 1 2
4 5 3
7 8 6

17. Blank square moves RIGHT --->
1 0 2
4 5 3
7 8 6

18. Blank square moves RIGHT --->
1 2 0
4 5 3
7 8 6

19. Blank square moves DOWN --->
1 2 3
4 5 0
7 8 6

20. Blank square moves DOWN --->
1 2 3
4 5 6
7 8 0
```