Please Use this template to complete this program.

#include #include using namespace std; bool test(int q[], int c) { //same ok function from 1D 8 Queens } int main() { for (int n = 1; n  
 
  The n queens problem By the "n queens problem" we mean the problem of placing n queens on an nXn "chessboard" in such a way that no queen can capture any other on the next move. In class we solved the "8 queens" problem. Write a function that inputs an integer n and returns the number of solutions to the "n queens" problem. Your function should use the one dimensional representation for the board, the algorithm we discussed in class, and no gotos. Test your function with a main program that prompts the user for an integer n. The main program then calls the function n times, once for each number from 1 -n, and then prints the number of solutions to each of these problems, one on a line For example, if you enter n-5 your program should output 1. There are 2-There are- 3There are 4. There are_ 5. There are so solutions to the 1 queens problem. lutions to the 2 queens problem. lutions to the 3 queens problem solutions to the 4 queens problem. lutions to the 5 queens problem Now, since each time through the loop you will need an array q of a different length, you will need to allocate the array off of the heap (which we mentioned in class) and not the run-time stack. To do this you use the "new operator" to request the heap to dynamically allocate the memory for you. For example, to get a one dimensional array of integers of size n and called q, we use the following syntax: int* q = new int[n]; This allocates the array for us dynamically, at run-time. After this we can use the array q just as if it had been declared normally" and it has n elements denoted q[0] through q[n-1]