Implement the n-queens algorithm specified in figure 2.2 in a program named NQueens.java or nqueens.py. This will contain the PlaceQueens method given in the figure and a main method that:

• Prompts for a positive integer, which is the number of queens
• Declares and initializes the Q array
• Calls the PlaceQueens method
• Prints the Boolean return value from PlaceQueens. If it returns true, it should also print the Q array, which specifies the column where the queen on each row should be placed.

This is the figure

for j PLACEQUEENS(Q[1..n),r): if r=n+1 print Q[1..n] else 1 to n legal TRUE for ir 1 to s 1 if (Q[i]=j) or (Q[i]=j+r-i) or (Q[i]=j-s+i) legal FALSE if legal Q[r]- j PLACEQUEENS(Q[1..n],r+1) (Recursion!>> Figure 2.2. Gauss and Laquire's backtracking algorithm for the n queens problem. for j PLACEQUEENS(Q[1..n),r): if r=n+1 print Q[1..n] else 1 to n legal TRUE for ir 1 to s 1 if (Q[i]=j) or (Q[i]=j+r-i) or (Q[i]=j-s+i) legal FALSE if legal Q[r]- j PLACEQUEENS(Q[1..n],r+1) (Recursion!>> Figure 2.2. Gauss and Laquire's backtracking algorithm for the n queens