It's currently solved for up to N=27
Both 26 and 27 solutions came from supercomputers/FPGAs and took months of compute time.
The N-Queens completion problem is NP-hard
21–30 of 57 posts
Re: The N-Queens completion problem is NP-hard
#22What 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?
You have to be P=NP fast. ;)
Re: The N-Queens completion problem is NP-hard
#23What 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?
If you can solve it at all for even 50x50 would mean a revolution in certain algorithmic fields.
Re: The N-Queens completion problem is NP-hard
#24The article completely misinterprets the press release[1]. The University of St Andrews isn't offering a prize; they've just shown that the Queens puzzle on an n-by-n board (EDIT: actually, the n Queens completion puzzle) is NP-hard. (By the way, even the press release, though less wrong than the article, is still pretty bad: apparently NP-complete problems are hard because they use "backtracking". Also it seems to s…
If I'm reading it right, they haven't shown that the N Queens problem is NP-hard, but rather that the N Queens completion problem is NP-hard.
Ok we'll change the title to that above.
Re: The N-Queens completion problem is NP-hard
#25[deleted]
Re: The N-Queens completion problem is NP-hard
#26Thanks for telling me that :)
Re: The N-Queens completion problem is NP-hard
#27The article completely misinterprets the press release[1]. The University of St Andrews isn't offering a prize; they've just shown that the Queens puzzle on an n-by-n board (EDIT: actually, the n Queens completion puzzle) is NP-hard. (By the way, even the press release, though less wrong than the article, is still pretty bad: apparently NP-complete problems are hard because they use "backtracking". Also it seems to s…
'Completely' even is an understatement, given https://en.wikipedia.org/wiki/Eight_queens_puzzle#Explicit_s....
Re: The N-Queens completion problem is NP-hard
#28What 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?
The time it takes to solve needs to grow at most polynomially with the length of the representation of the input.
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.
Re: The N-Queens completion problem is NP-hard
#29Earlier quoted context omitted.
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.
Actually the queens problem starting with an empty board is not NP-Hard. See: https://cstheory.stackexchange.com/questions/12682/is-the-n-... The "completion" problem is the NP-Hard one. As one of the other comments noted, the paper behind this press release is about the completion problem.
That's just a good heuristic, though, it does not guarantee finding a solution. Also note that NP is a class of decision problems, and finding a solution for the n-Queens problem is not.
None of the two decision problems that arise naturally from n-queens, deciding whether there exists solutions for a given board size, and verifying whether a candidate is indeed a solution, are NP-hard (solutions exist for n \not\in {2, 3}; verification can clearly be done in time quadratic in n). Counting solutions is #P-complete, though.
Re: The N-Queens completion problem is NP-hard
#30The article completely misinterprets the press release[1]. The University of St Andrews isn't offering a prize; they've just shown that the Queens puzzle on an n-by-n board (EDIT: actually, the n Queens completion puzzle) is NP-hard. (By the way, even the press release, though less wrong than the article, is still pretty bad: apparently NP-complete problems are hard because they use "backtracking". Also it seems to s…
Phys.org is a dumpster fire, and ANY information from there is better linked to from another source, of which there are many. I recommend the AAAS sites www.eurekalert.com and www.sciencemag.com. As well as Nature. At least then you'll have doi links, and a better class of journalism.