1 of 2 136.613 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 corresponding 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 (ij), there may be at most eight possible moves for the knight which will move it to one of the squares (i - 2j + 1)(i-1,j +2),(i+1,j +2),(i+2,j +1),(i+2j-1),(i+1j-2),(i-1j -2),(i-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 once You do not need to know this for implementing your project, but the procedure corresponds to a depth 1 of 2 136.613 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 corresponding 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 (ij), there may be at most eight possible moves for the knight which will move it to one of the squares (i - 2j + 1)(i-1,j +2),(i+1,j +2),(i+2,j +1),(i+2j-1),(i+1j-2),(i-1j -2),(i-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 once You do not need to know this for implementing your project, but the procedure corresponds to a depth