Slashdot Mirror
Solve a 'Simple' Chess Puzzle, Win $1 Million (st-andrews.ac.uk)
An anonymous reader brings an important announcement:
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 $1 million 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. In a paper [PDF] published in the Journal of Artificial Intelligence Research today, the team conclude the rewards to be reaped by such a program would be immense, not least in financial terms with firms rushing to use it to offer technological solutions, and also a $1 million prize offered by the Clay Mathematics Institute in America.
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.
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.
"once the chess board increases to a large size no computer program can solve it"
How large is that? Many algorithms for simpler problems would fail if the size is multiplied by a big number.
Slashdot, fix the reply notifications... You won't get away with it...
First of all, the problem cant in any real sense be considered a chess puzzle, except in the superficial sense of placing queens on a board. Chess reasoning has nothing to do with a solution of the problem.
Second of all, the $1m prize is exactly the clay millennium prize for the resolution of P vs NP. If n-qeens has a solution in P, being NP-complete, this implies P=NP.
tldr Sensationalist title is sensationalist
Also something about chess.
I have discovered a truly remarkable program which this box is too small to contain. I'll complete it after I get back from a duel I have later today.
Three researchers proved that the queen problem is NP-complete. The prize is the millennium prize for P=NP. The journal publication is at http://jair.org/papers/paper5512.html.
Not only that, but if an 8-queen solution works on an 8x8 board, it'll work just as well on a 1000x1000 or a 10k x 10k board, etc. board. Move it over, put it in the same relative location in the 8x8 group at the corner of the larger board, done. So solve for 8x8 and move.
So you'll need to split that money with me, pal. :)
Of course, it's just slightly possible that TFS is not an accurate summary of the actual article / problem, but...
Nah. Besides, everyone knows that reading TFA is un-American. Even reading the summary raises red flags with Homeland Security, and may result in a National Security Letter (which you can read, but can't discuss.)
I've fallen off your lawn, and I can't get up.
too bad that with Prolog solving the queen problem using CLP(FD) (using gprolog for instance) 500 queens can be solved in less than a second...
Serious question... I've written something like that before, and although it wasn't speedy... I don't recall it being particularly long either.
Also, does it have to come up with all solutions quickly, or just one?
File under 'M' for 'Manic ranting'
> Dr Jefferson added: “There is a $1,000,000 prize for anyone who can prove whether or not the Queens Puzzle can be solved quickly so the rewards are high.”
It's not the solution that gets you the prize, but the proof that the solution can be done quickly (without exploring nearly every permutation).
Often wrong but never in doubt.
I am Jack9.
Everyone knows me.
Start cursor in the upper left cell.
Mark/Queen location
--- Subroutine start
Shift cursor right, down 2 (like a Knight!)
Mark
if out of bounds or final Y row
break
--- Subrouting end
Shift cursor up, right 2
Mark
--- Subroutine start
Shift cursor right, up 2
Mark
if out of bounds or initial Y row
break
--- Subrouting end
Done. There is a simple solution, but the prize is about being able to prove there is a simple solution, without coming up with it (P = NP)
Often wrong but never in doubt.
I am Jack9.
Everyone knows me.
Ok, So give me a cluster of 30K machines, each machine having access to a few k of computer cores (think 4 GPUs) that gives me access to about 100M compute cores to solve this problem. I imagine this is a rather ridiculously easy problem to throw cores at - so with 100M cores in a compute cluster I imagine this problem simplifies into a few months worth of cluster time...
I have mod points and I am not afraid to use them
But this comment field is too small for me to post it.
I don't understand the fuss, I found not only one but TWO ways to figure out P=NP using Python. Doesn't even require numpy or a GPU and it works even with super big numbers.
#Solution 1:
for N in range(sys.maxsize):
P = 0
if P == N * P:
print("it works.")
#Solution 2:
for P in range(sys.maxsize):
N = 1
if P == N * P:
print("it works.")
Python is so powerful.
lucm, indeed.
And slashdot gets stupider yet.
So, prove P=NP, win $1 million. Makes sense, why is this nonsense even here?
Such a proof would not necessarily be worth a million dollars. It could be applicable only to the Queens Puzzle and to nothing else.
Yes it would. The Queen's Puzzle is an NP-complete problem, hence a solution to it would solve every other NP-complete problem.
I read the paper.
They wrote their solver in Java.. You can't trust anything they say, especially about performance.
Really cool in-browser visualizer of 5 different algorithms for solving this problem...
http://haseebq.com/n-queens-visualizer/
Both the summary and the article are crap.
The important part is the following line from the abstract:
We show that n-Queens Completion is both NP-Complete and #P-Complete.
All the rest (other than the math in the actual paper) is fluff.
the answer is 42.
Citation needed.
it feels like it should be possible to set up a physical analog of the problem and let it find its own stable point. Isn't this what quantum computing is meant to solve ? Or is that cheating by trying every possible solution just very quickly ? There, I've just demonstrated my ignorance (again).
Nullius in verba
Because AA batteries solve all portable energy problems.
It's almost certainly not NP-complete. The problem is trivially in P/poly. Proving it NP-complete would prove P/poly contains NP, which is nearly as big of a breakthrough as showing P = NP.
https://en.m.wikipedia.org/wik...â"Levin_theorem Cook showed that any decision problem with easily checkable solution could be mechanically and quickly converted into a Boolean satisfiability problem of similar size. Thus, SAT became the first known example of a so called NP-complete problem. Other examples are then much more easily found by giving a procedure to convert SAT problems into that kind of problem. Such a procedure was apparently given for some variation of the queen problem. So in fact yes, an algorithm fast for specifically queens can be composed with the (already known) fast transformation from SAT and ultimately through Cooks construction for any particular NP problem (where he is able to be completely general by taking as input the Turing machine for the solution checker)
If you think it's unbelievable, that's completely natural. No one would suspect the existance of NP complete problems from the start.