COS 226

8 Puzzle
Checklist

assignment

Frequently Asked Questions (General)

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 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 when computing either the Hamming or Manhattan priority functions.

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.

How can I align the integers in the toString() method? Yes. Be sure to include the board size and use 0 for the blank square. Use String.format() to format strings—it works like StdOut.printf(), but returns the string instead of printing it to standard output. For reference, our implementation is below.

public String toString() {
    StringBuilder s = new StringBuilder();
    s.append(n + "\n");
    for (int row = 0; row < n; row++) {
        for (int col = 0; col < n; col++) {
            s.append(String.format("%2d ", tileAt(row, col)));
        }
        s.append("\n");
    }
    return s.toString();
}

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. Recall that the blank square is not considered to be a tile. The priority function is implemented in Solver.

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, create a nested data type, 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 the Hamming and Manhattan priority functions, it’s not technically the A* algorithm (and will not find the correct solution for other problems and other priority functions).

The assignment says that the total number of moves we need to make (including those already made) is at least the priority of a search node. Why? For Hamming priority, this is true because each tile that is out of place must move at least once to reach its goal position. For Manhattan priority, this is true because each tile must move its Manhattan distance from its goal position. Note that we do not count the blank square when computing the Hamming or Manhattan priorities.

I noticed that the priorities of the search nodes 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 search node) 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.

Even with the critical optimization, the priority queue may contain two or more search nodes corresponding to the same board. Should I try to eliminate these? In principle, you could do so with a set data type such as SET in algs4.jar or java.util.TreeSet (provided that the Board data type were Comparable). However, almost all of the benefit from avoiding duplicate boards is already extracted from the critical optimization and the cost to identify other duplicate boards exceeds the benefit from doing so.

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 PuzzleChecker 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. Be sure not to put the JVM option in the wrong spot or it will be treated as a command-line argument, e.g., java-algs4 PuzzleChecker -Xmx1600m puzzle36.txt.

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 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. Also, be sure to execute from the command line (and not DrJava).

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.

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.