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

public class KnightsTourSolver {

    private class Choice {
        
        private final static int [][] MOVES = {{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1}};

        int move;
        
        public Choice(int move) {
            this.move = move;
        }

    }

    private class State implements StateAllowingBacktracking<Choice> {

        ///////////////////
        // ADD CODE HERE //
        ///////////////////
        
    }

    private StateAllowingBacktracking<Choice> state;
    static private int numSolutionsFound;

    public KnightsTourSolver(int boardSize) {

        this.state = new State(boardSize);
        KnightsTourSolver.numSolutionsFound = 0;
    }

    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() {
        numSolutionsFound++;
        System.out.println("Solution " + numSolutionsFound + System.lineSeparator() + state);
    }

    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();

        KnightsTourSolver finder = new KnightsTourSolver(boardSize);
        finder.searchFromCurrentState();
    }

}