8 Puzzle Write a program to solve the 8-puzzle problem (and its natural generali
ID: 3692348 • Letter: 8
Question
8 Puzzle
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:
Hamming priority function. The number of blocks in the wrong position, plus the number of moves made so far to get to the search node. Intuitively, a search node with a small number of blocks in the wrong position is close to the goal, and we prefer a search node 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 search node.
For example, the Hamming and Manhattan priorities of the initial search node below are 5 and 10, respectively.
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 observation: 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 square 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. Best-first search has 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 8 1 3 8 1 3 4 2 4 2 4 2 3 4 2 4 2 5 7 6 5 7 6 5 7 6 5 7 6 5 7 6 previous search node neighbor neighbor neighbor (disallow)
Game tree. One way to view the computation is as a game tree, where each search node is a node in the game tree and the children of a node correspond to its neighboring search nodes. The root of the game tree is the initial search node; the internal nodes have already been processed; the leaf nodes are maintained in a priority queue; at each step, the A* algorithm removes the node with the smallest priority from the priority queue and processes it (by adding its children to both the game tree and the priority queue).
Detecting unsolvable puzzles. Not all initial boards can lead to the goal board by a sequence of legal moves, including the two below:
1 2 3 1 2 3 4 4 5 6 5 6 7 8 8 7 9 10 11 12 13 15 14 unsolvable unsolvable
To detect such situations, 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 blocks (the blank square is not a block). (Difficult challenge for the mathematically inclined: prove this fact.) To apply the fact, run the A* algorithm on two puzzle instances—one with the initial board and one with the initial board modified by swapping a pair of blocks—in lockstep (alternating back and forth between exploring search nodes in each of the two game trees). Exactly one of the two will lead to the goal board.
Board and Solver data types. Organize your program by creating an immutable data type Board with the following API:
Corner cases. You may assume that the constructor receives an N-by-N array containing the N2 integers between 0 and N2 1, where 0 represents the blank square.
Performance requirements. Your implementation should support all Board methods in time proportional to N2 (or better) in the worst case.
Also, create an immutable data type Solver with the following API:
To implement the A* algorithm, you must use MinPQ from algs4.jar for the priority queue(s).
Corner cases. The constructor should throw a java.lang.NullPointerException if passed a null argument.
Solver test client. Use the following test client to read a puzzle from a file (specified as a command-line argument) and print the solution to standard output.
Input and output formats. 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,
% 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
% more puzzle3x3-unsolvable.txt 3 1 2 3 4 5 6 8 7 0 % java Solver puzzle3x3-unsolvable.txt No solution possible
Your program should work correctly for arbitrary N-by-N boards (for any 2 N < 128), even if it is too slow to solve some of them in a reasonable amount of time.
Deliverables. Submit only the files Board.java and Solver.java (with the Manhattan priority). We will supply algs4.jar. You may not call any library functions other those in java.lang, java.util, andalgs4.jar. You must use MinPQ for the priority queue(s).
Explanation / Answer
public class SolverClient
{
public static void main(String[] args) {
// create initial board from file
In in = new In(args[0]);
int N = in.readInt();
int[][] blocks = new int[N][N];
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
blocks[i][j] = in.readInt();
Board initial = new Board(blocks);
// 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);
}
}
}
Solver.java
public class Solver {
private int moves = 0;
private Node finalNode;
private Boolean solverRan, solvable;
public Iterable<Board> solution() {
Node printBoard = finalNode;
LinkedStack<Board> solutionStack = new LinkedStack<Board>();
while (printBoard != null) {
solutionStack.push(printBoard.board);
printBoard = printBoard.prev;
}
if (this.solvable) {
return solutionStack;
} else {
return null;
}
}
public Solver(Board initial) // find a solution to the initial board (using the A* algorithm)
{
Board twin;
Board orig;
Node prev;
Node newNode;
orig = initial;
twin = initial.twin();
Node origNode = new Node(initial, null, moves);
Node twinNode = new Node(twin, null, moves);
MinPQ<Node> PQ = new MinPQ<Node>();
PQ.insert(origNode);
MinPQ<Node> twinPQ = new MinPQ<Node>();
twinPQ.insert(twinNode);
while (true) {
moves++;
origNode = PQ.delMin();
if (origNode.board.isGoal()) {
solverRan = true;
solvable = true;
finalNode = origNode;
break;
}
prev = origNode;
Iterable<Board> neighbors = origNode.board.neighbors();
for (Board neighbor : neighbors) {
newNode = new Node(neighbor, prev, prev.moves + 1);
if (origNode.prev == null || !newNode.board.equals(origNode.prev.board)) {
PQ.insert(newNode);
}
}
twinNode = twinPQ.delMin();
if (twinNode.board.isGoal()) {
solverRan = true;
solvable = false;
finalNode = twinNode;
break;
}
prev = twinNode;
Iterable<Board> twinNeighbors = twinNode.board.neighbors();
for (Board neigbor : twinNeighbors) {
newNode = new Node(neigbor, prev, prev.moves + 1);
if (twinNode.prev == null || !newNode.board.equals(twinNode.prev.board)) {
twinPQ.insert(newNode);
}
}
}
}
public boolean isSolvable() {
return solvable;
}
public int moves() {
if (this.solvable) {
return finalNode.moves;
} else {
return -1;
}
}
private class Node implements Comparable<Node> {
public Board board;
Node prev;
public int priority, moves;
public Node(Board board, Node prev, int moves) {
this.board = board;
this.prev = prev;
this.moves = moves;
this.priority = moves + board.manhattan();
}
public int compareTo(Node that) {
if (this.priority > that.priority) {
return 1;
}
if (that.priority > this.priority) {
return -1;
}
return 0;
}
}
}
Board.java
public class Board {
/**
* An NxN array indexed by i(0to N-1) and j(0-1) representing the position
* of the blocks on the board.
*/
private int[][] board;
/**
* The dimension of the board
*/
private int N;
/**
* Initialises a Board from an N-by-N array of blocks, (where blocks[i][j] =
* block in row i, column j, with i,j indexed from 0 to N-1)
*
* @param blocks NxN array
*/
public Board(int[][] blocks)//
{
N = blocks.length;
board = new int[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
board[i][j] = blocks[i][j];
}
}
}
/**
* return the dimension of the board
*
* @return integer the dimension N
*/
public int dimension() {
return N;
}
/**
* return boolean does the board represent the goal board
*
* @return boolean true if board is goal, false otherwise
*/
public boolean isGoal() {
int row, col;
for (int i = 0; i < (N * N) - 1; i++) {
row = i / N;
col = i % N;
if (board[row][col] != i + 1) {
return false;
}
}
return true;
}
/**
* Finds a twin of the current board. A twin of a board is obtained by
* swapping the position of any two adjacent tiles
*
* @return a twin if the current board
*/
public Board twin() {
Board twin = new Board(board);
//deal with degenerate cases
if (twin == null || twin.dimension() == 1) {
return twin;
}
// We can find a twin by exchanging the leftmost two tiles of a row,
// provided that they are both non-empty. We try the first row, if this
// does not have the first two tiels non-empty, we use the second row
int row;
for (row = 0; row < N; row++) {
if (board[row][0] != 0 && board[row][1] != 0) {
twin.board[row][0] = board[row][1];
twin.board[row][1] = board[row][0];
return twin;
}
}
return twin;
}
/**
* The hamming distance is the number of tiles out of position with respect
* to the goal board
*
* @return the hamming distance from the goal board
*/
public int hamming() {
int ham = 0;
int row, col;
for (int i = 0; i < (N * N); i++) {
row = i / N;
col = i % N;
// the ith element should be i+1 (we have 1 in position 0 etc.)
if (board[row][col] != i + 1 && board[row][col] != 0) {
ham++;
}
}
return ham;
}
/**
* Returns the Manhattan number.
*
* <p>
* The Manhattan number of a tile is the sum of its horizontal and vertical
* distance of that tile from its position on the goal board. The Manhattan
* number of the board is the sum of Manhattan numbers of its tiles position
* on the goal board
* <p>
* @return the Manhattan distance from the goal board
*/
public int manhattan() {
int man = 0;
int row, col, brow, bcol;
for (int i = 0; i < (N * N); i++) {
row = i / N;
col = i % N;
if (board[row][col] == 0) {
continue;
}
brow = (board[row][col] - 1) / N;
bcol = (board[row][col] - 1) % N;
man += Math.abs(brow - row) + Math.abs(bcol - col);
}
return man;
}
/**
* Creates a string representation of the board for display
*
* @return string representation of the board
*/
@Override
public String toString() {
StringBuilder s = new StringBuilder();
s.append(N + " ");
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
s.append(String.format("%2d ", board[i][j]));
}
s.append(" ");
}
return s.toString();
}
/**
* Returns true if the board is equal to the argument, false otherwise.
*
* ***Best practice deviation - in order to implement API, this class does
* not implement hash table.***
*
* Two boards are considered equal if every tile is in the same position on
* each.
*
* @return boolean ture if equal to the argument board, false otherwise
*
* {@inheritDoc}
*
*/
@Override
public boolean equals(Object Y) {
if (Y == this) {
return true;
}
if (Y == null) {
return false;
}
if (this.getClass() != Y.getClass()) {
return false;
}
Board that = (Board) Y;
// If the hamming and manhattan values are cached, the perfomance of
// can be improved in the case where hamming or manhattan values differ
if (this.hamming()
!= that.hamming()) {
return false;
}
if (this.manhattan()
!= that.manhattan()) {
return false;
}
for (int i = 0;
i < (this.dimension()); i++) {
for (int j = 0; j < (this.dimension()); j++) {
if (this.board[i][j] != that.board[i][j]) {
return false;
}
}
}
return true;
}
/**
* Returns a stack of the neighbours of the board.
*
* Neighbours are boards that can be reach within on move from the current
* board. Each board has 2,3 or 4 neighbours.
*
* The stack used in this method is LinkedStack, an implementation of a
* stack using a linked list.
*
* @return A stack containing the neighbours of the board
*
*
*/
public Iterable<Board> neighbors() {
LinkedStack<Board> Stack = new LinkedStack<Board>();
Board neighbor;
int row, col;
for (int i = 0; i < (N * N); i++) {
row = i / N;
col = i % N;
if (board[row][col] == 0) {
if (row != N - 1) {
neighbor = new Board(board);
neighbor.board[row][col] = neighbor.board[row + 1][col];
neighbor.board[row + 1][col] = 0;
Stack.push(neighbor);
}
if (row != 0) {
neighbor = new Board(board);
neighbor.board[row][col] = neighbor.board[row - 1][col];
neighbor.board[row - 1][col] = 0;
Stack.push(neighbor);
}
if (col != N - 1) {
neighbor = new Board(board);
neighbor.board[row][col] = neighbor.board[row][col + 1];
neighbor.board[row][col + 1] = 0;
Stack.push(neighbor);
}
if (col != 0) {
neighbor = new Board(board);
neighbor.board[row][col] = neighbor.board[row][col - 1];
neighbor.board[row][col - 1] = 0;
Stack.push(neighbor);
}
return Stack;
}
}
return Stack;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.