1. Program 9 Instructions, CS102, Prof. LoftinDue Monday, November 23, 2009In chess, a knight can move in eight possible directions: From posi-tion (i, j) for 0 ≤ i, j ≤ 7, the knight can move to one of the positions(i + 2, j + 1), (i + 2, j − 1), (i + 1, j + 2), (i + 1, j − 2), (i − 1, j + 2), (i −1, j − 2), (i − 2, j + 1), (i − 2, j − 1). So if K represents the knight, thepossible positions it can move to are given by an x:. . . . . . . .. . . . . . . .. . x . x . . .. x . . . x . .. . . K . . . .. x . . . x . .. . x . x . . .. . . . . . . .Write a class KnightsTour.java which uses a recursive algorithmto find a knight’s tour on the chessboard. This means that, startingfrom the (0, 0) position (the upper left corner), the knight should makemoves to visit all the positions of the chessboard exactly once. Here isthe output of my program for an 8x8 chessboard:1 12 9 6 3 14 17 2010 7 2 13 18 21 4 1531 28 11 8 5 16 19 2264 25 32 29 36 23 48 4533 30 27 24 49 46 37 5826 63 52 35 40 57 44 4753 34 61 50 55 42 59 3862 51 54 41 60 39 56 43This tour represents the order in which the squares on the chessboardare visited, 1 through 64.2. How to do itIt is useful to have a global constant representing the size of theboard (it is useful in debugging to work with smaller examples). Thesmallest square board on which there is a knight’s tour is 5x5.private final static int BOARD_SIZE = 8;The other global data structures I used in my solution areprivate int[][] board;private int num; // current knight to be placed12The board array will contain an integer for the correct number of theknight’s move (from 1 to BOARD SIZE * BOARD SIZE), and a zero if theknight has not yet moved there in the current tour.The main method should initialize a new instance of the class KnightsTourand begin the recursion at position (0, 0), and may contain similar codeto the following:KnightsTour K = new KnightsTour();if (K.tour(0,0))System.out.println(K);elseSystem.out.println("No knight’s tour possible on a " +BOARD_SIZE + " x " + BOARD_SIZE + " board.");Use the constructor to set up the board array and initialize num. Theprimary recursive method may look like this:private boolean tour (int row, int column)It should return true if there is a tour going forward placing the cur-rent knight at place (row,column). Its format should be similar to therecursive method in the Maze class from Lewis & Loftus discussed inlecture. In particular, it will be useful to have a boolean variable doneto signify whether the knight’s tour has been found.Things you should address:• How to update num?• How to place a knight on the board?• How to remove a knight from the board (when backtracking)?• How to check if placing a knight at (row,column) is valid? (It’snot valid if you land off the chessboard, and also if this positionhas already been visited in the current tour.)• What is the base case of the recursion? How do you checkwhether the tour is complete?• How to perform the next move of the knight? The code withthe recursive method calls (eight in all, corresponding to theeight possible moves of the knight) should be structured likethe recursive calls in Maze.java.You should also write an appropriate toString() method.3. How to turn it inTurn a stand-alone Java class called KnightsTour.java to me byemailing it, as an attachment, to [email protected]. Due dateNovember 23, 2009.5. Hints on debuggingSet the BOARD SIZE to a small number (4 will be OK for the recursion,though you have to go to at least 5 to get a successful knight’s tour).Write in an extra print statement to print out the board whenever itis updated (either by placing a new knight or by removing an old one).This way, you should be able to tell what your code may be doingwrong in a case you can work out by hand.**VERY IMPORTANT** Comment out your extra print statementsbefore handing your program in, and set the BOARD SIZE to