|
|
Can I use different class names, method names, or method signatures from those proscribed in the API? No. This will incur a serious deduction.
Do I have to implement my own stack, queue, and priority queue? No. Use the versions from lecture. You can either download them 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<Board> or Queue<Board> and return that.
How do I implement equals()? See the PhoneNumber.java example from the elementary symbol table lecture. Be careful to get it right.
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. The one that is removed depends 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, document that in your readme.txt file.
My program can't solve puzzle4x4-hard1.txt, even if I give it a huge amount of space. What am I doing wrong? Probably nothing. The A* algorithm will struggle to solve even some 4-by-4 instances.
|
|
Input. The ftp directory contains many sample input files. The shortest solution to puzzleN.txt requires exactly N 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
Is there an efficient way to solve the 8-puzzle and its generalizations? Finding a shortest solution to a slider puzzle is NP-hard, so it's unlikely that aan efficient solution exists.
Are there better algorithms for solving the 15-puzzle? This paper uses a variation of the A* algorithm known as IDA* (for iterative deepening).
What if I don't care about finding the shortest solution? In this case, there are efficient algorithms. This paper describes an algorithm that performs N^3 moves.