# How to write recurrence relation for backtracking problem?

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.

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.