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> {

        private int[][] board;
        private int currentX,currentY;
        private int countOfMovesMade;

        public State(int boardSize) {
            this.board = new int[boardSize][boardSize];
            currentX = 0;
            currentY = 0;
            board[currentX][currentY] = 1;
            countOfMovesMade = 1;
        }

        private int boardSize() {
            return this.board.length;
        }
        
        public String toString() {  
            String s = "";
            for (int r = 0; r < this.boardSize(); r++) {
                for (int c = 0; c < this.boardSize(); c++) {
                    s += this.board[r][c] + "\t";
                }
                s += System.lineSeparator();
            }
            return s;
        }

        public boolean isSolution() { 
            return (countOfMovesMade == boardSize()*boardSize());   
        }

        public List<Choice> nextChoicesToConsider() {
            List<Choice> listOfChoices = new ArrayList<Choice>();
            for (int i = 0; i < 8; i++)
            listOfChoices.add(new Choice(i));
            return listOfChoices;
        }

        public boolean isValid(Choice choice) {
            int dx = Choice.MOVES[choice.move][0];
            int dy = Choice.MOVES[choice.move][1];
            int newX = currentX + dx;
            int newY = currentY + dy;
            return (newX >= 0) && (newX < this.boardSize()) && (newY >= 0) && (newY < this.boardSize()) && (board[newX][newY] == 0);
        }

        public void makeChoice(Choice choice) {
            int dx = Choice.MOVES[choice.move][0];
            int dy = Choice.MOVES[choice.move][1];
            this.currentX = currentX + dx;
            this.currentY = currentY + dy;
            countOfMovesMade++;
            board[currentX][currentY] = countOfMovesMade;
        }

        public void undoChoice(Choice choice) {
            board[currentX][currentY] = 0;
            int dx = Choice.MOVES[choice.move][0];
            int dy = Choice.MOVES[choice.move][1];
            this.currentX = currentX - dx;
            this.currentY = currentY - dy;
            countOfMovesMade--;
        }
    }

    private State 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();
    }
}