public class Puzzle

{

    private int n;

    private int missingCellRow;

    private int missingCellCol;

    private int[][] cells;

    private int moves;

    private long startTimeMillis;


    public Puzzle(int n)

    {
        this.n = n;
        this.missingCellRow = n-1;
        this.missingCellCol = n-1;
        cells = new int[n][n];
        setCells();
        scramble();


    }


    public int getSize()

    {

        return n;

    }


    private void setCells()

    {
            for (int i=0; i<n*n; i++)
        {
            setCell(i, i+1);
        }
        setCell(missingCellRow*n+missingCellCol, -1);


    }


    public int getCell(int row, int col)
    {

        return cells[row][col];

    }


    public int getCell(int index)

    {

        return getCell(index/n, index%n);
    }


    public void setCell(int row, int col, int value)
    {

        cells[row][col] = value;

    }


    public void setCell(int index, int value)
    {

        setCell(index/n, index%n, value);
    }


    public int getMissingCellRow()

    {

        return missingCellRow;

    }


    public int getMissingCellCol()

    {

        return missingCellCol;

    }


    public boolean isCellMovable(int row, int col)
    {
        // corner cells
        if (missingCellRow == 0 && missingCellCol == 0)
        {
            return ((row==0 && col==1) || (row==1 && col==0));
        }
        else if (missingCellRow == 0 && missingCellCol == n-1)
        {
            return ((row==0 && col==n-2) || (row==1 && col==n-1));
        }
        else if (missingCellRow == n-1 && missingCellCol == 0)
        {
            return ((row==n-2 && col==0) || (row==n-1 && col==1));
        }
        else if (missingCellRow == n-1 && missingCellCol == n-1)
        {
            return ((row==n-2 && col==n-1) || (row==n-1 && col==n-2));
        }

        // side cells not at corners
        else if (missingCellRow == 0)
        {
            return ((row==0 && col==missingCellCol-1)
                || (row==0 && col==missingCellCol+1)
                || (row==1 && col==missingCellCol));
        }
        else if (missingCellRow == n-1)
        {
            return ((row==n-1 && col==missingCellCol-1)
                || (row==n-1 && col==missingCellCol+1)
                || (row==n-2 && col==missingCellCol));
        }
        else if (missingCellCol == 0)
        {
            return ((col==0 && row==missingCellRow-1)
                || (col==0 && row==missingCellRow+1)
                || (col==1 && row==missingCellRow));
        }
        else if (missingCellCol == n-1)
        {
            return ((col==n-1 && row==missingCellRow-1)
                || (col==n-1 && row==missingCellRow+1)
                || (col==n-2 && row==missingCellRow));
        }

        // rest of cells
        else
        {
            return ((row==missingCellRow-1 && col==missingCellCol)
                || (row==missingCellRow && col==missingCellCol-1)
                || (row==missingCellRow && col==missingCellCol+1)
                || (row==missingCellRow+1 && col==missingCellCol));
        }


    }


    public boolean isCellMovable(int index)
    {

        return isCellMovable(index/n, index%n);
    }


    public void move(int row, int col)

    {
        setCell(missingCellRow, missingCellCol, getCell(row, col));
        missingCellRow = row;
        missingCellCol = col;
        setCell(missingCellRow*n+missingCellCol, -1);
        moves++;


    }


    public void move(int index)

    {

        move(index/n, index%n);

    }


    public void scramble()

    {
        for (int i=0; i<n*n*n; i++)
        {
            int index;
            do
            {
                index = (int)(Math.random()*n*n);
            }
            while (!isCellMovable(index));
            move(index);
        }
        moves = 0;


    }


    public boolean isDone()

    {
         for (int index=0; index<n*n-1; index++)
         {
             if (getCell(index) != index+1)
                 return false;
         }
         return true;


    }


    public int getMoves()

    {

        return moves;

    }


    public void startTimer()

    {

        startTimeMillis = System.currentTimeMillis();
    }


    public String getElapseTime()

    {
        int seconds = (int) ((System.currentTimeMillis() - startTimeMillis) / 1000);
        int minute = seconds / 60;
        int second = seconds % 60;
        return minute+"' "+second+"''";


    }

}