Hello,

Below is the code I have written for this assignment so far, I was wondering if someone could give me some guidance or help as what I can do better, what I am doing wrong?

import edu.princeton.cs.algs4.MinPQ;

/**

* Solver class is used to solve any puzzle that is in the "8 puzzle format"

* It implements the A* algorithm which is used in path-finding games and map

* traversals. It approximates the shortest path from start to finish.

* @author amie3

*/

public class Solver{

private Node search;//create a field to implement the SearchNode

private int movesToSolve;//field used to find the number of moves it takes to solve our initial puzzle

private boolean canUSolve; //we will initially set it to false in the Solver method

/**

* The solver method used the A* algorithm to find a solution to the

* initial board using the MinPQ data type

*

* Generic min priority queue implementation with a binary heap.

* Can be used with a comparator instead of the natural order.

* The MinPQ class represents a priority queue of generic keys.

* It supports the usual insert and delete-the-minimum operations, along with methods for peeking at the minimum key,

* testing if the priority queue is empty, and iterating through the keys.

* This implementation uses a binary heap. The insert and delete-the-minimum operations take logarithmic amortized time.

* The min, size, and is-empty operations take constant time. Construction takes time proportional to the specified capacity or the

* number of items used to initialize the data structure.

*

* 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 predecessor search node.

* First, insert the initial search node (the initial board, 0 moves, and a null predecessor 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:

* @param initial

*/

public Solver(Board initial) {

//corner exception, throw illegal argument if the initial board cannot be solved

if(initial == null) {

throw new java.lang.IllegalArgumentException("sorry, initial board is not solvable :(");

}

canUSolve = false; //Initialize with false

movesToSolve = 0; //initialize with 0

MinPQ mini = new MinPQ(); //create a new instance of the MinPQ class

//First, insert the initial search node (the initial board, 0 moves, and a null previous search node) into a priority queue.

mini.insert(new Node(initial, movesToSolve, null));

//if the board is not solved, go through the instructions within the while loop

while(!canUSolve) {

Node lastNode = mini.delMin();//delete from the priority queue the search node with the minimum priority

if(lastNode.board.isGoal()) {//if this is the goal board

movesToSolve = -1;

canUSolve = false;

}

}

}

/**

* Moves method solves the minimum number of moves to solve the initial puzzle

* @return the number of moves it takes to solve

*/

public int moves() {

return movesToSolve;

}

/*create a search node for the game to be a board, the number of moves made to reach the board

* and the predecessor search node

*/

private class Node implements Comparable {

private Board board; //create an instance of board

//constructor for the search node to implement First, insert the initial search node

//(the initial board, 0 moves, and a null previous search node) into a priority queue.

public Node(Board initial, int movesToSolve, Object object) {

// TODO Auto-generated constructor stub

}

@Override

public int compareTo(Node arg0) {

// TODO Auto-generated method stub

return 0;

}

}

}

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

Also, create an immutable data type Solver with the following API:

public class Solver {  public Solver(Board initial) // find a solution to the initial board (using the A* algorithm)  public int moves() // min number of moves to solve initial board  public Iterable solution() // sequence of boards in a shortest solution  public static void main(String[] args) // solve a slider puzzle (given below) } 

To implement the A* algorithm, you must use the MinPQ data type from algs4.jar for the priority queue.

Corner cases. The constructor should throw a java.lang.IllegalArgumentException if the initial board is not solvable and a java.lang.NullPointerException if the initial board is null.