Class Solver

04Lab-8Puzzle/Solver.java:12–110

import edu.princeton.cs.algs4.StdOut;

public class Solver {
    private final boolean solvable;

    private final int moves;

    private final Node goal;

    private class Node implements Comparable<Node> {
        final Board board;
        final Node prev;
        final int moves;
        final int manhattanScore;

        Node(Board b, Node p, int m) {
            board = b;
            prev = p;
            moves = m;
            manhattanScore = m + b.manhattan();
        }

        public int compareTo(Node that) {
            return Integer.compare(this.manhattanScore, that.manhattanScore);
        }
    }

    // find a solution to the initial board (using the A* algorithm)
    public Solver(Board initial) {
        if (initial == null) throw new IllegalArgumentException();
        MinPQ<Node> minPQ = new MinPQ<>();
        MinPQ<Node> minPQForTwin = new MinPQ<>();
        minPQ.insert(new Node(initial, null, 0));
        minPQForTwin.insert(new Node(initial.twin(), null, 0));
        MinPQ<Node> executor = minPQ;
        Node node = null;
        while (!executor.isEmpty()) {
            node = executor.delMin();
            if (node.board.isGoal()) {
                break;
            }
            Iterable<Board> neighbors = node.board.neighbors();
            for (Board b : neighbors)
                if (node.prev == null || !b.equals(node.prev.board))
                    executor.insert(new Node(b, node, node.moves + 1));

            executor = executor == minPQ ? minPQForTwin : minPQ;
        }
        solvable = executor == minPQ;
        assert node != null;
        moves = node.moves;
        goal = node;
    }

    // is the initial board solvable? (see below)
    public boolean isSolvable() {
        return solvable;
    }

    // min number of moves to solve initial board; -1 if unsolvable