|
|
Can I use different class names, method names, or method signatures from those prescribed 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 implmenting equals(), discussed on p. 271 of Algorithms, 4th edition. Note that the argument to equals() is required to be Object. You can also inspect PhoneNumber.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) 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 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 twins.
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).
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 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). Another idea is to use bidirectional search, where you simultaneously search from the initial board to find the goal board and from the goal board to find the initial board, and have the two search trees meet in the middle. Handling the stopping condition is delicate.
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.