Write a program to solve the 8-puzzle problem (and its natural generalizations) using the A* search algorithm.

**The problem.**
The 8-puzzle problem
is a puzzle invented and popularized by Noyes Palmer Chapman in the 1870s. It is
played on a 3-by-3 grid with 8 square blocks labeled 1 through 8 and a blank
square. Your goal is to rearrange the blocks so that they are in order, using
as few moves as possible.
You are permitted to slide blocks horizontally or vertically
into the blank square.
The following
shows a sequence of legal moves from an initial board position (left)
to the goal position (right).

1 3 1 3 1 2 3 1 2 3 1 2 3 4 2 5 => 4 2 5 => 4 5 => 4 5 => 4 5 6 7 8 6 7 8 6 7 8 6 7 8 6 7 8 initial 1 left 2 up 5 left goal

**Best-first search.**
Now, we describe a solution to the problem that illustrates a
general artificial intelligence methodology known as the
A* search algorithm.
We define a *state* of the game to be a board position, the number
of moves made to reach the board position, and the previous state.
First, insert the initial state
(the initial board, 0 moves, and a null previous state)
into a priority queue. Then,
delete from the priority queue the state with the minimum priority,
and insert onto the priority queue all neighboring states
(those that can be reached in one move).
Repeat this procedure until the state dequeued is the goal state.
The success of this approach
hinges on the choice of *priority function* for a state. We
consider two priority functions:

*Hamming priority function.*The number of blocks in the wrong position, plus the number of moves made so far to get to the state. Intutively, a state with a small number of blocks in the wrong position is close to the goal state, and we prefer a state that have been reached using a small number of moves.*Manhattan priority function.*The sum of the Manhattan distances (sum of the vertical and horizontal distance) from the blocks to their goal positions, plus the number of moves made so far to get to the state.

8 1 3 1 2 3 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 4 2 4 5 6 ---------------------- ---------------------- 7 6 5 7 8 1 1 0 0 1 1 0 1 1 2 0 0 2 2 0 3 initial goal Hamming = 5 + 0 Manhattan = 10 + 0

We make a key oberservation: To solve the puzzle from a given state on the priority queue, the total number of moves we need to make (including those already made) is at least its priority, using either the Hamming or Manhattan priority function. (For Hamming priority, this is true because each block that is out of place must move at least once to reach its goal position. For Manhattan priority, this is true because each block must move its Manhattan distance from its goal position. Note that we do not count the blank tile when computing the Hamming or Manhattan priorities.) Consequently, as soon as we dequeue a state, we have not only discovered a sequence of moves from the initial board to the board associated with the state, but one that makes the fewest number of moves. (Challenge for the mathematically inclined: prove this fact.)

**A critical optimization.**
After implementing best-first search, you will notice one annoying
feature: states corresponding to the same board position
are enqueued on the priority queue many times.
To reduce unnecessary exploration of useless states,
when considering the neighbors of a state, don't enqueue
a neighbor if its board position is the same as the
previous state.

8 1 3 8 1 3 8 1 3 4 2 4 2 4 2 7 6 5 7 6 5 7 6 5 previous state disallow

**Your task.**
Write a program `Solver.java` that reads the initial board
from standard input and prints to standard output a sequence of
board positions that solves the puzzle in the fewest number of moves.
Also print out the total number of moves.

The input and output format for a board is the board dimension *N* followed by
the *N*-by-*N*
initial board position, using 0 to represent the blank square.
As an example,

Note that your program should work for arbitrary% more puzzle04.txt3 0 1 3 4 2 5 7 8 6 %java Solver < puzzle04.txtMinimum number of moves = 4 3 0 1 3 4 2 5 7 8 6 3 1 0 3 4 2 5 7 8 6 3 1 2 3 4 0 5 7 8 6 3 1 2 3 4 5 0 7 8 6 3 1 2 3 4 5 6 7 8 0

**Detecting infeasible puzzles.**
Not all initial board positions can lead to the goal state.
Modify your program to detect and report such situations.

%more puzzle-impossible3x3.txt3 1 2 3 4 5 6 8 7 0 %java Solver < puzzle3x3-impossible.txtNo solution possible

**Board and Solver data types.**
Organize your program by creating two immutable data types `Board` and
`Solver`, with the following APIs.
Do not add any other public methods.

Include the followingpublic class Board { public Board(int[][] tiles) // construct a board from an N-by-N array of tiles, where tiles[i][j] = tile in row i, column j public int hamming() // number of blocks out of place public int manhattan() // sum of Manhattan distances between blocks and goal public Board twin() // a board obtained by exchanging two adjacent blocks in the same row public boolean equals(Object y) // does this board position equal y? public Iterable<Board> neighbors() // all neighboring board positions public void draw() // draw the board to standard draw public String toString() // string representation of the board in the output format specified above } public class Solver { public Solver(Board initial) // find a solution to the initial board public boolean isSolvable() // is the initial board solvable? public int moves() // return min number of moves to solve initial board; -1 if no solution public Iterable<Board> solution() // return sequence of board positions in a shortest solution; null if no solution }

public static void main(String[] args) { // create initial board from standard input 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 initial = new Board(tiles); // solve the puzzle Solver solver = new Solver(initial); if (!solver.isSolvable()) { StdOut.println("No solution possible"); } else { StdOut.println("Minimum number of moves = " + solver.moves()); // print and animate the solution StdDraw.show(0); for (Board board : solver.solution()) { StdOut.println(board); StdDraw.clear(); board.draw(); StdDraw.show(1000); } } }

**Deliverables.**
Submit `Board.java`, `Solver.java`
(with the Manhattan priority),
and any other helper data types that you use
(excluding those in `stdlib.jar` and `adt.jar`).
Finally, submit a
readme.txt file and answer the questions.