The following is an algorithm nQueens that takes as input a list partialSolution and a positive integer n, the dimension of the nn chessboard, and for prints all solutions to the n-Queens problem using backtracking. Function nQueens(partialSolution, n) { positions = getPositions(partialSolution, n) If positions is empty { If length(partialSolution) ==n { print(partialSolution) } } Else { For each element in positions { push(element, partialSolution) nQueens(partialSolution, n) pop(partialSolution) } } }

Write a program in Python that takes as input a positive integer n and prints all possible solutions to the n-Queens problem. Your program should use backtracking.

For example, your program may output: Enter value for n: 4 Solutions ------------ [1, 3, 0, 2] [2, 0, 3, 1] ------------ and Enter value for n: 2 Solutions