3 ms·

Please note that the linear solution to N-Queens is only giving a single solution for a board. If I remember right, there is a number of similar linear-time so

• ahelwer 14y ago
  Polynomial time with respect to what? The number of possible solutions grows exponentially with respect to the board size.
• Someone 14y ago
  http://oeis.org/A000170 http://oeis.org/A000170 hints that there is no such algorithm: "Strong conjecture : there is a constant c around 2.54 such that a(n) is asymptotic to n!/c^n" That would imply that a(n) grows faster than polynomial. That, in turn, would mean that merely counting the number of solutions cannot be done in polynomial time. N-Queens, by the way, becomes simple once you realize that you cannot have two queens at (p,q) and (r,s) if any of the following is true: p = r q = s p-q = r-s p+q = r+s (The first two check for horizontal and vertical attacks, last two for diagonal ones) Real programmers implement Knuth's dancing links (http://arxiv.org/pdf/cs.DS/0011047.pdf http://arxiv.org/pdf/cs.DS/0011047.pdf) and use it to solve a way larger class of problems.
• swannodette 14y ago
  http://en.wikipedia.org/wiki/Exact_cover http://en.wikipedia.org/wiki/Exact_cover