TIFR CSE 2024 | Part B | Question: 12

Question

In the $n$-queens completion problem, the input is an $n \times n$ chess board with queens on some squares, and the goal is to determine if there is a way to place more queens so that the total number of queens is $n$ and no two queens attack each other (two queens are said to attack each other if they are on the same row, or they are on the same column, or they are on the same diagonal).

Consider the following statements:

1. The $n$-queens completion problem is decidable.
2. The $n$-queens completion problem is decidable in time $O\left(n^{n^{n}}\right)$.
3. The problem of "checking whether a given program solves the $n$-queens completion problem" is decidable.
4. The problem of "checking whether a given program solves the $n$-queens completion problem in time $O\left(n^{n^{n}}\right)$ " is decidable.
5. The problem of "checking whether a given program solves the $n$-queens completion problem" is decidable in time $O\left(n^{n^{n}}\right)$.

Which of the above is true?

• A. Only $\text{(i) and (ii)}$.
• B. Only $\text{(i) and (iii)}$.
• C. Only $\text{(i), (ii) and (iv)}$.
• D. Only $\text{(iii),(iv) and (v)}$.
• E. Only $\text{(i), (iii) and (iv)}$.

   

Answer 1

n-queens problem is solvable in $\mathcal{O}(N!)$

1 & 2.  $\mathcal{O}(N!) < \mathcal{O}(N^N) < \mathcal{O}(N^{N^N})$
3 & 5. It is basically halting problem which is undecidable.
4. Since there is a finite upper bound for computation, it is decidable