Question

Write a program ( Java) to solve the 8-puzzle problem (and its natural generalizations) using the A* search algorithm. The problem. The 8-puzzle problem 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. 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). 13 13 123 123 123 4 2 5 => 4 2 5 => 4 5 => 4 5 => 4 5 6 786 786 786 786 78 initial goal Best-first search. We now describe an algorithmic 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 the 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. Hamming priority function. The number of blocks in the wrong position, plus the number of moves made so far to get to the state. Intuitively, 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. For example, the Hamming and Manhattan priorities of the initial state below are 5 and 10, respectively. 813 123 12345678 12345678 4 2 4 5 6 ---------------------- ---------------------- 765 78 11001101 12002203 initial goal Hamming = 5 + 0 Manhattan = 10 + 0 We make a key observation: 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. 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 prevent unnecessary exploration of useless states, when considering the neighbors of a state, don't enqueue the neighbor if its board position is the same as the previous state. 813 813 813 424242 765 765 765 previous state disallow Your task. Write a program 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 and the total number of states ever enqueued. The input will consist of the board dimension N followed by the N-by-N initial board position. The input format uses 0 to represent the blank square. Important note: implement the Hamming priority function. Sample input: 3 013 425 786 Sample output: 13 425 786 13 425 786 123 45 786 123 45 786 123 456 78 Number of states enqueued = 10 Minimum number of moves = 4 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.

Answer 1

Java coad

For 8 puzzle problem

public class Board {
   public Board(int[][] tiles)        // construct a board from an N-by-N array of tiles
   public int hamming()               // return number of blocks out of place
   public int manhattan()             // return sum of Manhattan distances between blocks and goal
   public boolean equals(Object y)    // does this board position equal y
   public Iterable<Board> neighbors() // return an Iterable of all neighboring board positions
   public String toString()           // return a string representation of the board
}


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 an Iterable of board positions in solution
}
main() 

public static void main(String[] args) {
   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);
    Solver solver = new Solver(initial);
    for (Board board : solver.solution())
       System.out.println(board);
    if (!solver.isSolvable()) System.out.println("No solution possible");
    else System.out.println("Minimum number of moves = " + solver.moves());
}

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