1
$\begingroup$

I am not able to understand how to write a recurrence relation for n queen problem. I searched on web and everywhere it was given directly without explaining how can we arrive to that. Recurrence relation is for n*n board $T(n)=n*T(n-1)+O(n^2)$ but think it should be $T(n)=T(n-1)+O(n^2)$ as if we put the queen anywhere in first row, we are left with $(n-1)*(n-1)$ board and it is sub-problem for T(n-1). But how n gets multiplied is not understandable. Can anyone help in explaining such recurrence relation.

$\endgroup$
1
$\begingroup$

Recurrence relation is for n*n board $T(n)=n*T(n-1)+O(n^2)$ but think it should be $T(n)=T(n-1)+O(n^2)$ as if we put the queen anywhere in first row, we are left with $(n-1)*(n-1)$ board and it is sub-problem for T(n-1). But how n gets multiplied is not understandable.

How many cells are there in the first row? $n$. That is where the factor $n$ come from.

  • We put the Queen in the first cell of the first row. Removing the first row and first column, we then check the remaining $(n-1)*(n-1)$ board.
  • We put the Queen in the second cell of the first row. Removing the first row and second column, we then check the remaining $(n-1)*(n-1)$ board.
  • $\vdots$
  • We put the Queen in the last cell of the first row. Removing the first row and last column, we then check the remaining $(n-1)*(n-1)$ board.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.