import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;

public class NQueensSolver {
    
    ///////////////////
    // INNER CLASSES //
    ///////////////////
    
    private class Choice {
        
        private int c;
        
        public Choice(int c) {
            this.c = c;
        }
        
        public boolean equals(Object o) {
            return (o != null) && (o instanceof Choice) && ((Choice) o).c == this.c;
        }
        
        public int col() {
            return c;
        }
        
        public String toString() {
            String s = "";
            for (int i = 0; i < NQueensSolver.this.boardSize; i++) 
                s += (c == i ? "Q " : "* ");
            return s;
        }
    }
    
    private class State implements StateAllowingBacktracking<Choice> {
        
        private Stack<Choice> choicesMade;
        
        public State() {
            this.choicesMade = new Stack<Choice>();
        }
        
        public String toString() {
            String s = "";
            for (Choice choice : choicesMade) {
                s += choice + System.lineSeparator();
            }
            return s;
        }
        
        private int numQueensPlaced() {
            return this.choicesMade.size();
        }
        
        public boolean isSolution() {
            return numQueensPlaced() == NQueensSolver.this.boardSize;  // we could just use "boardSize" here,
        }                                                              // but this avoids any ambiguity
        
        private boolean sameColumnAsPrevQueen(Choice choice) {
            for (Choice prevChoice : choicesMade) {
                if (choice.equals(prevChoice)) return true;
            }
            return false;
        }
        
        private boolean sameDiagonalAsPrevQueen(Choice choice) {
            for (int r = 0; r < choicesMade.size(); r++) {
                int c = choicesMade.get(r).col();
                int row = choicesMade.size();
                int col = choice.col();
                if ((r-row == c-col) || (row-r == c-col)) return true;
            }
            return false;
        }
        
        public List<Choice> nextChoicesToConsider() {
            
            List<Choice> listOfChoices = new ArrayList<Choice>();
            for (int c = 0; c < NQueensSolver.this.boardSize; c++) {
                listOfChoices.add(new Choice(c));
            }

            return listOfChoices;
        }
        
        public boolean isValid(Choice choice) {
            // returns false when the choice is invalid or otherwise undesirable
            // (false-returning choices will "prune" the search tree)
            return (! sameColumnAsPrevQueen(choice)) && (! sameDiagonalAsPrevQueen(choice));
        }
        
        public void makeChoice(Choice choice) {
            choicesMade.push(choice);
        }
        
        public void undoChoice(Choice choice) {
            choicesMade.pop();
        }
    }
    
    ////////////////////////
    // INSTANCE VARIABLES //
    ////////////////////////
    
    private int boardSize;
    private StateAllowingBacktracking<Choice> state;
    private static int solutionsFound;
    
    /////////////////
    // CONSTRUCTOR //
    /////////////////
    
    public NQueensSolver(int boardSize) {
        this.boardSize = boardSize;
        state = new State();
    }
    
    //////////////////////
    // INSTANCE METHODS //
    //////////////////////
    
    public void searchFromCurrentState() {
        
        if (state.isSolution()) {
            reactToSolution();
            return; // stop pursuing this path
        }
        
        for (Choice choice : state.nextChoicesToConsider()) {
            if (state.isValid(choice)) {
                state.makeChoice(choice);
                searchFromCurrentState();  // <-- the recursive call!
                state.undoChoice(choice);  // try another path
            }
        }
    }
    
    private void reactToSolution() {
        System.out.println(state);
        solutionsFound++;
    }
    
    public static void main(String[] args) {
        System.out.println("Enter board size to solve:");
        Scanner scanner = new Scanner(System.in); 
        int boardSize = scanner.nextInt();
        scanner.close();
        
        NQueensSolver solver = new NQueensSolver(boardSize);
        solver.searchFromCurrentState();
        
        System.out.println("Solutions Found: " + solutionsFound);
    }
}