How to write recurrence relation for backtracking problem?
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.