Now number of possible arrangements of $N$ Queens on $N \times N$ chessboard is $N!$, given you are skipping row or column, already having a queen placed. So average and worst case complexity of the solution is $O(N!)$ (since, you are checking all the possible solutions i.e. $N^N$ arrangements). The best case occurs if you find your solution before exploiting all possible arrangements. This depends on your implementation.
And if you need all the possible solutions, the best, average and worst-case complexity remains $O(N!)$
(Note: none of the other answers (or links on them) on the link above help in my understanding)
I don't understand this at all.
Surely the total number of possible arrangements (not the total number of solutions) for the $8$ Queens - assuming we have an 8x8 board (hence $N=8$) - will be
$64\cdot 63\cdot 62\cdot 61\cdot 60\cdot 59\cdot 58\cdot 57$
...based on what I learned from a similar problem (number of seating arrangements), which gives me a far, far greater value than $N^N$???