The input is just a single number. So grow polynomial from N x N board size?

I really don't get how this is equivalent to NP.

You either read the earlier version before it was corrected, or you're misunderstanding. The problem is not the N-Queens problem, it's the N-Queens /completion/ problem. The problem is this:

Here's an NxN board with k queens already placed. Is there a way to place another N-k queens so they are all mutually non-attacking?

Most instances will be easy, but current algorithms to solve this are such that for each N, the time taken in the worst case is an exponential function of N.

Ahh, thanks it looks like it was changed after I read it.