(Solver Data Type) Create an immutable data type Solver in Solver.java with the following API:

Corner cases.

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

And the result should look like this:

Here's the input file:

3 4 1 3 0 2 6 7 5 8

And here's what I have and the format should look like:

Transcribed Image Text:

method Solver (Board initial) int moves () Iterable solution () description find a solution to the initial board (using the A* algorithm) the minimum number of moves to solve initial board sequence of boards in a shortest solution $ java Solver data/puzzle05.txt Minimum number of moves = 5 3 040 3 3 1 4 7 013 3 7 3 125 1 4 7 1 4 7 ∞ os c 12 4 0 7 5 8 6 5 8 03 2 6 58 3 600 2 5 2 3 5 0 8 ∞o os co 6 360 3 80 Solver.java * import edu.princeton.cs.algs4. In; import edu.princeton.cs.algs4.LinkedStack; import edu.princeton.cs.algs4.MinPQ; import edu.princeton.cs.algs4.Stdout; import java.util.Comparator; // A solver based on the A* algorithm for the 8-puzzle and its generalizations. public class Solver { LinkedStack solution; int moves; // Helper search node class. private class SearchNode { Board board; int moves; SearchNode prev; } SearchNode (Board board, int moves, SearchNode previous) { board; } this.board this. moves = moves; this.prev = previous; // Find a solution to the initial board (using the A* algorithm). public Solver (Board initial) { if (initial == null) { throw new NullPointerException(); } Comparator comparator = new ManhattanOrder(); solution = new LinkedStack (); SearchNode first = new SearchNode (initial,0,null); //initialize the first search node. int moves = 0; MinPQ pq = new MinPQ (233, comparator); pq.insert (first); //insert the first node into the queue. while (!pq.isEmpty()) { SearchNode node = Hamming or manhattan distance. if(node.board.isGoal()) { // if a node's board has solved, push that and all previous node except the first into the solution stack. } pq.delMin(); // dequeue the board with minimum for (SearchNode x = node; x.prev != null;x x.prev) { solution.push(x.board); } break; } for (Board x:node.board.neighbors()) { SearchNode next = new SearchNode (x, moves, node); pq.insert(next); } // insert all neighbors into the queue. } this.moves++; // The minimum number of moves to solve the initial board. public int moves () { return this. moves; } } // Sequence of boards in a shortest solution. public Iterable solution () { return solution; } // Helper hamming priority function comparator. private static class HammingOrder implements Comparator { public int compare (SearchNode a, SearchNode b) { if(a.board.hamming() + a.moves > b. board.hamming() + b. moves) { return 1; } else if (a.board.hamming() + a.moves < b.board.hamming() + b.moves) return -1; } else { return 0; } } private static class Manhattanorder implements Comparator { public int compare (SearchNode a, SearchNode b) { if(a.board.manhattan () + a.moves > b. board. manhattan () + b.moves) { return 1; } else if (a.board.manhattan () + a.moves < b.board.manhattan () + b.moves) { return -1; } else { return 0; } } } // Test client. [DO NOT EDIT] public static void main(String[] args) { In in new In (args[0]); int N = in.readInt (); int[][] tiles = new int [N] [N]; for (int i = 0; i < N; i++) { } for (int j = 0; j < N; j++) { tiles[i][j] in. readInt (); = } } Board initial = new Board (tiles); if (initial.isSolvable()) { } Solver solver = new Solver(initial); Stdout.println("Minimum number of moves + solver.moves()); for (Board board solver.solution()) { Stdout.println (board); } } else { Stdout.println("Unsolvable puzzle"); method Solver (Board initial) int moves () Iterable solution () description find a solution to the initial board (using the A* algorithm) the minimum number of moves to solve initial board sequence of boards in a shortest solution $ java Solver data/puzzle05.txt Minimum number of moves = 5 3 040 3 3 1 4 7 013 3 7 3 125 1 4 7 1 4 7 ∞ os c 12 4 0 7 5 8 6 5 8 03 2 6 58 3 600 2 5 2 3 5 0 8 ∞o os co 6 360 3 80 Solver.java * import edu.princeton.cs.algs4. In; import edu.princeton.cs.algs4.LinkedStack; import edu.princeton.cs.algs4.MinPQ; import edu.princeton.cs.algs4.Stdout; import java.util.Comparator; // A solver based on the A* algorithm for the 8-puzzle and its generalizations. public class Solver { LinkedStack solution; int moves; // Helper search node class. private class SearchNode { Board board; int moves; SearchNode prev; } SearchNode (Board board, int moves, SearchNode previous) { board; } this.board this. moves = moves; this.prev = previous; // Find a solution to the initial board (using the A* algorithm). public Solver (Board initial) { if (initial == null) { throw new NullPointerException(); } Comparator comparator = new ManhattanOrder(); solution = new LinkedStack (); SearchNode first = new SearchNode (initial,0,null); //initialize the first search node. int moves = 0; MinPQ pq = new MinPQ (233, comparator); pq.insert (first); //insert the first node into the queue. while (!pq.isEmpty()) { SearchNode node = Hamming or manhattan distance. if(node.board.isGoal()) { // if a node's board has solved, push that and all previous node except the first into the solution stack. } pq.delMin(); // dequeue the board with minimum for (SearchNode x = node; x.prev != null;x x.prev) { solution.push(x.board); } break; } for (Board x:node.board.neighbors()) { SearchNode next = new SearchNode (x, moves, node); pq.insert(next); } // insert all neighbors into the queue. } this.moves++; // The minimum number of moves to solve the initial board. public int moves () { return this. moves; } } // Sequence of boards in a shortest solution. public Iterable solution () { return solution; } // Helper hamming priority function comparator. private static class HammingOrder implements Comparator { public int compare (SearchNode a, SearchNode b) { if(a.board.hamming() + a.moves > b. board.hamming() + b. moves) { return 1; } else if (a.board.hamming() + a.moves < b.board.hamming() + b.moves) return -1; } else { return 0; } } private static class Manhattanorder implements Comparator { public int compare (SearchNode a, SearchNode b) { if(a.board.manhattan () + a.moves > b. board. manhattan () + b.moves) { return 1; } else if (a.board.manhattan () + a.moves < b.board.manhattan () + b.moves) { return -1; } else { return 0; } } } // Test client. [DO NOT EDIT] public static void main(String[] args) { In in new In (args[0]); int N = in.readInt (); int[][] tiles = new int [N] [N]; for (int i = 0; i < N; i++) { } for (int j = 0; j < N; j++) { tiles[i][j] in. readInt (); = } } Board initial = new Board (tiles); if (initial.isSolvable()) { } Solver solver = new Solver(initial); Stdout.println("Minimum number of moves + solver.moves()); for (Board board solver.solution()) { Stdout.println (board); } } else { Stdout.println("Unsolvable puzzle");

Answer rating: 100% (QA)

Solution import javautilComparator public class Solver private MinPQ pq private MinPQ pqTwin private SearchNode goal null private boolean solvable tru... View the full answer