|
|
Can I use different class names, method names, or method signatures from those proscribed in the API? No. This will incur a serious deduction (10 points).
Do I have to implement my own priority queue? No. Use MinPQ or MaxPQ.
How can I access Stack, Queue, MinPQ and MaxPQ? You can either download individually or download adt.jar and add it to your classpath.
How do I return an Iterable<Board>? Add the elements you want to a Stack or Queue and return that.
How do I implement equals()? See the PhoneNumber.java example from the elementary symbol table lecture.
How do I print out solution once I've dequeued the goal state? Since each state records the previous state to get there, you can chase the pointers all the way back to the initial state (and print them in reverse order).
Will the total number of states be enqueued be the same for everyone in the class? Not necessarily. When you remove the minimum key from the priority queue, there might be several with the same priority. So your implementation might choose a different one, depending on the order in which you enqueue neighboring states.
How do I create a board from the input format? Feel free to use the following.
int N = StdIn.readInt();
int[][] tiles = new int[N][N];
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
tiles[i][j] = StdIn.readInt();
Board board = new Board(tiles);
I run out of memory of some of the large instances. What should I do? Be sure to ask Java for additional memory, e.g., java -Xmx1600m Solver < ftp/puzzle36.txt. If your program is unable to solve certain instances, just document that in your readme.txt file.
|
|
Input. The ftp directory contains many sample input files. The shortest solution to puzzlex.txt requires exactly x moves. Warning: puzzle36.txt is especially difficult.
Testing. A good way to automatically run your program on our test inputs is to use Checker.java.
Readme. Use the following readme file template and answer all questions.
|
|
These are purely suggestions for how you might make progress. You do not have to follow these steps.
|
|
Is there a faster way to find solutions to random 4-by-4 puzzles that don't necessarily use the minimum number of moves? Yes, change the priority function to put more weight on the Manhattan distance, e.g., 100 times the Manhattan distance plus the number of moves made already.
What if I want to solve random 4-by-4 puzzles in the minimum number of moves? Use the A* algorithm but with a better priority function. One approach is to use a pattern database. For each possible configuration of 4 tiles and the blank, determine the minimum number of moves to put just these tiles in their proper position and store these values in a database. The heuristic value is the maximum over all configurations, plus the number of moves made so far. This can reduce the number of states examined for random 15-puzzle instances by a factor of 1000.
Can a puzzle have more than one shortest solution? Yes. See puzzle07.txt.
Solution 1
------------------------------------------------------------------------------------
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3
7 6 7 6 7 4 6 7 4 6 4 6 4 6 4 5 6 4 5 6
5 4 8 5 4 8 5 8 5 8 7 5 8 7 5 8 7 8 7 8
Solution 2
------------------------------------------------------------------------------------
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3
7 6 5 7 6 5 7 6 5 6 5 6 4 5 6 4 5 6 4 5 6
5 4 8 4 8 4 8 4 7 8 4 7 8 7 8 7 8 7 8