Frequently Asked Questions (General)

How do I return an Iterable<Board>? Add the items you want to a Stack<Board> or Queue<Board> and return that. For example, see the keys() method in ArrayST.java. The client should not depend on whether the iterable returned is a stack or queue (because it could be any iterable).

Should I implement my own stack, queue, and priority queue? No, use the versions in algs4.jar.

Frequently Asked Questions (Board)

Is 0 a tile? No, 0 represents the absence of a tile. Do not treat it as a tile in either hamming() or manhattan().

Should the hamming() and manhattan() methods return the Hamming and Manhattan priority functions? No, they should return the Hamming and Manhattan distances between the board and the goal board. The priority function is implemented in Solver.

How do I implement equals()? Java has some arcane rules for implementing equals(), discussed on p. 103 of Algorithms, 4th edition. Note that the argument to equals() is required to be of type Object. For online examples, see Date.java or Transaction.java.

Can I use the expression a == b to check whether two arrays a and b are equal? No. That expression checks the two arrays for reference equality (and not whether the two arrays contain the same sequence of values).

Can I call Arrays.equals(a, b) to check whether two arrays a and b are equal? It depends. If a and b are of type int[], then Arrays.equals() works as expected. If a and b are of type int[][], then use Arrays.deepEquals().

Can I call Arrays.copyOf() to create an independent copy of an array a? It depends. If a is of type int[], then either Arrays.copyOf() or a.clone() will get the job done. However, if a is of type int[][], then Arrays.copy() will not produce an independent copy because it performs a shallow copy. Instead, you can write a double nested loop to copy the entries in a two-dimensional array.

How can I align the integers in the toString() method? Use String.format() to format strings—it works like StdOut.printf().

String.format("%2d ", tileAt(row, col));

Why does the autograder complain that my toString() method uses string concatenation in a loop? String concatenation takes time proportional to the length of the resulting string (because it has to create a new character array to store the resulting string). Instead, use StringBuilder, which takes constant amortized time to append a character (because it uses a resizing character array to represent the underlying string).
// takes Theta(n^2) time
int n = s.length();
String reverse = "";
for (int i = n-1; i >= 0;; i--)
    reverse += s.charAt(i);

// takes Theta(n) time
int n = s.length();
StringBuilder sb = new StringBuilder();
for (int i = n-1; i >= 0;; i--)
    sb.append(s.charAt(i));
String reverse = sb.toString();

Frequently Asked Questions (Solver)

Can I assume that the puzzle inputs (arguments to the Board constructor and input to Solver) are valid? Yes, though it never hurts to include some basic error checking.

How do I create a MinPQ<Board>? You can’t because Board is not comparable. Instead, define a nested class, say SearchNode, that represents a search node and can be compared to other search nodes according to the Manhattan 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 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 slider puzzle problem (using either the Hamming or Manhattan priority functions), it’s not technically the A* algorithm (and will not find the correct solution for other problems and other priority functions).

I'm getting the right number of moves for puzzle04.txt but the wrong number of moves for some other puzzles. How might I identify what is going wrong? Check the detailed trace for puzzle04.txt in the testing section. Even if your program returns the correct number of moves for this puzzle, the trace might reveal that you are adding/removing boards in the wrong 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., with

java-algs4 -Xmx1600m PuzzleChecker puzzle36.txt
Do not put the JVM option after the name of the class or it will be treated as a command-line argument.

Even after giving my program more memory, it is too slow to solve some of the large sample puzzles. Is this OK? You should not expect to solve many of the larger puzzles with the Hamming priority function. However, you should be able to solve most (but not all) of the larger puzzles with the Manhattan priority function.

Testing

Input files.   The zip file 8puzzle.zip contains many sample puzzles. The shortest solution to puzzle4x4-hard1.txt and puzzle4x4-hard2.txt are 38 and 47, respectively. The shortest solution to puzzle*[T].txt requires exactly T moves. Warning: puzzle36.txt, puzzle47.txt, and puzzle49.txt, and puzzle50.txt are relatively difficult.

Testing. A good way to automatically run your program on our sample puzzles is to use the client PuzzleChecker.java.

Visualization client. You can also use SolverVisualizer.java, which 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. Below is a detailed trace of each data structure during the solution to puzzle04.txt. This trace is useful not only for testing correctness, but also for identifying memory and timing bugs.

For brevity, we assign each search node a single-letter ID. The following table provides the relevant information for each search node (the ID, the board, its Manhattan distance from the goal board, the number of moves to reach the search node, the Manhattan priority function, and the previous search node).

ID  Board   Priority function     Parent in game tree
================================================================================

A   0 1 3   Manhattan:        4   Previous: null
    4 2 5   Moves:            0
    7 8 6   Priority: 4 + 0 = 4

B   1 0 3   Manhattan:        3   Previous: A
    4 2 5   Moves:            1
    7 8 6   Priority: 3 + 1 = 4

C   4 1 3   Manhattan:        5   Previous: A
    0 2 5   Moves:            1
    7 8 6   Priority: 5 + 1 = 6

d   0 1 3   Manhattan:        4   Previous: B
    4 2 5   Moves:            2
    7 8 6   Priority: 4 + 2 = 6

