import java.util.*;

/**
 * This class extends Node to solve the Superqueens problem.
 */
class SuperqueensNode extends Node {

    /**
     * Superqueen positions are stored here.
     * If there's a superqueen at row i, column j,
     * then element i of this List will be equal to j.
     */
    private List<Integer> queenPositions;
    
    /**
     * Size of the board.
     */
    private int n;

    /**
     * Creates a starting search node with the specified board size.
     * 
     * @param n - the board size.
     * @return
     */
    public static SuperqueensNode createRootNode(int n) {
        return new SuperqueensNode(null, 0, new ArrayList<Integer>(), n);
    }

    /**
     * Creates a new instance of this class using the specified parent node,
     * g-value, queens position array, and the number of queens placed on the
     * board.
     * 
     * @param parent
     * @param gValue
     * @param board
     * @param nQueens
     */
    public SuperqueensNode(SuperqueensNode parent, double gValue, 
            List<Integer> queenPositions, int n) {
        super(parent, gValue);
        this.queenPositions = new ArrayList<Integer>(queenPositions);
        this.n = n;
    }

    /**
     * Returns true is we've put all the queens on the board.
     */
    public boolean isGoal() {
        // TODO: add your code here
        /*
         * Implementation notes:
         * Simply check if the number of elements in queenPositions is equal to the
         * board size.
         */
    }

    /**
     * Returns the heuristic value for this state.
     */
    public double evaluateHeuristic() {
        // TODO: add your code here
        /*
         * Implementation notes:
         * The heuristic should be based on the state configuration stored in
         * "queensPositions" (see the description of this variable above)
         * and the board size "n".
         * You may find the method "checkConflict" useful. See the method comment 
         * below.
         */
    }

    /**
     * Returns a list of the successor search nodes.
     */
    public List<SuperqueensNode> generateChildren() {
        // TODO: add your code here.
        /*
         * Implementation notes:
         * 1. Create an empty list of successor nodes.
         * List<SuperqueensNode> children = new ArrayList<SuperqueensNode>();
         * 2. For each successor node, whose queen positions are stored, say, in 
         * a list "childQueens" and g-value stored in "childG", call
         * children.add(new SuperqueensNode(this, childG, childQueens, n));
         * 3. Return "children".
         */
    }

    /**
     * Checks whether queens at positions (x1,y1) and (x2,y2) conflict. Returns
     * true if they're on the same row, diagonal, or within one knight's move.
     */
    private static boolean checkConflict(int x1, int y1, int x2, int y2) {
        // assume that y1 < y2

        // check same row
        if (x1 == x2)
            return true;

        // check knight's move
        if (Math.abs(x1 - x2) + Math.abs(y1 - y2) == 3)
            return true;

        // check diagonal move
        if (Math.abs(x1 - x2) == Math.abs(y1 - y2))
            return true;

        return false;
    }

    /**
     * Returns a String representation of this node. The representation is the
     * board showing the queens' positions.
     */
    public String toString() {
        StringBuffer sb = new StringBuffer();
        // sb.append("value " + getGValue() + "\n");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (j < queenPositions.size() && queenPositions.get(j) == i) {
                    sb.append("Q");
                } else {
                    sb.append(".");
                }
            }
            sb.append("\n");
        }
        return sb.toString();
    }

    /**
     * Prints out the solution, assuming that this node is the goal node. This
     * method prints the board state (showing the queens' positions) and the
     * number of conflicts on the board.
     */
    public int printSolution() {
        System.out.println(this.toString());
        System.out.println("Number of conflicts: " + (int) getGValue());
        return n;
    }
}