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