The article completely misinterprets the press release[1].<p>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.<p>(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 suggest that this is something computer programmers would solve, rather than mathematicians...)<p>[1]: <a href="https://phys.org/news/2017-09-simple-chess-puzzle-key-1m.html#jCp" rel="nofollow">https://phys.org/news/2017-09-simple-chess-puzzle-key-1m.htm...</a>
Completely off-topic: As a one-time civil engineer, mathematical dullard, and frequent New York visitor, who is losing his mind, I thought this was about completing a subway line. In my defense, the N train does go to Queens (though it's not called the N-Queens), and everybody knows completing a subway line is a really hard problem, especially if you're following the story of the new 2nd Ave line.
The 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.
It's currently solved for up to N=27<p>Both 26 and 27 solutions came from supercomputers/FPGAs and took months of compute time.<p><a href="http://www.nqueens.de/sub/WorldRecord.en.html" rel="nofollow">http://www.nqueens.de/sub/WorldRecord.en.html</a>
You can also claim the $1 million by being good at Mario and explaining your techniques:<p><a href="https://arxiv.org/abs/1203.1895" rel="nofollow">https://arxiv.org/abs/1203.1895</a>
Is there a proof somewhere which states that all NP hard problem can have a similar / generic solution?<p>I find it more likely that the N-Queens problem will have a very specific solution