LAB ASSIGNMENT FOR PROGRAMMING CLASS

CS 345: Spring, 2015 page 1 of 3 Lab 1: 16-Puzzle

CS 345: Spring, 2015 Lab 1 Due: 4/29/2015 For this lab, you will implement a state-space search that will find a solution to the sixteen- puzzle. For this program, in addition to the state-space search control, you will need to implement at least two other classes. One class will be a Queue class. This is not a difficult class to implement if you make use of the LinkedList collection class. For example, the add() method appends the parameter to the end of the list, and the remove() method removes and returns the object at the head of the list: hence you have a queue. There is also a size() method in the class, which makes it easy to implement an isEmpty() method for the Queue class. The second class will be a State class. As in the example, a state should consist of a one dimensional, 16 location, integer array and another integer variable that holds the index of the space. In addition, since we want to print out the moves that solve the problem, we need something to hold the moves thus far. A String will work quite well, since the moves can be represented by the letters “U”, “D”, “L”, “R”. As a move is made, just concatenate the appropriate letter to the end of the String. And, to read the moves for a solution, the charAt() method in the String class can get to individual letters. Your class should have accessor methods that return the current values of the array, the space variable and the moves variable, as well as a constructor that takes all three of these values. This will allow a new state to be created that is a clone of the parent state. Then there should be four methods that implement a move. When a move is implemented, the array and the value of the space index are changed and the appropriate letter is concatenated to end of the move list. In addition, there should be four boolean methods that test if a move can be applied to a state. The tests to see if a move applies to a state are given in the 16-puzzle example. However, there should be one other condition added to the tests. If, for example, I am checking to see if a Down rule applies to a state, a condition that must be true is that the space index is less than 12. In addition, the last move in the move list should not be a “U”. Why? Think of the 16-puzzle game: if you move a tile up, one move you can always make next is to move that tile down. But, this just brings you back to the previous situation and is a wasted move. So, a move, X, should not be applicable to a state if the last entry in the move list is the opposite of X. Does this condition make a difference? Well, I tried the basic rules without this condition on a puzzle that would take about 10 moves to solve. I also had the program keep track of the number of new states created and print out this number each time a new state was created. The program could not solve the puzzle because it ran out of heap space after creating almost 800,000 states. I then added this condition to the rules, and the program was able to solve the puzzle. It had made less than 5,000 new states by the time the puzzle was solved. Finally, there should be two other methods in the State class. One is a boolean method that tests is the state is a goal state or not. The other method should print the moves of the state.

CS 345: Spring, 2015 page 2 of 3 Lab 1: 16-Puzzle

The main program should have a means of taking a list of numbers and creating an initial state. For example, the list 4, 0, 2, 3, 5, 1, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 represents an initial state of:

4 2 3 5 1 6 7 8 9 10 11 12 13 14 15

As the initial state, the move list for this state should be the empty string. Once the initial state is created, it is placed into the queue. Then a loop, while the queue is not empty and the puzzle is not solved, is started. Within the loop, take a state out the queue and check if each of the four moves apply. If a move applies, create a new state that is a clone of the current state, apply the move to the new state, and check if the new state is the goal state. If it is the goal state, set a global state variable to this state and set the loop condition to solved. If it is not the goal state, add it to the queue. The loop should end for one of two reasons. If the queue is empty, then no solution is found. If the solution is found, then a global variable should have been set with the solution state. The moves of this state are then printed out. For example, in the puzzle above, three moves solve this puzzle. They are Down, Left, and Up (remember these moves apply to the space). For testing purposes, here are four more initial states along with the set of moves that solve the puzzle. Remember that the 0 represents the location of the space. 1. 4, 1, 2, 3, 5, 6, 10, 7, 8, 0, 9, 11, 12, 13, 14, 15. Solution: R, U, L, L, U 2. 1, 2, 6, 3, 4, 0, 10, 7, 8, 5, 9, 11, 12, 13, 14, 15. Solution: D, R, U, U, L, L 3. 4, 1, 2, 3, 8, 0, 5, 7, 9, 10, 6, 11, 12, 13, 14, 15. Solution: R, D, L, L, U, U 4. 1, 2, 6, 3, 4, 5, 0, 7, 12, 8, 10, 11, 13, 14, 9, 15. Solution: D, D, L, L, U, R, R, U, U, L, L Note, if you run out of heap space on number 4, you did not add the extra test mentioned above.

CS 345: Spring, 2015 page 3 of 3 Lab 1: 16-Puzzle

To Turn In Place your source code (Java files only please) in a zip or jar file named XXXL1, where XXX represents your initials. For example, Alan Mathison Turing would have named his lab AMTL1. E-mail this file to me. Be sure that each of your files contains a header with your name on it. In addition, you need to turn in a hard copy of the file. This lab is worth 40 points. As part of the grading for each lab, the following points will be awarded. 5 points: The archive file contains only source files, is emailed on time, and your name is

in a comment in the header. 5 points: A hard copy of your source files is handed in, and the name of the archive file is

contained in a comment in the header. 5 points: The source files have appropriate documentation (comments) and use a consistent

and readable programming style. 5 points: The source files compile and run under JDK 1.5 or higher. 10 points: The program has usable GUI interface. 10 points: The program correctly prints the rules to solve a puzzle. As a reminder, you are to do your own work. If I judge two or more programs to be essentially copies of each other, they will receive no credit.