|
|
Can I use different class names, method names, or method signatures from those proscribed in the API? No, as usual, anything violating the API 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 and look at their API specifications or download adt.jar and add it to your classpath.
How do I return an Iterable<Board>? Add the items you want to a Stack<Board> or Queue<Board> and return that.
How do I implement equals()? How do I format strings so they align nicely? See the PhoneNumber.java example.
How do I reconstruct the 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 consider them in reverse order).
I run out of memory when running some of the large sample files. 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 files. 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.
|
|
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 an 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.