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

public class NQueensSolver {
 
    private class Choice {
      
       private int c; // This variable should be the column for the queen placed.  
		      // Note, the state will be represented by a stack,  which will 
		      // grow as choices are made for rows 0 and up.
		      // As such, the row associated with the choice can be inferred,
		      // and need not be stored explicitly 

       //////////////////////////////////////////////////////////// 
       // ADD APPROPRIATE CONSTRUCTORS AND INSTANCE METHODS HERE // 
       //////////////////////////////////////////////////////////// 
    }
    
    private class State implements StateAllowingBacktracking<Choice> {
       
        private Stack<Choice> choicesMade; // Interpret this so that the choice at the bottom of the stack 
                                           // gives the column for the queen in first row, the choice next
                                           // up the stack gives the column for the queen in the second row, etc.

        ////////////////////////////////////////////////////////////
        // ADD APPROPRIATE CONSTRUCTORS AND INSTANCE METHODS HERE // 
        ////////////////////////////////////////////////////////////

        public String toString() {
            String s = "";
            for (Choice choice : choicesMade) {
                s += choice + System.lineSeparator();
            }
            return s;
        }
    }
    
    private int boardSize;
    private StateAllowingBacktracking<Choice> state;
    private static int solutionsFound;

    // Do not add any more instance variables to the NQueensSolver class //
    
    public NQueensSolver(int boardSize) {
        this.boardSize = boardSize;
        state = new State();
    }
    
    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);
    }
}