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 (left) to the goal board (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 search node of the game to be a board, the number of moves made to reach the board, and the previous search node. First, insert the initial search node (the initial board, 0 moves, and a null previous search node) into a priority queue. Then, delete from the priority queue the search node with the minimum priority, and insert onto the priority queue all neighboring search nodes (those that can be reached in one move from the dequeued search node). Repeat this procedure until the search node dequeued corresponds to a goal board. The success of this approach hinges on the choice of priority function for a search node. We consider two priority functions:
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 search node 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, when the goal board is dequeued, we have discovered not only a sequence of moves from the initial board to the goal board, 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: search nodes corresponding to the same board are enqueued on the priority queue many times. To reduce unnecessary exploration of useless search nodes, when considering the neighbors of a search node, don't enqueue a neighbor if its board is the same as the board of the previous search node.
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 search node disallow
Your task. Write a program Solver.java that reads the initial board from standard input and prints to standard output a sequence of boards 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, using 0 to represent the blank square. As an example,
Note that your program should work for arbitrary N-by-N boards (for any N greater than 1), even if it is too slow to solve some of them in a reasonable amount of time.% more puzzle04.txt 3 0 1 3 4 2 5 7 8 6 % java Solver < puzzle04.txt Minimum 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 boards can lead to the goal board. Modify your program to detect and report such situations.
Hint: use the fact that boards are divided into two equivalence classes with respect to reachability: (i) those that lead to the goal board and (ii) those that lead to the goal board if we modify the initial board by swapping any pair of adjacent (non-blank) blocks in the same row. (Challenge for the mathematically inclined: prove this fact.) To apply the hint: Run the A* algorithm simultaneously on two puzzle instances—one with the initial board and one with the initial board modified by swapping a pair of adjacent blocks in the same row. Exactly one of the two will lead to the goal board.% more puzzle-unsolvable3x3.txt 3 1 2 3 4 5 6 8 7 0 % java Solver < puzzle3x3-unsolvable.txt No solution possible
Board and Solver data types. Organize your program by creating an immutable data type Board with the following API:
public 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 boolean isGoal() // is this board the goal board?
public Board twin() // a board obtained by exchanging two adjacent blocks in the same row
public boolean equals(Object y) // does this board equal y?
public Iterable<Board> neighbors() // all neighboring boards
public String toString() // string representation of the board in the output format specified above
}
and an immutable data type Solver with the following API:
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 boards in a shortest solution; null if no solution
}
Test client. Include the following main() in Solver. It reads a puzzle instance from standard input and prints the solution to standard output.
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);
// print solution to standard output
if (!solver.isSolvable())
StdOut.println("No solution possible");
else {
StdOut.println("Minimum number of moves = " + solver.moves());
for (Board board : solver.solution())
StdOut.println(board);
}
}
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 algs4.jar). Finally, submit a readme.txt file and answer the questions.