COMP421 Artificial Intelligence, Assignment II, A* Search

Board.java

import java.util.Arrays;

public class Board implements Comparable<Board> {
    public static final byte BLANK = -1;

    private byte[] numbers;
    private Board father;
    private int totalMovement;
    private int heuristicCost;

    public enum Direction {UP, RIGHT, DOWN, LEFT}

    public Board(byte[] numbers) {
        assert numbers.length == 9;
        this.numbers = numbers;
        heuristicCost = calculateHeuristicCost(numbers);
    }

    public Board(byte[] numbers, Board father) {
        this(numbers);
        this.father = father;
        this.totalMovement = father.getTotalMovement() + 1;
    }

    public Board move(Direction direction) {
        int blankPos = getBlankPos();
        int targetPos = -1;
        switch (direction) {
            case UP:
                if (blankPos / 3 > 0)
                    targetPos = blankPos - 3;
                break;
            case DOWN:
                if (blankPos / 3 < 2)
                    targetPos = blankPos + 3;
                break;
            case LEFT:
                if (blankPos % 3 != 0)
                    targetPos = blankPos - 1;
                break;
            case RIGHT:
                if (blankPos % 3 != 2)
                    targetPos = blankPos + 1;
                break;
        }
        if (targetPos < 0)
            return null;
        byte[] newNumbers = numbers.clone();
        newNumbers[blankPos] = newNumbers[targetPos];
        newNumbers[targetPos] = BLANK;
        return new Board(newNumbers, this);
    }

    private static int calculateHeuristicCost(byte[] numbers) {
        int cost = 0;
        for (int i = 0; i < numbers.length; ++i) {
            if (numbers[i] == BLANK)
                continue;
            assert i >= 0 && i <= 7;
            cost += Math.abs((i / 3) - (numbers[i]) / 3);
            cost += Math.abs((i % 3) - (numbers[i]) % 3);
        }
        return cost;
    }

    private int getBlankPos() {
        for (int i = 0; i < numbers.length; ++i)
            if (numbers[i] == BLANK)
                return i;
        throw new RuntimeException("No blank found on board.");
    }

    public Board getFather() {
        return father;
    }

    public int getTotalMovement() {
        return totalMovement;
    }

    public int getHeuristicCost() {
        return heuristicCost;
    }

    public int getTotalCost() {
        return getTotalMovement() + getHeuristicCost();
    }

    @Override
    public int compareTo(Board o) {
        return getTotalCost() - o.getTotalCost();
    }

    @Override
    public boolean equals(Object o) {
        if (o instanceof Board) {
            Board board = (Board) o;
            return Arrays.equals(board.numbers, numbers);
        }
        return false;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append("[ ");
        for (int i = 0; i < numbers.length; ++i) {
            if (i == 3 || i == 6)
                builder.append("\n  ");
            builder.append(numbers[i] == BLANK ? "#" : numbers[i]);
            builder.append(' ');
        }
        builder.append("] (g = ").append(getTotalMovement())
                .append(", h = ").append(getHeuristicCost()).append(')');
        return builder.toString();
    }

}

PuzzleEight.java

import java.util.*;

public class PuzzleEight {
    public static void main(String[] args) {
        Board board = null;
        if (args.length == 1)
            board = parseBoardFromString(args[0].trim());
        if (board == null) {
            System.out.println("Usage example: \n\t$ java PuzzleEight 30#542176");
            System.exit(1);
        }

        Stack<Board> steps = getSolution(board);
        if (steps.isEmpty())
            System.out.println("No solution.");
        while (!steps.isEmpty())
            System.out.println(steps.pop());
    }

    public static Board parseBoardFromString(String string) {
        if (string.length() != 9)
            return null;
        int setValues = 0;
        byte[] tiles = new byte[9];
        for (int i = 0; i < tiles.length; ++i) {
            char c = string.charAt(i);
            if (c == '#') {
                tiles[i] = Board.BLANK;
            } else {
                tiles[i] = Byte.parseByte("" + c);
                setValues |= 1 << tiles[i];
            }
        }
        if (setValues != 0xff)
            return null;
        return new Board(tiles);
    }

    public static Stack<Board> getSolution(Board initialBoard) {
        PriorityQueue<Board> leafNodes = new PriorityQueue<>();
        HashSet<Board> closedSet = new HashSet<>();
        leafNodes.add(initialBoard);

        while (!leafNodes.isEmpty() && leafNodes.peek().getHeuristicCost() > 0) {
            int currentMinCost = leafNodes.peek().getTotalCost();
            List<Board> newNodes = new ArrayList<>();

            // Poll all leaf nodes whose totalCost equal currentMinCost.
            // For each of them, try to move it in all four directions, and
            // add moved boards back to leafNodes.
            while (!leafNodes.isEmpty() && leafNodes.peek().getTotalCost() == currentMinCost) {
                Board board = leafNodes.poll();
                closedSet.add(board);
                for (Board.Direction direction : Board.Direction.values()) {
                    Board movedBoard = board.move(direction);
                    if (movedBoard != null && !closedSet.contains(movedBoard))
                        newNodes.add(movedBoard);
                }
            }
            leafNodes.addAll(newNodes);
        }

        Stack<Board> stack = new Stack<>();
        for (Board p = leafNodes.poll(); p != null; p = p.getFather())
            stack.push(p);
        return stack;
    }
}