N queen time complexity issue

#1

what is the recursive relation and time complexity of n-queen problem…how is it derived?
what is the space complexity in backtracking solution?

#2

Hi @Rj.25,
N queen problem is a backtracking problem. There isn’t any recurrence relation as such. It just involve placing a queen at a specific position then moving on to next row and repeating the steps until we find there is no way we can place the queen in the current row. If such a case arrives, we backtrack and select a different position for the queen in the last row.
The space complexity in n^2 and time complexity is O(n!).
there are n ways to place quuen in first row, n-1 to place in second row, n-3 in 3rd and so on. Hence the time complexity can be roughly scene as O(n!)=O(n* n-1* n-2*…* 2* 1).
Hope dis resolves ur doubt.

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.