Frequently Asked Questions |

** Can I use different class names, method names,
or method signatures from those proscribed in the API?**
No. This will incur a serious deduction.

**Do I have to implement my own stack, queue, and priority queue?**
No. Use the versions from lecture.
You can either download them individually
or download
`adt.jar`
and add it to your classpath.

**How do I return an Iterable<Board>?**
Add the elements you want to a

**How do I implement equals()?**
See the PhoneNumber.java
example from the elementary symbol table lecture. Be careful to get it right.

** How do I print out 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 print them in reverse order).

**Will the total number of states be enqueued be the same for everyone
in the class?**
Not necessarily. When you remove the minimum key from the priority queue,
there might be several with the same priority.
The one that is removed depends on the order in which you
enqueue neighboring states.

**How do I create a board from the input format?**
Feel free to use the following.

int N = StdIn.readInt(); int[][] tiles = new int[N][N]; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) tiles[i][j] = StdIn.readInt(); Board board = new Board(tiles);

**I run out of memory of some of the large instances. What should I do?**
Be sure to ask Java for additional memory,
e.g., `java -Xmx1600m Solver < ftp/puzzle36.txt`.
If your program is unable to solve certain instances, document that in
your `readme.txt` file.

**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.

Testing and Submission |

**Input.**
The
ftp directory
contains many sample input files.
The shortest solution to `puzzleN.txt` requires exactly N moves.
Warning: `puzzle36.txt` is especially difficult.

**Testing.**
A good way to automatically run your program on our test inputs
is to use
Checker.java.

**Readme.**
Use the
following readme file template and answer all questions.

Possible Progress Steps |

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

- Download the directory
`8puzzle`to your system. It contains a number of sample input files. - Write the data type
`Board`that represents an N-by-N puzzle board. Be sure to throughly test and debug it before proceding. - Write a class
`State`that represents a state of the game (board, number of moves to reach it, and previous state). Make it implement the`Comparable<State>`interface so that you can use it with a`MinPQ`. The`compareTo()`method will compare states based on their Hamming or Manhattan priorities. You can either make this a subclass within`Solver`or make it a stand-alone class. - Write the class
`Solver`that uses the A* algorithm to solve puzzle instances.

Enrichment |

**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 aan 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).

**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.