/* vim: set expandtab tabstop=4 shiftwidth=4 : */

public class Board {

    private int d;
    private byte[][] blocks;
    private int openRow;
    private int openCol;

    private Board(byte[][] blocks, int openI, int openJ)
    {
        this.d = blocks[0].length;
        this.blocks = blocks;
        this.openRow = openI;
        this.openCol = openJ;
    }

    // construct a board from an N-by-N array of blocks
    // (where blocks[i][j] = block in row i, column j)
    public Board(int[][] blocks)
    {

        this.d = blocks[0].length;
        this.blocks = new byte[d][d];

        for (int i = 0; i < d; i++)
        {
            for (int j = 0; j < d; j++)
            {
                this.blocks[i][j] = (byte) blocks[i][j];
                if (blocks[i][j] == 0)
                {
                    this.openRow = i;
                    this.openCol = j;
                }
            }
        }
    }

    // board dimension N
    public int dimension()
    {
        return d;
    }

    // number of blocks out of place
    public int hamming()
    {
        int k = 1;
        int hamming = 0;

        for (int i = 0; i < d; i++)
            for (int j = 0; j < d; j++, k++)
                if (blocks[i][j] != 0 && blocks[i][j] != k) hamming += 1;

        return hamming;
    }

    // sum of Manhattan distances between blocks and goal
    public int manhattan()
    {
        int manhattan = 0;

        for (int i = 0; i < d; i++)
            for (int j = 0; j < d; j++)
            {
                int v = blocks[i][j] -1;
                if (v == -1) continue;
                manhattan += Math.abs((v / d) - i) + Math.abs((v % d) - j);
            }

        return manhattan;
    }

    // is this board the goal board?
    public boolean isGoal()
    {
        int k = 1;

        if (blocks[d-1][d-1] != 0) return false;

        for (int i = 0; i < d; i++)
            for (int j = 0; j < d; j++)
                if (blocks[i][j] != k++ && !((i == j) && (j == d - 1))) return false;

        return true;
    }

    private byte[][] copy()
    {
        byte[][] bytes = new byte[d][d];

        for (int i = 0; i < d; i++)
            for (int j = 0; j < d; j++)
                bytes[i][j] = blocks[i][j];

        return bytes;
    }

    // a board obtained by exchanging two adjacent blocks in the same row
    public Board twin()
    {
        int row = 0;
        if (openRow == 0) row = 1;

        byte [][]bytes = copy();

        byte tmp = bytes[row][0];
        bytes[row][0] = bytes[row][1];
        bytes[row][1] = tmp;

        return new Board(bytes, openRow, openCol);
    }

    // does this board equal y?
    public boolean equals(Object y)
    {
        if (y == null) return false;
        if (y.getClass() != this.getClass()) return false;
        Board other = (Board) y;

        if (d != other.d) return false;
        for (int i = 0; i < d; i++)
            for (int j = 0; j < d; j++)
                if (blocks[i][j] != other.blocks[i][j]) return false;
        return true;
    }

    private Board move(int rowDelta, int colDelta)
    {
        byte [][]bytes = copy();

        int or = openRow + rowDelta;
        int oc = openCol + colDelta;

        byte tmp = bytes[openRow][openCol];
        bytes[openRow][openCol] = bytes[or][oc];
        bytes[or][oc] = tmp;

        return new Board(bytes, or, oc);
    }

    // all neighboring boards
    public Iterable<Board> neighbors()
    {
        Queue<Board> q = new Queue<Board>();
        if (openRow != 0)
            q.enqueue(move(-1, 0));
        if (openRow < d - 1)
            q.enqueue(move(1, 0));
        if (openCol != 0)
            q.enqueue(move(0, -1));
        if (openCol < d - 1)
            q.enqueue(move(0, 1));

        return q;
    }

    // string representation of the board
    public String toString()
    {
        String out = d+"\n";
        // out += "open      "+openRow+" "+openCol+"\n";
        // out += "goal      "+(isGoal() ? "OK" : "KO")+"\n";
        // out += "hamming   "+hamming()+"\n";
        // out += "manhattan "+manhattan()+"\n";
        for (int i = 0; i < d; i++)
        {
            for (int j = 0; j < d; j++)
                out += " "+(int) blocks[i][j];
            out += "\n";
        }
        return out; //.substring(0, out.length() - 1);
    }
}