The n-queens puzzle accepts a positive integer n and returns whether it is possible to place n queens on an n n chess board so that no queen is directly horizontal, vertical, or diagonal of another queen (in other words, the queens do not threaten each other). Prove that n-queens is an NP problem in questions 5 and 6.

5. Give pseudocode for a polynomial-time verification algorithm for n-queens.

6. Find the worst-case complexity for your verification algorithm.