2048 Checklist
Can I use different class names, method names, or method signatures from those prescribed in the API? No, as usual, you will receive a serious deduction for violating the API.
How do I return an Iterable<Board>? Add the items you want to a Stack<Board> or Queue<Board> and return that. Of course, your client code should not depend on whether the Iterable returned is a Stack or a Queue (because it could be any Iterable).
Should I implement my own stack, queue, and priority queue? No, use the versions found in algs4.jar.
Is 0 a tile? No, 0 represents the absence of a tile. However, since we are multiplying, it is fine whether or not you consider it as a tile in distanceWeightedScore() and leftWeightedScore().
How can I align the integers in the toString() method? Be sure to use 0 for blank squares. Use String.format() to format Strings -- it works like StdOut.print(), but returns the String instead of printing it to standard output. You can use our reference implementation below, where n is the length of the Board.
public String toString() {
StringBuilder str = new StringBuilder();
str.append(n);
str.append("\n");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
String temp = String.format("%5d", tileAt(i, j));
str.append(temp);
}
str.append("\n");
}
return str.toString();
}
Can I assume that the board inputs (arguments to the Board constructor and input to Solver are valid?) Yes, although it never hurts to include some basic error checking.
How do I create a MaxPQ<Board>?You can't, because Board is not Comparable. Instead, create a nested data type, say SearchNode, that represents a search node and can be compared to other search nodes according to the Weighted score priority function.
How do I reconstruct the solution once I've dequeued the goal search node? Since each search node records the previous search node used to get there, you can chase the pointers all the way back to the initial search node (and consider them in reverse order).
Can I terminate the search as soon as a goal search node is enqueued (instead of dequeued)? No, even though it does lead to a correct solution for the problem using the priority functions, it’s not technically the A* algorithm (and will not find the correct solution for other problems and other priority functions).
Why does my Solver find a different number of moves compared to a friend's Solver even though neither of us are finding mistakes? It is possible that people with different correct code could have a different number of moves, although this will mostly happen only on initial boards further away from the goal and the difference in moves will generally be within 5% of the total number of moves required to reach the goal.
I noticed that my solution sometimes overestimates the number of moves. Is this a problem? No. In the language of the A* algorithm, the priority functions are known as heuristics. Neither heuristic is admissible (never overestimates the number of moves to the goal search node). Therefore the priorities of the search nodes dequeued from the priority queue can decrease.
My program is too slow to solve some of the large sample puzzles, even if given a huge amount of memory. Is this okay? You will not necessarily be able to solve 2048 with the distance weighted score priority function within a reasonable time, but left weighted score should be able to successfully reach the 2048 tile. Also, be sure to execute from the command line (and not your IDE).
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-algs4 -Xmx1600m BoardChecker 2048 Board1.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 distance priority function.
Input files. The zip file 2048.zip contains many sample input Boards.
Testing. A good way to automatically run your program on our sample puzzles is to use the client BoardChecker.java.
Visualization client. SolverVisualizer.java. takes the name of a puzzle file as a command-line argument and animates the solution.
Sample trace. The program defines two different data structures on the set of search nodes—the game tree and the priority queue. We plan to provide a detailed trace of each data structure during the solution to ?
Can a puzzle have more than one solution? Yes. And some solutions will be shorter than others.
How can I reduce the amount of memory a Board uses?
For starters, recall that an n-by-n int[][] array in Java uses
about 24 + 32n + 4n2 bytes; when n equals 4,
this is 216 bytes.
To save memory, consider using a 1D array of length n2.
If you limit the goal size then you can use fewer bits to represent each integer.
Are there better ways to find the solution to 2048? Yes, you can come up with a better priority function. One idea is to allow for more moves while reducing the overall time. Another is to attempt to reduce the number of moves allowed.