Should be written in C++.

The overall objective of this exercise is to get familiar with the use of several data structures including arrays, linked lists, and stacks. The basic problem to be solved is what is commonly known as the Knight's Tour" problem among puzzle and chess enthusiasts. Briefly stated, the problem is to move the knight, beginning from any given square on the chess-board, successively to all 64 squares, touching each square once and only once. For a given initial position, the solution is represented by placing the numbers 0, 1,. 63 in an 8x8 array encoding the chessboard. The numbers placed in the array indicate the order in which the corresponding squares are visited One can write a recursive procedure to solve the above problem. However, you are required not to do that and you will not get credit for doing so. Instead, you should write an iterative procedure with 'back tracking involving a stack. The board state at each instant is an 8x8 array of integers all of whose elements are initially set at -1. As you move to a square, you replace the corresponding array element by the sequence number of the move made (such as 1 for the square visited after the first move, 2 for the second move etc.). At each instant the board state with any other necessary information is pushed on to the stack. This is to recover from the case when the knight is trapped somewhere, with no unvisited square to move to, without finding the complete solution. In such a case, you back-track along the traversed path by popping the states from the stack, until you find a square from which you can make a valid move. While back-tracking you should also unmark the the squares (i.e., put -1 at the orresponding elements of the current board state) so that you can visit those squares again If, at a particular instant, the knight's position on the board is given by (J), there may be at most eight possible moves for the knight which will move it to one of the squares (i 2j+ 11(i-1,/ +2)(i+1,/ +2), (i+2,/ +1)(i+2j-1(i+j-2)i-1j-21i-2,j -1). However, in some cases when the knight is located near the edge of the board, some of these moves are not valid since they may move the knight off the board. Also, remember that in the successful trajectory, the knight can visit a square only ou do not need to know this for implementing your project, but the procedure corresponds to a depth first search of a tree which is used to generate systematically (and laboriously) one path after another on the board until you find the correct path. If at every square you choose one move out of the available valid ones in a fixed simple manner (say, always the lowest numbered move), you will find that the program, for most of the initial conditions, takes an inordinate amount of time to terminate. (Satisfy yourself that this is the case). This is because there are too many possible paths to search through before the solution can be found. And there is a solution for every initial position of the knight. Can you guesstimate how many moves of the knight will be made in the worst case before the solution is found? If you cannot, do not worry, since we will develop the theory necessary for such estimation later in the course in the context of tree This combinatorial explosion problem associated with an exhaustive search process is a fundamental one that we encounter over and over again in Computer Science, particularly in the area of Artificial Intelligence. One of the approaches to overcome this is to develop heuristic rules, if possible, that The overall objective of this exercise is to get familiar with the use of several data structures including arrays, linked lists, and stacks. The basic problem to be solved is what is commonly known as the Knight's Tour" problem among puzzle and chess enthusiasts. Briefly stated, the problem is to move the knight, beginning from any given square on the chess-board, successively to all 64 squares, touching each square once and only once. For a given initial position, the solution is represented by placing the numbers 0, 1,. 63 in an 8x8 array encoding the chessboard. The numbers placed in the array indicate the order in which the corresponding squares are visited One can write a recursive procedure to solve the above problem. However, you are required not to do that and you will not get credit for doing so. Instead, you should write an iterative procedure with 'back tracking involving a stack. The board state at each instant is an 8x8 array of integers all of whose elements are initially set at -1. As you move to a square, you replace the corresponding array element by the sequence number of the move made (such as 1 for the square visited after the first move, 2 for the second move etc.). At each instant the board state with any other necessary information is pushed on to the stack. This is to recover from the case when the knight is trapped somewhere, with no unvisited square to move to, without finding the complete solution. In such a case, you back-track along the traversed path by popping the states from the stack, until you find a square from which you can make a valid move. While back-tracking you should also unmark the the squares (i.e., put -1 at the orresponding elements of the current board state) so that you can visit those squares again If, at a particular instant, the knight's position on the board is given by (J), there may be at most eight possible moves for the knight which will move it to one of the squares (i 2j+ 11(i-1,/ +2)(i+1,/ +2), (i+2,/ +1)(i+2j-1(i+j-2)i-1j-21i-2,j -1). However, in some cases when the knight is located near the edge of the board, some of these moves are not valid since they may move the knight off the board. Also, remember that in the successful trajectory, the knight can visit a square only ou do not need to know this for implementing your project, but the procedure corresponds to a depth first search of a tree which is used to generate systematically (and laboriously) one path after another on the board until you find the correct path. If at every square you choose one move out of the available valid ones in a fixed simple manner (say, always the lowest numbered move), you will find that the program, for most of the initial conditions, takes an inordinate amount of time to terminate. (Satisfy yourself that this is the case). This is because there are too many possible paths to search through before the solution can be found. And there is a solution for every initial position of the knight. Can you guesstimate how many moves of the knight will be made in the worst case before the solution is found? If you cannot, do not worry, since we will develop the theory necessary for such estimation later in the course in the context of tree This combinatorial explosion problem associated with an exhaustive search process is a fundamental one that we encounter over and over again in Computer Science, particularly in the area of Artificial Intelligence. One of the approaches to overcome this is to develop heuristic rules, if possible, that