import java.util.*;

public class knights_tour_1{

    private Square[][] arr;
    private int k = 1;

    public static void main(String[] args) {
        knights_tour_1 l = new knights_tour_1(8);
        l.calc(1,1);
        l.print();

    }

    public void calc(int x, int y){

            arr[x-1][y-1].setTouched(k);
            k++;

            //use get possible moves method
            int[][] possibleMoves = getPossibleMoves(x,y);

            if(possibleMoves.length <= 0) return;

            //randomly selected possible move
            Random r = new Random();
            int random = r.nextInt(possibleMoves.length);



            //recursivel call calc(newX,newY)
            calc(x + possibleMoves[random][0],y + possibleMoves[random][1]);


    }

    //this method gets the availale positions the knight can jump to
    //if the knight is at a position x,y
    public int[][] getPossibleMoves(int x, int y){

        //list all possible moves
        int[][] possibleMoves = new int[][]{ {1,-2}, {2,-1}, {-1,-2}, {-2,-1}, {1,2}, {2,1}, {-1,2}, {-2,1} };

        //stores the indexes of the moves the knight can jump to. for example, if the knight can go x=-1 and y=2 or x=1 and y=2
        //the moveIndexes array will contain numbers 0 and 4
        ArrayList<Integer> moveIndexes = new ArrayList<Integer>();

        for(int i = 0; i < possibleMoves.length; i++){
            if(inBounds(x + possibleMoves[i][0]-1, y + possibleMoves[i][1]-1)){
                if(arr[x+possibleMoves[i][0]-1][y+possibleMoves[i][1]-1].isOpen()){
                    moveIndexes.add(i);
                }
            }
        }

        int[][] availableMoves = new int[moveIndexes.size()][2];
        for(int i = 0; i < availableMoves.length; i++){
            availableMoves[i] = possibleMoves[moveIndexes.get(i)];
        }
            //randomly selected possible move

        return availableMoves;


    }

    //n = width/height
    public knights_tour_1(int n){
        arr = new Square[n][n];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                arr[i][j] = new Square();
            }
        }

    }

    private boolean inBounds(int i, int j){
        if( i < arr.length && i > -1){
            if(j < arr.length && j > -1){
                return true;
            }
        }
        return false;
    }

    public void print(){
        for(int i = 0; i < arr.length; i++){
            for(int j = 0; j < arr.length; j++){
                System.out.print(arr[i][j] + " ");
            }
            System.out.print("\n");
        }
    }



    class Square{

        boolean touched;
        int touchNum = 0;


        Square(){
            this.touched = false;
        }


        void setTouched(int k){
            touched = true;
            touchNum = k;
        }

        boolean isOpen(){
            return !touched;
        }

        public String toString(){
            return "" + touchNum;
        }

    }
}