Slider Puzzle

• Checklist
• Project
• Submit
• Leaderboard

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.

What is meant by an immutable data type? An object is immutable if its data-type value (state) never changes once it is constructed. A data type is immutable if every object of that type is immutable. For example, to make the Board data type immutable, you must make a defensive copy of the tiles[][] array in the constructor (because the client might change one of the entries in the original tiles[][] array after constructing the Board object).

Can my methods have side effects that are not described in the API? No. For example, calling board.neighbors() must not rearrange the tiles in board (or it could have a serious side effect on the client). We usually allow methods to have benign side effects, such as changing the state of a random number generator.

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 wrong number of moves for puzzle04.txt. How might I identify what is going wrong? Check the detailed trace for puzzle04.txt in the testing section.

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 umber of moves for this puzzle, the trace might reveal that you are adding/removing boards in the wrong order.

I'm getting the right number of moves for puzzle04.txt and other puzzles but my program takes too long or runs out of memory. 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, the trace might reveal that you are adding unnecessary boards.

I'm getting the right number of moves for puzzle04.txt and other puzzles but my program uses twice as much memory as needed. How might I identify what is going wrong? Check the detailed trace for puzzle04.txt in the testing section. Are you adding the initial board to the priority queue twice?

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

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.

Detailed trace for puzzle04.txt. 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.

• The game tree represents relationships obtained by executing valid moves in the slider puzzle. If a search node X is the parent of another search node Y, then the boards in X and Y are neighbors (and one move apart). If the board in a search node equals the board in its grandparent, it is rejected by the critical optimization and its subtree is not explored; we assign a lowercase letter as the ID for such a search node. If the board in a search node equals the goal board, we denote it by brackets in the game tree. The path from the root to such a node provides a sequence of moves to solve the puzzle.

• We also show the contents of the priority queue (assumed to be a binary heap) after each priority queue operation. We use the symbol '-' to denote an empty entry in an array.

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

• Write the data type Board that represents an n-by-n puzzle board. Be sure to thoroughly test and debug it before proceeding.

• Within Solver, write a nested class SearchNode that represents a search node of the game (such as the board, the number of moves to reach it, and the previous search node). Include a constructor that initializes the value of each instance variable. Make the class Comparable so that you can use it with a MinPQ. The compareTo() method should compare search nodes based on the Manhattan (or Hamming) priority function.

• Write the class Solver that uses the A* search algorithm to solve puzzle instances. This will include creating a MinPQ of SearchNode objects. Don't worry about the critical optimization until Solver can solve small puzzles.

  This video is provided for those wishing additional assistance. The video was made in early 2014 and is somewhat out of date. For example, the API has changed.

  Enrichment

  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 the Hamming priority function, this property holds because each tile that is out of place must move at least once to reach its goal position. For the Manhattan priority function, this property holds because each tile must move its Manhattan distance from its goal position.

  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 either edu.princeton.cs.algs4.SET 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.

  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  
  

  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 + 4n² bytes; when n equals 3, this is 156 bytes. To save memory, consider using a 1D array of length n². In principle, each board is a permutation of size n², so you need only about lg ((n²)!) bits to represent it; when n equals 3, this is only 19 bits.

  Are there better ways to solve 8- and 15-puzzle instances using the minimum number of moves? Yes, there are a number of approaches.

  • Use the A* algorithm with a better admissible priority function:

    • Linear conflict: if two tiles form an inversion and each tile is in its respective goal row (column), then add 2 to the Manhattan priority function because one of the tiles must move up/down (left/right) before reaching the goal state. If a row (or column) has more than one such linear conflict, add 2 times the minimum number of tiles you must move to have no linear conflicts in the row (or column).

      // add +0 for row 1         // add +4 for row 1         // add +2 for row 1
      1 2 3 4 5                   3 4 5 1 2                   1 4 2 9 8
      . . . . .                   . . . . .                   . . . . .
      . . . . .                   . . . . .                   . . . . .
      . . . . .                   . . . . .                   . . . . .
      . . . . .                   . . . . .                   . . . . .
      
      // add +2 for row 1         // add +8 for row 1         // add +4 for row 1
      1 4 2 3 5                   5 4 3 2 1                   5 7 4 6 3
      . . . . .                   . . . . .                   . . . . .
      . . . . .                   . . . . .                   . . . . .
      . . . . .                   . . . . .                   . . . . .
      . . . . .                   . . . . .                   . . . . .
      

    • 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 search nodes examined for random 15-puzzle instances by a factor of 1,000.

  • Use a variant of the A* algorithm known as IDA* (for iterative deepening). This paper describes its application to the 15-slider puzzle.

  • Another approach is to use bidirectional search: 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.

  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 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. Alternatively, this paper describes an algorithm that guarantees to perform proportional to n³ moves in the worst case.

  What’s the maximum number of moves need to solve any 8-slider puzzle? Any solvable 8-slider puzzle can be solved with at most 31 moves; any solvable 15-slider puzzle can be solved with at most 80 moves. There are only two solvable 8-slider puzzles (out of 181,440 possibilities) that require 31 moves: puzzle31.txt and puzzle3x3-31.txt. There are only 17 solvable 15-slider puzzles (out of over 10 trillion possibilities) that require 80 moves, including puzzle80.txt.

  What’s the best known algorithm for determining whether a puzzle is solvable? You can do it in time proportional to n². For example, this paper describes a linear-time algorithm to compute the the parity of the number of inversions of the permutation (also known as the sign of the permutation).