3 ms·
The time it takes to solve needs to grow at most polynomially with the length of the representation of the input.
by umanwizard 9y ago
The time it takes to solve needs to grow at most polynomially with the length of the representation of the input.
- Retric 9y agoThe 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.
- pg_is_a_butt 9y agowow... if you don't get it, then P=NP. you did it. you're all idiots.
- CarolineW 9y agoYou 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.
- Retric 9y agoAhh, thanks it looks like it was changed after I read it.