What's the order class of T(n) = n(T(n−1) + n) with T(1)=1? This recurrence basically comes from the typical solution to N-queens problem. Some people say the complexity is O(n) while giving recurrence T(n) = n(T(n−1) + n). But from what I can tell, this concludes O((n+1)!), which is surely different from O(n!) asymptotically.
By induction,
If T(k) <= ck!,
Then, T(n) <= n*c(n-1)! + n*n = cn! + n*n. Thus we don't have T(n) <= cn!.
On the other hand, 
If T(k) <= c(k+1)!,
Then, T(n) <= n*cn! + n*n <= n*cn! + cn! = c(n+1)!.
Is this correct? If so, what's the correct way to prove it(other ways than induction is also OK)?

Let $U(k)=\frac{T(k)}{k!}$.  Then 
$$U(n)=U(n-1)+\frac{n}{(n-1)!}=U(n-1)+\frac1{(n-1)!}+\frac1{(n-2)!}\\
<U(1)+2e-1\\
T(n)<2e(n!)$$
