define recursion nqueens board adt the -queens board is used for positioning queens on square board for use in solving the -queens problem the board consists of squares arranged in rows and columnswith each square identified by indices in the range [ nqueensboardn )creates an empty board size()returns the size of the board numqueens()returns the number of queens currently positioned on the board unguardedrowcol )returns boolean value indicating if the given square is currently unguarded placequeenrow,col )places queen on the board at position (rowcolremovequeenrow,col )removes the queen from position (rowcolreset()resets the board to its original state by removing all queens currently placed on the board draw()prints the board in readable format using characters to represent the squares containing the queens and the empty squares using the adt given the adt definitionwe can now design recursive function for solving the -queens problem the function in listing takes an instance of the nqueens board adt and the current column in which we are attempting to place queen when called for the first timean index value of should be passed to the function the function begins by testing if solution has been found that is one of three base cases if no solution has been foundthen we must loop through the rows in the current column to find an unguarded square if one is founda queen is placed at that position (line and recursive call is made in an attempt to place queen in the next column upon return of the recursive callwe must check to see if solution was found with the queen placed in the square at position (row,colif solution was foundanother base case is reached and the function returns true if no solution was foundthen the queen in the current column must be picked up (line and another attempt made to place the queen within this column if all unguarded squares within the current column have been exhaustedthen there is no solution to the problem using the configuration of the queens from the previous columns in this casewhich represents the last base casewe must backtrack and allow the previous instance of the recursive function to try other squares within the previous column