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