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

import java.util.Iterator;
// import java.util.Collection;
// import java.util.ArrayDeque;

public class Solver
{
    private SearchNode sol0;
    private SearchNode sol1;
    private final MinPQ<SearchNode> pq0;
    private final MinPQ<SearchNode> pq1;
    private final RedBlackBST<String, Board> gameTree0;
    private final RedBlackBST<String, Board> gameTree1;

    private class SearchNode implements Comparable<SearchNode>
    {
        private final int moves;
        private final int fitness;
        private final SearchNode parent;
        private final Board board;
        private final String key;

        public SearchNode(Board b, SearchNode p, int n)
        {
            this.board = b;
            this.parent = p;
            this.moves = n;
            // this.fitness = n + b.hamming();
            this.fitness = n + b.manhattan();
            this.key = b.toString().replace(" ", "").replace("\n", "");
        }

        public String getKey()   { return key; }
        public int getFitness()   { return fitness; }
        public int getMoves()   { return moves; }
        public Board getBoard() { return board; }
        public SearchNode getParent() { return parent; }

        public int compareTo(SearchNode that)
        {
            if (this == that) return 0;
            if (this.fitness > that.fitness) return 1;
            else if (this.fitness < that.fitness) return -1;
            else return 0;
        }
    }

    private class SearchNodeIterator implements Iterator<SearchNode> {
        private SearchNode current;
        public SearchNodeIterator(SearchNode n) {
            current = n;
        }
        public boolean hasNext()    { return current.getParent() != null; }
        public void remove() { throw new UnsupportedOperationException();  }
        public SearchNode next() {
            if (!hasNext()) throw new java.util.NoSuchElementException();
            return current.getParent();
        }
    }

    // find a solution to the initial board (using the A* algorithm)
    public Solver(Board initial)
    {
        sol0 = null;
        sol1 = null;
        pq0 = new MinPQ<SearchNode>();
        pq1 = new MinPQ<SearchNode>();
        gameTree0 = new RedBlackBST<String, Board>();
        gameTree1 = new RedBlackBST<String, Board>();

        pq0.insert(new SearchNode(initial, null, 0));
        pq1.insert(new SearchNode(initial.twin(), null, 0));

        solve();
    }

    private boolean isKnown(SearchNode n, Board b)
    {
        SearchNode p = n.getParent();
        while (p != null)
        {
            if (b.equals(p.getBoard())) return true;
            p = p.getParent();
        }
        return false;
    }

    private void solve()
    {
        while ((sol0 == null) && (sol1 == null))
        {
            if (pq0.isEmpty() && pq1.isEmpty())
            {
                // StdOut.println("FAIL");
                break;
            }
            if (!pq0.isEmpty())
            {
                SearchNode n = pq0.delMin();
                Board b = n.getBoard();
                if (b.isGoal())
                {
                    sol0 = n;
                    break;
                }
                if (gameTree0.contains(n.getKey()))
                    continue;
                int m = n.getMoves() + 1;
                SearchNode p = n.getParent();
                if (p == null) {
                    for (Board nb : b.neighbors())
                        pq0.insert(new SearchNode(nb, n, m));
                }
                else {
                    Board pb = p.getBoard();
                    for (Board nb : b.neighbors())
                    {
                        if (!pb.equals(nb))
                            pq0.insert(new SearchNode(nb, n, m));
                    }
                }
                gameTree0.put(n.getKey(), b);
            }
            if (!pq1.isEmpty())
            {
                SearchNode n = pq1.delMin();
                Board b = n.getBoard();
                if (b.isGoal())
                {
                    sol1 = n;
                    break;
                }
                if (gameTree1.contains(n.getKey()))
                    continue;
                int m = n.getMoves() + 1;
                SearchNode p = n.getParent();
                if (p == null) {
                    for (Board nb : b.neighbors())
                        pq1.insert(new SearchNode(nb, n, m));
                }
                else {
                    Board pb = p.getBoard();
                    for (Board nb : b.neighbors())
                    {
                        if (!pb.equals(nb))
                            pq1.insert(new SearchNode(nb, n, m));
                    }
                }
                gameTree1.put(n.getKey(), b);
            }
        }
    }

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

    // min number of moves to solve initial board; -1 if no solution
    public int moves()
    {
        if (!isSolvable()) return -1;
        return sol0.getMoves();
    }

    // sequence of boards in a shortest solution; null if no solution
    public Iterable<Board> solution()
    {
        if (!isSolvable()) return null;

        Stack<Board> s = new Stack<Board>();
        SearchNode n = sol0;
        while (n != null)
        {
            s.push(n.getBoard());
            n = n.getParent();
        }
        return s;
    }

    // solve a slider puzzle (given below)
    public static void main(String[] args)
    {
        // Stopwatch w = new Stopwatch();
        // create initial board from file
        In in = new In(args[0]);
        int N = in.readInt();
        int[][] blocks = new int[N][N];
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                blocks[i][j] = in.readInt();
        Board initial = new Board(blocks);

        // solve the puzzle
        Solver solver = new Solver(initial);

        // print solution to standard output
        if (!solver.isSolvable())
            StdOut.println("No solution possible");
        else {
            StdOut.println("Minimum number of moves = " + solver.moves()+"\n");
            for (Board board : solver.solution())
                StdOut.println(board);
        }
        // StdOut.printf("Time: %f\n\n", w.elapsedTime());
    }
}