public class Main {
    public static void main(String[] args){

        int[][] numbers = {
                {1, 0, 3},
                {4, 2, 6},
                {7, 5, 8}
        };

        Board board = new Board(numbers);


        Search search = new Search(board);

    }
}

import java.util.ArrayList;

/**
 * The board where the game is played.
 *
 * @author Paymon Sattarzadeh
 * @date 27/11/2014
 * @time 12:20
 */
public class Board {

    /**
     * Numbers in the board
     */
    private int[][] numbers = {};

    private int rows = 3;
    private int columns = 3;

    /**
     * The board
     */
    private ArrayList<Tile> board = new ArrayList();

    /**
     * Constructs a <code>Board</code> instance and fills
     * it with <code>Tile</code> instances
     */
    public Board(int[][] numbers) {

        this.numbers = numbers;
        int j = 0;

        for(int[] row: numbers){

            for (int i = 0; i < row.length; i++) {
                board.add(new Tile(row[i], i, j));
            }

            j += 1;
        }

    }

    /**
     * @return
     *      Numbers for board
     */
    public int[][] getNumbers(){

        return numbers;
    }

    /**
     * @return
     *      Tiles in board
     */
    public ArrayList<Tile> getTiles(){

        return board;
    }

    /**
     * Moves the specified <code>Tile</code> to the specified position.
     * Swaps positions with <code>Tile</code> at that position.
     *
     * @param tile
     *      <code>Tile</code> to be moved
     * @param x
     *      The horizontal position you want <code>Tile</code> to move to.
     * @param y
     *      The vertical position you want <code>Tile</code> to move to.
     */
    public void moveTile(Tile tile, int x, int y) {

        int _x = tile.getXPosition();
        int _y = tile.getYPosition();

        Tile tileToBeMoved = tile;
        Tile tileAtPosition;

        if(findTile(x, y) != null) {
            tileAtPosition = findTile(x, y);
        } else {
            System.out.println("No tile exists at that position");
            return;
        }

        /* Move tileToBeMoved to chosen position */
        tileToBeMoved.setPosition(x, y);

        /* swap*/
        tileAtPosition.setPosition(_x, _y);


    }

    /**
     * Checks if neighbouring <code>Tile</code>s exist, if so, it returns the <code>Tile</code>
     *
     * @param tile
     *      Current <code>Tile</code>
     * @return
     *      Set of <code>Tile</code>s
     */
    public ArrayList<Tile> checkNeighbouringTiles(Tile tile){

        ArrayList<Tile> neighbouringTiles = new ArrayList<>();

        int x = tile.getXPosition();
        int y = tile.getYPosition();

        /* Neighbour to the right of tile */
        int rightNeighbourX = x + 1;
        int rightNeighbourY = y;

        /* Neighbour to the left of tile */
        int leftNeighbourX = x - 1;
        int leftNeighbourY = y;

        /* Neighbour to the top of tile */
        int topNeighbourX = x;
        int topNeighbourY = y - 1;

        /* Neighbour to the bottom of tile */
        int bottomNeighbourX = x;
        int bottomNeighbourY = y + 1;


        for(Tile t: board) {
            if ((t.getXPosition() == rightNeighbourX) && (t.getYPosition() == rightNeighbourY)) {
                neighbouringTiles.add(t);

            } else if((t.getXPosition() == leftNeighbourX) && (t.getYPosition() == leftNeighbourY)){
                neighbouringTiles.add(t);

            } else if((t.getXPosition() == topNeighbourX) && (t.getYPosition() == topNeighbourY)){
                neighbouringTiles.add(t);

            } else if((t.getXPosition() == bottomNeighbourX) && (t.getYPosition() == bottomNeighbourY)){
                neighbouringTiles.add(t);
            }
        }

        return neighbouringTiles;
    }

    /**
     * Finds a <code>Tile</code> with matching position
     *
     * @param x
     *      The horizontal position
     * @param y
     *      The vertical position
     * @return
     *      matching <code>Tile</code>
     */
    public Tile findTile(int x, int y){

        for(Tile t: board) {
            if(t.getXPosition() == x && t.getYPosition() == y)
                return t;
        }

        return null;
    }

    /**
     * Finds a <code>Tile</code> with matching number
     *
     * @param number
     *      The number on the <code>Tile</code>
     * @return
     *      matching <code>Tile</code>
     */
    public Tile findTile(int number){

        for(Tile t: board) {
            if(t.getNumber() == number)
                return t;
        }

        return null;
    }


    /**
     *Prints the board
     */
    public void print() {

        System.out.println("*=====*");

        for(int j = 0; j < rows; j++){
            System.out.print("||");

            for(int i = 0; i < columns; i++){
                if(findTile(i, j) != null){
                    System.out.print(findTile(i, j).getNumber());
                }
            }
            System.out.println("||");
        }

        System.out.println("*=====*");

    }

}

/**
 * Represents a single tile on a board
 *
 * @author Paymon Sattarzadeh
 * @date 27/11/2014
 * @time 02:27
 */
public class Tile {

    /**
     * Number on Tile
     */
    private int number;

    /**
     * Horizontal position of tile
     */
    private int x;

    /**
     * Vertical position of tile
     */
    private int y;

    /**
     * Constructs a <code>Tile</code> instance with a number and position.
     *
     * @param number
     * 		The number for the <code>Tile</code>.
     * @param x
     * 		The Horizontal position for the <code>Tile</code>.
     */
    public Tile(int number, int x, int y){
        this.number = number;
        this.x = x;
        this.y = y;
    }

