The N-Queens completion problem is NP-hard
atlasobscura.com
The N-Queens completion problem is NP-hard
1–10 of 57 posts
Re: The N-Queens completion problem is NP-hard
#2The million-dollar prize just appears to be the Clay Institute's prize for solving P vs NP. I am guessing that the queens problem (a special case of maximum independent set in a graph) is NP-Hard.
Re: The N-Queens completion problem is NP-hard
#3[deleted]
Re: The N-Queens completion problem is NP-hard
#4You can also claim the $1 million by being good at Mario and explaining your techniques:
Re: The N-Queens completion problem is NP-hard
#5ahh nqueens, this was my first real parallel program that I did using mpi
Re: The N-Queens completion problem is NP-hard
#6The million-dollar prize just appears to be the Clay Institute's prize for solving P vs NP. I am guessing that the queens problem (a special case of maximum independent set in a graph) is NP-Hard.
[deleted]
Re: The N-Queens completion problem is NP-hard
#7The million-dollar prize just appears to be the Clay Institute's prize for solving P vs NP. I am guessing that the queens problem (a special case of maximum independent set in a graph) is NP-Hard.
Damn it. I didn't know it's NP hard. I thought I would discover the generating function for the number of possible solutions for board sized N.
Re: The N-Queens completion problem is NP-hard
#8You can also claim the $1 million by being good at Mario and explaining your techniques: https://arxiv.org/abs/1203.1895
Only if you are provably, mathematically good at Mario. Not just you seem to do well over the course of a measly billion games of.
Re: The N-Queens completion problem is NP-hard
#9What you is fast in this case? If you can solve 1,000 x 1,000 in say 1 minute is that fast? Or do you need to solve 1,000,000 x 1,000,000 in a second?
Re: The N-Queens completion problem is NP-hard
#10The million-dollar prize just appears to be the Clay Institute's prize for solving P vs NP. I am guessing that the queens problem (a special case of maximum independent set in a graph) is NP-Hard.
Damn it. I didn't know it's NP hard. I thought I would discover the generating function for the number of possible solutions for board sized N.
Counting solutions is not a decision problem, so it can't be in NP. The corresponding counting complexity class is #P.