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

public class LatinSquareFinder {
    
    private class Choice {
        
        ///////////////////
        // ADD CODE HERE //
        ///////////////////
    }
    
    public class State implements StateAllowingBacktracking<Choice> {
        
        ///////////////////
        // ADD CODE HERE //
        ///////////////////
        
    }
    
    private StateAllowingBacktracking<Choice> state;
    private static int solutionsFound;
    
    public LatinSquareFinder(int size) {
        state = new State(size);
    }
    
    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 gridSize = scanner.nextInt();
        scanner.close();
        
        LatinSquareFinder finder = new LatinSquareFinder(gridSize);
        finder.searchFromCurrentState();
        
        System.out.println("Solutions Found: " + solutionsFound);
    }
}