| 36 | |
| 37 | // find a solution to the initial board (using the A* algorithm) |
| 38 | public Solver(Board initial) { |
| 39 | if (initial == null) throw new IllegalArgumentException(); |
| 40 | MinPQ<Node> minPQ = new MinPQ<>(); |
| 41 | MinPQ<Node> minPQForTwin = new MinPQ<>(); |
| 42 | minPQ.insert(new Node(initial, null, 0)); |
| 43 | minPQForTwin.insert(new Node(initial.twin(), null, 0)); |
| 44 | MinPQ<Node> executor = minPQ; |
| 45 | Node node = null; |
| 46 | while (!executor.isEmpty()) { |
| 47 | node = executor.delMin(); |
| 48 | if (node.board.isGoal()) { |
| 49 | break; |
| 50 | } |
| 51 | Iterable<Board> neighbors = node.board.neighbors(); |
| 52 | for (Board b : neighbors) |
| 53 | if (node.prev == null || !b.equals(node.prev.board)) |
| 54 | executor.insert(new Node(b, node, node.moves + 1)); |
| 55 | |
| 56 | executor = executor == minPQ ? minPQForTwin : minPQ; |
| 57 | } |
| 58 | solvable = executor == minPQ; |
| 59 | assert node != null; |
| 60 | moves = node.moves; |
| 61 | goal = node; |
| 62 | } |
| 63 | |
| 64 | // is the initial board solvable? (see below) |
| 65 | public boolean isSolvable() { |