|
|
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.
Can I assume that the puzzle inputs (arguments to the Board constructor) are valid? Yes, though it never hurts to include some basic error checking.
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 algs4.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()? Java has some arcane rules for implementing equals(), discussed on p. 271 of Algorithms, 4th edition. Note that the argument to equals() is required to be Object. You can also inspect Person.java for an online example.
How do I format strings so they align nicely? Use String.format(), which works like StdOut.printf(). See PhoneNumber.java for an online example.
Must I implement the toString() method for Board exactly as specified? Yes. Be sure to include the board dimension and use 0 for the blank square.
How should I implement the draw() method in Board? It is intended primarily for debugging. You should draw a graphical representation of the board, similar to the output of the toString() method. You can use StdDraw.text(x, y, s) (where s is a string that does not contain newlines) to draw the string s, centered on (x, y). You can also use StdDraw.setFont(new Font("SansSerif", Font.PLAIN, 24)); to change the font size.
I'm a bit confused about the purpose of the twin() method. You will use it to determine whether a puzzle is solvable: exactly one of a board and its twin are solvable. A twin is obatined by swapping two blocks (the blank does not count) in the same row. For example, here is a board and its 5 possible twins. Your solver will use only one twin.
1 3 3 1 1 3 1 3 1 3 1 3
4 2 5 4 2 5 2 4 5 4 5 2 4 2 5 4 2 5
7 8 6 7 8 6 7 8 6 7 8 6 8 7 6 7 6 8
board twin twin twin twin twin
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).
Can I terminate the search as soon as a goal state is enqueued (instead of dequeued)? No, even though it does lead to a correct solution for the slider puzzle problem using the Hamming and Manhattan priority functions, it's not techincally the A* algorithm (and will not find the correct solution for other problems and other priority functions).
I noticed that the priorities of the states dequeued from the priority queue never decrease. Is this a property of the A* algorithm? Yes. In the language of the A* algorithm, the Hamming and Manhattan distances (before adding in the number of moves so far) are known as heuristics. If a heuristic is both admissible (never overestimates the number of moves to the goal state) and consistent (satisfies a certain triangle inequality), then this property is guaranteed. The Hamming and Manhattan heuristics are both admissible and consistent. You may use this property as a debugging clue: if it is ever violated, then you know you did something wrong.
I run out of memory on much simpler puzzles than puzzle36.txt. How can I figure out what I am doing wrong? Note that for puzzle04.txt our reference solution enqueues 10 states before finding the solution. You should not enqueue many more than that for that puzzle.
I run out of memory when running some of the large sample puzzles. What should I do? Be sure to ask Java for additional memory, e.g., java -Xmx1600m Solver < puzzle36.txt. If your program is unable to solve certain instances, document that in your readme.txt file. You should expect to run out of memory when using the Hamming priority function.
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 puzzles. The shortest solution to puzzleT.txt requires exactly T moves. Warning: puzzle36.txt is especially difficult.
Testing. A good way to automatically run your program on our sample puzzles is to use the client Checker.java.
|
|
These are purely suggestions for how you might make progress. You do not have to follow these steps.
|
|
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.
What if I'm satisfied with any solution and don't need one that uses the fewest 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. This paper describes an algorithm that guarantees to perform at most N^3 moves.
Are ther better ways to solve 8- and 15-puzzle instances using the minimum number of moves? Yes, there are a number of approaches.
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