8-Puzzle Board.java

Board.java

import java.util.ArrayList;

public class Board {
  private int[][] board;
  private final int n;
  private int hammingDist;
  private int manhattanDist;
  private int blankX, blankY;
  // create a board from an n-by-n array of tiles,
  // where tiles[row][col] = tile at (row, col)
  public Board(int[][] tiles) {
    if (tiles == null) {
      throw new IllegalArgumentException("tiles must not be null");
    }
    n = tiles.length;
    board = new int[n][n];
    hammingDist = 0;
    manhattanDist = 0;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        board[i][j] = tiles[i][j];
        if (board[i][j] == 0) {
          blankX = i;
          blankY = j;
        }
        else {
          int x = board[i][j] - 1;
          int deltaX = Math.abs(i - x / n);
          int deltaY = Math.abs(j - x % n);
          if (deltaX + deltaY > 0) {
            hammingDist++;
            manhattanDist += deltaX + deltaY;
          }
        }
      }
    }
  }
                                          
  // string representation of this board
  public String toString() {
    StringBuilder ret = new StringBuilder();
    ret.append(n);
    for (int i = 0; i < n; i++) {
      ret.append("\n");
      String sep = "";
      for (int j = 0; j < n; j++) {
        ret.append(sep + board[i][j]);
        sep = " ";
      }
    }
    return ret.toString();
  }

  // board dimension n
  public int dimension() {
    return n;
  }

  // number of tiles out of place
  public int hamming() {
    return hammingDist;
  }

  // sum of Manhattan distances between tiles and goal
  public int manhattan() {
    return manhattanDist;
  }

  // is this board the goal board?
  public boolean isGoal() {
    return hammingDist == 0;
  }

  // does this board equal y?
  public boolean equals(Object y) {
    if (this == y) {
      return true;
    }
    if (y == null) {
      return false;
    }
    if (getClass() != y.getClass()) {
      return false;
    }
    Board other = (Board) y;
    if (dimension() != other.dimension()) {
      return false;
    }
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (board[i][j] != ((Board) y).board[i][j]) {
          return false;
        }
      }
    }
    return true;
  }

  // all neighboring boards
  public Iterable<Board> neighbors() {
    ArrayList<Board> boards = new ArrayList<Board>();
    int[] dx = {-1, 0, 1, 0};
    int[] dy = { 0, 1, 0, -1};
    for (int i = 0; i < 4; i++) {
      if (!(blankX + dx[i] < 0 || blankX + dx[i] >= n ||
          blankY + dy[i] < 0 || blankY + dy[i] >= n)) {
        swap(blankX, blankY, blankX + dx[i], blankY + dy[i]);
        boards.add(new Board(board));
        swap(blankX, blankY, blankX + dx[i], blankY + dy[i]);
      }
    }
    return boards;
  }
  

  // a board that is obtained by exchanging any pair of tiles
  public Board twin() {
    Board b = null;
    for (int i = 0; i < n; i++) {
      if (board[0][i] != 0 && board[n - 1][i] != 0) {
        swap(0, i, n - 1, i);
        b = new Board(board);
        swap(0, i, n - 1, i);
        break;
      }
    }
    return b;
  }

  private void swap(int a, int b, int c, int d) {
    int temp = board[a][b];
    board[a][b] = board[c][d];
    board[c][d] = temp;
  }
}

MinPQ.java

/******************************************************************************
 *  Compilation:  javac MinPQ.java
 *  Execution:    java MinPQ < input.txt
 *  Dependencies: StdIn.java StdOut.java
 *  Data files:   https://algs4.cs.princeton.edu/24pq/tinyPQ.txt
 *  
 *  Generic min priority queue implementation with a binary heap.
 *  Can be used with a comparator instead of the natural order.
 *
 *  % java MinPQ < tinyPQ.txt
 *  E A E (6 left on pq)
 *
 *  We use a one-based array to simplify parent and child calculations.
 *
 *  Can be optimized by replacing full exchanges with half exchanges
 *  (ala insertion sort).
 *
 ******************************************************************************/

