SoylentNews is people
SoylentNews
Researchers at the University of St Andrews have thrown down the gauntlet to computer programmers to find a solution to a "simple" chess puzzle which could, in fact, take thousands of years to solve and net a $1M prize. Computer Scientist Professor Ian Gent and his colleagues, at the University of St Andrews, believe any program capable of solving the famous "Queens Puzzle" efficiently, would be so powerful, it would be capable of solving tasks currently considered impossible, such as decrypting the toughest security on the internet.
Devised in 1850, the Queens Puzzle originally challenged a player to place eight queens on a standard chessboard so that no two queens could attack each other. This means putting one queen in each row, so that no two queens are in the same column, and no two queens in the same diagonal. Although the problem has been solved by human beings, once the chess board increases to a large size no computer program can solve it.
The team found that once the chess board reached 1000 squares by 1000, computer progams could no longer cope with the vast number of options and sunk into a potentially eternal struggle akin to the fictional "super computer" Deep Thought in Douglas Adams' Hitchhiker's Guide to the Galaxy, which took seven and a half million years to provide an answer to the meaning of everything.
https://phys.org/news/2017-09-simple-chess-puzzle-key-1m.html
[Abstract]: "Complexity of n-Queens Completion"
[Source]: https://www.st-andrews.ac.uk/news/archive/2017/title,1539813,en.php
Any takers for this challenge?
(Score: 3, Informative) by JoeMerchant on Saturday September 02 2017, @10:21PM (2 children)
What ticks me off about the usual presentation of "NP" problems is the old: "They're easy to check, but hard to find" meme. The next statement is usually something like: "N-Queens is an NP problem, here's the N-Queens problem, you have to place N Queens on a chessboard that is NxN in such a way that no Queen threatens another." End of presentation. In University I got a similar presentation for the sum of products to product of sums transformation problem.
What is almost always left out of the presentation of the problem is the part that makes it NP-hard. For N-Queens, that's finding every possible solution for the given N, not just finding one. Other NP problems are similar, they have an easy-ish case that you can attack and solve and say "HA! I beat it!" then the serious mathematicians will slowly explain to you the real problem, while the poseurs will scratch their heads and say something like "You must have made a mistake somewhere, it's really unlikely that you solved NP=P." Yeah poseur, what you really mean is that you don't even know what special case of the problem makes it NP, you just go around parroting what you were fed in the lectures.
So, go out there, skip the research and independently find a solution for N-Queens where N=1000, present it for the prize, and be told how your methods were "well studied back in the 1970s and don't really present anything novel or valuable." The really sad part is how disorganized the research is, even today, it's really hard (maybe not NP hard, but harder than it should be) to pull together the collection of search methods and heuristics that have been tried and comparisons between them, much less in-depth explanations of how each one works. There's some really elegant/simple backtracking code out there that does the solution in NP time, but not much on the faster methods that are known.
🌻🌻 [google.com]
(Score: 0) by Anonymous Coward on Saturday September 02 2017, @10:26PM (1 child)
(Serious)Why did you spend so much time commenting? Are you rich enough to pass on the prize? I'll assume you are. You sound smart enough to do this in maybe a weekend.
(Score: 3, Informative) by JoeMerchant on Sunday September 03 2017, @12:50AM
I took a run at NP back in college, my conclusion matches the literature: once you get all the terms of the problems, they're not simple at all. They're usually intractable search problems that involve pernicious edge cases.
The researchers that posted this prize have a paper (I linked it somewhere else in the comments) where they describe how N-Queens transitions from P to NP as the number of pre-defined Queen positions increases - if no Queens are pre-placed on the board, you can find a solution rather easily, but at some point the problem becomes NP hard to determine if there is a solution or not, given the starting position. This is the game people used to pass around in the late 1800s: take a tough starting position and either find the solution or determine that there isn't one. Now that we know for certain all 12 solutions to the problem, you can classify any of the 4 billion+ 8 Queens starting problems by inspection, it (or a reflection or rotation) either matches one of the 12 solutions by inspection, or it doesn't. As N gets higher, the number of solutions grows roughly exponentially, and the current meme is that by N=1000, the problem (of finding all solutions) is intractable, therefore it is difficult to say if a plausible partial starting position has a workable solution or not.
Some of the Clay prizes may still be up for grabs, but I don't think this one is - at least by conventional techniques. Maybe something with quantum computing might make it go faster, but I haven't heard about anybody trying to apply quantum techniques to NP, yet.
🌻🌻 [google.com]