You will implement a state-space search that will find a solution to the sixteenpuzzle. 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??*?t 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.
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.