import java.util.Comparator;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 *  The {@code MinPQ} class represents a priority queue of generic keys.
 *  It supports the usual <em>insert</em> and <em>delete-the-minimum</em>
 *  operations, along with methods for peeking at the minimum key,
 *  testing if the priority queue is empty, and iterating through
 *  the keys.
 *  <p>
 *  This implementation uses a <em>binary heap</em>.
 *  The <em>insert</em> and <em>delete-the-minimum</em> operations take
 *  &Theta;(log <em>n</em>) amortized time, where <em>n</em> is the number
 *  of elements in the priority queue. This is an amortized bound
 *  (and not a worst-case bound) because of array resizing operations.
 *  The <em>min</em>, <em>size</em>, and <em>is-empty</em> operations take
 *  &Theta;(1) time in the worst case.
 *  Construction takes time proportional to the specified capacity or the
 *  number of items used to initialize the data structure.
 *  <p>
 *  For additional documentation, see
 *  <a href="https://algs4.cs.princeton.edu/24pq">Section 2.4</a> of
 *  <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
 *
 *  @author Robert Sedgewick
 *  @author Kevin Wayne
 *
 *  @param <Key> the generic type of key on this priority queue
 */
public class MinPQ<Key> implements Iterable<Key> {
    private Key[] pq;                    // store items at indices 1 to n
    private int n;                       // number of items on priority queue
    private Comparator<Key> comparator;  // optional comparator

    /**
     * Initializes an empty priority queue with the given initial capacity.
     *
     * @param  initCapacity the initial capacity of this priority queue
     */
    public MinPQ(int initCapacity) {
        pq = (Key[]) new Object[initCapacity + 1];
        n = 0;
    }

    /**
     * Initializes an empty priority queue.
     */
    public MinPQ() {
        this(1);
    }

    /**
     * Initializes an empty priority queue with the given initial capacity,
     * using the given comparator.
     *
     * @param  initCapacity the initial capacity of this priority queue
     * @param  comparator the order in which to compare the keys
     */
    public MinPQ(int initCapacity, Comparator<Key> comparator) {
        this.comparator = comparator;
        pq = (Key[]) new Object[initCapacity + 1];
        n = 0;
    }

    /**
     * Initializes an empty priority queue using the given comparator.
     *
     * @param  comparator the order in which to compare the keys
     */
    public MinPQ(Comparator<Key> comparator) {
        this(1, comparator);
    }

    /**
     * Initializes a priority queue from the array of keys.
     * <p>
     * Takes time proportional to the number of keys, using sink-based heap construction.
     *
     * @param  keys the array of keys
     */
    public MinPQ(Key[] keys) {
        n = keys.length;
        pq = (Key[]) new Object[keys.length + 1];
        for (int i = 0; i < n; i++)
            pq[i+1] = keys[i];
        for (int k = n/2; k >= 1; k--)
            sink(k);
        assert isMinHeap();
    }

    /**
     * Returns true if this priority queue is empty.
     *
     * @return {@code true} if this priority queue is empty;
     *         {@code false} otherwise
     */
    public boolean isEmpty() {
        return n == 0;
    }

    /**
     * Returns the number of keys on this priority queue.
     *
     * @return the number of keys on this priority queue
     */
    public int size() {
        return n;
    }

    /**
     * Returns a smallest key on this priority queue.
     *
     * @return a smallest key on this priority queue
     * @throws NoSuchElementException if this priority queue is empty
     */
    public Key min() {
        if (isEmpty()) throw new NoSuchElementException("Priority queue underflow");
        return pq[1];
    }

    // helper function to double the size of the heap array
    private void resize(int capacity) {
        assert capacity > n;
        Key[] temp = (Key[]) new Object[capacity];
        for (int i = 1; i <= n; i++) {
            temp[i] = pq[i];
        }
        pq = temp;
    }

    /**
     * Adds a new key to this priority queue.
     *
     * @param  x the key to add to this priority queue
     */
    public void insert(Key x) {
        // double size of array if necessary
        if (n == pq.length - 1) resize(2 * pq.length);

        // add x, and percolate it up to maintain heap invariant
        pq[++n] = x;
        swim(n);
        assert isMinHeap();
    }

    /**
     * Removes and returns a smallest key on this priority queue.
     *
     * @return a smallest key on this priority queue
     * @throws NoSuchElementException if this priority queue is empty
     */
    public Key delMin() {
        if (isEmpty()) throw new NoSuchElementException("Priority queue underflow");
        Key min = pq[1];
        exch(1, n--);
        sink(1);
        pq[n+1] = null;     // to avoid loiterig and help with garbage collection
        if ((n > 0) && (n == (pq.length - 1) / 4)) resize(pq.length / 2);
        assert isMinHeap();
        return min;
    }


   /***************************************************************************
    * Helper functions to restore the heap invariant.
    ***************************************************************************/

    private void swim(int k) {
        while (k > 1 && greater(k/2, k)) {
            exch(k, k/2);
            k = k/2;
        }
    }

    private void sink(int k) {
        while (2*k <= n) {
            int j = 2*k;
            if (j < n && greater(j, j+1)) j++;
            if (!greater(k, j)) break;
            exch(k, j);
            k = j;
        }
    }