E   1 2 3   Manhattan:        2   Previous: B
    4 0 5   Moves:            2
    7 8 6   Priority: 2 + 2 = 4

F   1 3 0   Manhattan:        4   Previous: B
    4 2 5   Moves:            2
    7 8 6   Priority: 4 + 2 = 6

g   1 0 3   Manhattan:        3   Previous: E
    4 2 5   Moves:            3
    7 8 6   Priority: 3 + 3 = 6

H   1 2 3   Manhattan:        3   Previous: E
    0 4 5   Moves:            3
    7 8 6   Priority: 3 + 3 = 6

I   1 2 3   Manhattan:        3   Previous: E
    4 8 5   Moves:            3
    7 0 6   Priority: 3 + 3 = 6

J   1 2 3   Manhattan:        1   Previous: E
    4 5 0   Moves:            3
    7 8 6   Priority  1 + 3 = 4

K   1 2 0   Manhattan:        2   Previous: J
    4 5 3   Moves             4
    7 8 6   Priority  2 + 4 = 6

l   1 2 3   Manhattan:        2   Previous: J
    4 0 5   Moves:            4
    7 8 6   Priority: 2 + 4 = 6

M   1 2 3   Manhattan:        0   Previous: J
    4 5 6   Moves:            4
    7 8 0   Priority: 0 + 4 = 4



################################################################################
Step 0
================================================================================

Game Tree
--------------------------------------------------------------------------------

                                      A

Priority Queue
--------------------------------------------------------------------------------

pq = new MinPQ();   0 1 2 3 4 5 6 7 8 9
                    - - - - - - - - - -

pq.insert(A);       0 1 2 3 4 5 6 7 8 9
                    - A - - - - - - - -



################################################################################

Step 1
================================================================================

Game Tree
--------------------------------------------------------------------------------

                                      A
                                      |
                                     ---
                                    /   \
                                  B       C

Priority Queue
--------------------------------------------------------------------------------

pq.delMin();        0 1 2 3 4 5 6 7 8 9
// returns A        - - - - - - - - - -

pq.insert(B);       0 1 2 3 4 5 6 7 8 9
                    - B - - - - - - - -

pq.insert(C);       0 1 2 3 4 5 6 7 8 9
                    - B C - - - - - - -



################################################################################

Step 2
================================================================================

Game Tree
--------------------------------------------------------------------------------

                                      A
                                      |
                                     ---
                                    /   \
                                  B       C
                                  |
                                 ---
                                / | \
                              d   E   F

Priority Queue
--------------------------------------------------------------------------------

pq.delMin();        0 1 2 3 4 5 6 7 8 9
// returns B        - C - - - - - - - -

pq.insert(E);       0 1 2 3 4 5 6 7 8 9
                    - E C - - - - - - -

pq.insert(F);       0 1 2 3 4 5 6 7 8 9
                    - E C F - - - - - -



################################################################################

Step 3
================================================================================

Game Tree
--------------------------------------------------------------------------------

                                      A
                                      |
                                     ---
                                    /   \
                                  B       C
                                  |
                                 ---
                                / | \
                              d   E   F
                                  |
                               -------
                              / |   | \
                             g  H   I  J

Priority Queue
--------------------------------------------------------------------------------

pq.delMin();        0 1 2 3 4 5 6 7 8 9
// returns E        - F C - - - - - - -

pq.insert(H);       0 1 2 3 4 5 6 7 8 9
                    - F C H - - - - - -

pq.insert(I);       0 1 2 3 4 5 6 7 8 9
                    - F C H I - - - - -

pq.insert(J);       0 1 2 3 4 5 6 7 8 9
                    - J F H I C - - - -



################################################################################

Step 4
================================================================================

Game Tree
--------------------------------------------------------------------------------

                                      A
                                      |
                                     ---
                                    /   \
                                  B       C
                                  |
                                 ---
                                / | \
                              d   E   F
                                  |
                               -------
                              / |   | \
                             g  H   I  J
                                       |
                                      ---
                                     / | \
                                   K   l  [M]

Priority Queue
--------------------------------------------------------------------------------

pq.delMin();        0 1 2 3 4 5 6 7 8 9
// returns J        - C F H I - - - - -

pq.insert(K);       0 1 2 3 4 5 6 7 8 9
                    - C F H I K - - - -

pq.insert(M);       0 1 2 3 4 5 6 7 8 9
                    - M F C I K H - - -



################################################################################

Step 5
================================================================================

Game Tree
--------------------------------------------------------------------------------

                                      A
                                      |
                                     ---
                                    /   \
                                  B       C
                                  |
                                 ---
                                / | \
                              d   E   F
                                  |
                               -------
                              / |   | \
                             g  H   I  J
                                       |
                                      ---
                                     / | \
                                   K   l  [M]

Priority Queue
--------------------------------------------------------------------------------

pq.delMin();        0 1 2 3 4 5 6 7 8 9
// returns M        - H F C I K - - - -

M corresponds to a goal state, return path from root to leaf: A -> B -> E -> J -> M

Possible Progress Steps

These are purely suggestions for how you might make progress. You do not have to follow these steps.