    /**
     * @param x
     *      Horizontal position for the <code>Tile</code>
     * @param y
     *      Vertical position for the <code>Tile</code>
     */
    public void setPosition(int x, int y){

        this.x = x;
        this.y = y;
    }

    /**
     * @return
     *      Current horizontal position of <code>Tile</code>
     */
    public int getXPosition(){

        return x;
    }

    /**
     * @return
     *      Current vertical position of <code>Tile</code>
     */
    public int getYPosition(){

        return y;
    }

    /**
     * @param number
     *      Number on Tile
     */
    public void setNumber(int number){

        this.number = number;
    }

    /**
     * @return
     *      Current number on tile
     */
    public int getNumber(){

        return number;
    }

}

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;

/**
 * Respresents the A* algorithm
 *
 * @author Paymon Sattarzadeh
 * @date 27/11/2014
 * @time 16:19
 */
public class Search {

    /**
     * Active instance of <code>Board</code>
     */
    private Board board;

    /**
     * Set of fringes
     */
    private ArrayList<Integer> fringes = new ArrayList<>();

    /**
     * Current nodes
     */
    private int node;

    /**
     * Map linking tiles(by number) to the goal state
     */
    private static Map<Integer, int[]> goalStates = new HashMap<>();

    /**
     * g value
     */
    private int g = 0;

    /**
     * Is the search complete
     */
    private boolean searchComplete = false;

    /**
     * The last move
     */
    private int lastMove = 0;

    /**
     * Fills goalStates Map
     */
    static {
        goalStates.put(1, new int[]{0, 0});
        goalStates.put(2, new int[]{1, 0});
        goalStates.put(3, new int[]{2, 0});
        goalStates.put(4, new int[]{0, 1});
        goalStates.put(5, new int[]{1, 1});
        goalStates.put(6, new int[]{2, 1});
        goalStates.put(7, new int[]{0, 2});
        goalStates.put(8, new int[]{1, 2});
    };

    /**
     * Construct the <code>Search</code> instance
     *
     * @param board
     *      The board
     */
    public Search(Board board){
        this.board = board;

        searchAlgo();
    }

    /**
     * Main search algorithm
     */
    private void searchAlgo() {

        ArrayList<Integer> nodeFValues = new ArrayList();
        ArrayList<Tile> nodeTiles = new ArrayList<>();

        System.out.println("Step: " + g);

        board.print();

        /* Stores all the f values for the nodes in the fringe */
        for(Tile tile: board.checkNeighbouringTiles(board.findTile(0))){

            if(lastMove != tile.getNumber()) {
                nodeFValues.add(node(tile));
                nodeTiles.add(tile);
            }

        }

        /* Gets the minimum fringe */
        int minFValueIndex = nodeFValues.indexOf(Collections.min(nodeFValues));

        if (tilesOutOfPlaceHeuristic(board) == 0){
            System.out.println("Complete");
            searchComplete = true;

            return;
        }

        /* Goes to the node with the lowest f value. */
        board.moveTile(board.findTile(0),
                nodeTiles.get(minFValueIndex).getXPosition(),
                nodeTiles.get(minFValueIndex).getYPosition());

        lastMove = nodeTiles.get(minFValueIndex).getNumber();

        g += 1;

        /* If search is incomplete, it recursively calls itself */
        if(!searchComplete)
            searchAlgo();


    }

    /**
     * Represents each node
     *
     * @param tile
     *      The tile to be moved in the node
     * @return
     *      f value
     */
    private int node(Tile tile){

        /** Initialises new board object */
        Board nodeBoard = new Board(board.getNumbers());

        nodeBoard.moveTile(nodeBoard.findTile(0), tile.getXPosition(), tile.getYPosition());//moves 1 to 0, so 4 out of place now

        int h1 = tilesOutOfPlaceHeuristic(nodeBoard);
        int h2 = manhattanHeuristic(nodeBoard);

        int f = g + h2;

        return f;
    }

    /**
     * Calculates horizontal and vertical distances of tiles from their proper places.
     * Admissible Heuristic.
     *
     * @return
     *      Sum of horizontal and vertical distances of tiles from their proper places.
     */
    private int manhattanHeuristic(Board board) {

        int sum = 0;
        ArrayList<Tile> tiles = board.getTiles();
        int[] goalState;
        int goalX;
        int goalY;
        int differenceX;
        int differenceY;

        for(Tile tile: tiles){

            if(tile.getNumber() != 0) {
                goalState = goalStates.get(tile.getNumber());
                goalX = goalState[0];
                goalY = goalState[1];

                differenceX = goalX - tile.getXPosition();
                differenceY = goalY - tile.getYPosition();

                sum += Math.abs(differenceX) + Math.abs(differenceY);
            }

        }

        return sum;
    }

    /**
     * Calculates number of tiles out of place. Admissible Heuristic.
     *
     * @return
     *      Number of tiles out of place
     */
    private int tilesOutOfPlaceHeuristic(Board board) {

        int tilesInWrongPlace = 0;
        ArrayList<Tile> tiles = board.getTiles();

        for(Tile tile: tiles){

            if(tile.getNumber() != 0) {
                if ((tile.getXPosition() != goalStates.get(tile.getNumber())[0])
                        || (tile.getYPosition() != goalStates.get(tile.getNumber())[1])){
                    tilesInWrongPlace += 1;
                }
            }

        }

        return tilesInWrongPlace;
    }

}