   /***************************************************************************
    * Helper functions for compares and swaps.
    ***************************************************************************/
    private boolean greater(int i, int j) {
        if (comparator == null) {
            return ((Comparable<Key>) pq[i]).compareTo(pq[j]) > 0;
        }
        else {
            return comparator.compare(pq[i], pq[j]) > 0;
        }
    }

    private void exch(int i, int j) {
        Key swap = pq[i];
        pq[i] = pq[j];
        pq[j] = swap;
    }

    // is pq[1..n] a min heap?
    private boolean isMinHeap() {
        for (int i = 1; i <= n; i++) {
            if (pq[i] == null) return false;
        }
        for (int i = n+1; i < pq.length; i++) {
            if (pq[i] != null) return false;
        }
        if (pq[0] != null) return false;
        return isMinHeapOrdered(1);
    }

    // is subtree of pq[1..n] rooted at k a min heap?
    private boolean isMinHeapOrdered(int k) {
        if (k > n) return true;
        int left = 2*k;
        int right = 2*k + 1;
        if (left  <= n && greater(k, left))  return false;
        if (right <= n && greater(k, right)) return false;
        return isMinHeapOrdered(left) && isMinHeapOrdered(right);
    }


    /**
     * Returns an iterator that iterates over the keys on this priority queue
     * in ascending order.
     * <p>
     * The iterator doesn't implement {@code remove()} since it's optional.
     *
     * @return an iterator that iterates over the keys in ascending order
     */
    public Iterator<Key> iterator() {
        return new HeapIterator();
    }

    private class HeapIterator implements Iterator<Key> {
        // create a new pq
        private MinPQ<Key> copy;

        // add all items to copy of heap
        // takes linear time since already in heap order so no keys move
        public HeapIterator() {
            if (comparator == null) copy = new MinPQ<Key>(size());
            else                    copy = new MinPQ<Key>(size(), comparator);
            for (int i = 1; i <= n; i++)
                copy.insert(pq[i]);
        }

        public boolean hasNext()  { return !copy.isEmpty();                     }
        public void remove()      { throw new UnsupportedOperationException();  }

        public Key next() {
            if (!hasNext()) throw new NoSuchElementException();
            return copy.delMin();
        }
    }
}

Solver.java

import java.util.LinkedList;
import java.util.Deque;
import edu.princeton.cs.algs4.MinPQ;

public class Solver {
  private Node solutionNode = null;
  // find a solution to the initial board (using the A* algorithm)
  public Solver(Board initial) {
    if (initial == null) {
      throw new IllegalArgumentException("initial must not be null");
    }
    MinPQ<Node> tree1 = new MinPQ<Node>(
      (Node a, Node b) -> (a.board.manhattan() + a.moves - b.board.manhattan() - b.moves)
    );
    MinPQ<Node> tree2 = new MinPQ<Node>(
      (Node a, Node b) -> (a.board.manhattan() + a.moves - b.board.manhattan() - b.moves)
    );

    tree1.insert(new Node(initial));
    tree2.insert(new Node(initial.twin()));

    for (int i = 0; !tree1.isEmpty(); i++) {
      if (i % 2 == 0) {
        Node res = visit(tree1);
        if (res != null) {
          solutionNode = res;
          break;
        }
      } else {
        Node res = visit(tree2);
        if (res != null) {
          break;
        }
      }
    }
  }

  private Node visit(MinPQ<Node> pq) {
    if (!pq.isEmpty()) {
      Node curr = pq.delMin();
      if (curr.board.isGoal()) {
        return curr;
      }
      for (Board neighbor : curr.board.neighbors()) {
        if (curr.previous == null || !curr.previous.board.equals(neighbor)) {
          pq.insert(new Node(neighbor, curr.moves + 1, curr));
        }
      }
    }
    return null;
  }

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

  // min number of moves to solve initial board
  public int moves() {
    if (solutionNode != null) {
      return solutionNode.moves;
    }
    return -1;
  }

  // sequence of boards in a shortest solution
  public Iterable<Board> solution() {
    if (!isSolvable()) {
      return null;
    }
    Deque<Board> solutionPath = new LinkedList<Board>();
    Node node = solutionNode;
    while (node != null) {
      solutionPath.addFirst(node.board); 
      node = node.previous;
    }
    return solutionPath;
  }
 
  private class Node {
    public Board board = null;
    public Node previous = null;
    public int moves = 0;
    Node(Board board) {
      this.board = board;
    }
    Node(Board board, int moves, Node previous) {
      this.board = board;
      this.moves = moves;
      this.previous = previous;
    }
  }
}