$1 Million Chess Puzzle

[dee-u]

Anyone of you guys who wants to prove them wrong?

which could take thousands of years to solve

St Andrews scientists lay down million dollar chess challenge

[passel]

Not me. But I was curious so tried to solve the eight queens manually for a bit.
I could get 7 down easily enough but the 8th is the kicker.
Couldn't find the pattern but assumed it wouldn't be that hard to have a program solve it.
The code isn't the most efficient I assume, but solves the eight queens in 2 to 4 milliseconds on my Work I5 laptop, running in the IDE.
The answer I got was

 Q  _  _  _  _  _  _  _ 
 _  _  _  _  _  _  Q  _ 
 _  _  _  _  Q  _  _  _ 
 _  _  _  _  _  _  _  Q 
 _  Q  _  _  _  _  _  _ 
 _  _  _  Q  _  _  _  _ 
 _  _  _  _  _  Q  _  _ 
 _  _  Q  _  _  _  _  _

p.s. Since I had the code written, decided to try a few other board sizes.
Only did a single run for each size. the number above the dump is the number of milliseconds (I went ahead and added ms to the line after I pasted the results in the post).
Probably can't print the larger ones because of post limits, so will only note the time.

16x16
68ms
 Q  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _ 
 _  _  _  Q  _  _  _  _  _  _  _  _  _  _  _  _ 
 _  Q  _  _  _  _  _  _  _  _  _  _  _  _  _  _ 
 _  _  _  _  _  _  _  _  _  _  _  _  Q  _  _  _ 
 _  _  Q  _  _  _  _  _  _  _  _  _  _  _  _  _ 
 _  _  _  _  _  _  _  _  _  Q  _  _  _  _  _  _ 
 _  _  _  _  _  _  _  _  _  _  _  Q  _  _  _  _ 
 _  _  _  _  _  _  _  _  _  _  _  _  _  _  Q  _ 
 _  _  _  _  _  Q  _  _  _  _  _  _  _  _  _  _ 
 _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  Q 
 _  _  _  _  _  _  _  _  _  _  _  _  _  Q  _  _ 
 _  _  _  _  _  _  _  Q  _  _  _  _  _  _  _  _ 
 _  _  _  _  Q  _  _  _  _  _  _  _  _  _  _  _ 
 _  _  _  _  _  _  Q  _  _  _  _  _  _  _  _  _ 
 _  _  _  _  _  _  _  _  Q  _  _  _  _  _  _  _ 
 _  _  _  _  _  _  _  _  _  _  Q  _  _  _  _  _ 

20x20
1217 ms
 Q  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _ 
 _  _  _  Q  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _ 
 _  Q  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _ 
 _  _  _  _  Q  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _ 
 _  _  Q  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _ 
 _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  Q  _ 
 _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  Q  _  _  _ 
 _  _  _  _  _  _  _  _  _  _  _  _  _  _  Q  _  _  _  _  _ 
 _  _  _  _  _  _  _  _  _  _  _  Q  _  _  _  _  _  _  _  _ 
 _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  Q  _  _  _  _ 
 _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  Q 
 _  _  _  _  _  _  _  Q  _  _  _  _  _  _  _  _  _  _  _  _ 
 _  _  _  _  _  Q  _  _  _  _  _  _  _  _  _  _  _  _  _  _ 
 _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  _  Q  _  _ 
 _  _  _  _  _  _  Q  _  _  _  _  _  _  _  _  _  _  _  _  _ 
 _  _  _  _  _  _  _  _  _  _  _  _  Q  _  _  _  _  _  _  _ 
 _  _  _  _  _  _  _  _  _  _  Q  _  _  _  _  _  _  _  _  _ 
 _  _  _  _  _  _  _  _  Q  _  _  _  _  _  _  _  _  _  _  _ 
 _  _  _  _  _  _  _  _  _  _  _  _  _  Q  _  _  _  _  _  _ 
 _  _  _  _  _  _  _  _  _  Q  _  _  _  _  _  _  _  _  _  _ 

24x24  2997 ms
26x26  3659 ms
28x28 30521 ms
29x29 16681

A 30x30 is taking a huge amount of time. I'll run it while I go to bed and see if it completes or not when I get up.

The 30x30 board took 549676 milliseconds, so a little over 9 minutes, i.e. 00:09:09.676

[topshot]

May not want to spend too much time on it if you hope to get the prize
http://claymath.org/events/news/8-queens-puzzle

[passel]

Certainly wasn't planning on it.
No surprise that the reporter misrepresented the challenge in his article.

[Sitten Spynne]

The reason there's a prize for this is it's a trick question, and if you could provably solve the question as phrased you could solve a lot of other very exciting problems.

If I found the answer, I know it'd be worth way more than $1m. I would patent the hell out of it and I think Amazon would happily pay me $1b in licensing fees annually, because solving this kind of problem is considered key to solving the Traveling Salesman Problem, among other things.

A few times a year someone comes forth with a new "solution", but they always misunderstand the problem isn't "finding a solution" but "proving your algorithm finds the best solution".

[Shaggy Hiker]

The problem feels like prime numbers, to me. Any queen placed on an infinite chessboard sweeps out infinitely long vertical, horizontal, and diagonal files. The point to the game is that no other queen can be placed along those files, but can be placed on any other square not thus swept. Similarly, as you count from 2 upwards, each number sweeps out an infinite file of numbers. Two takes out all the multiples of two, three takes out all the multiples of three, and so forth. A number is prime if it isn't on one of those files. Finding prime numbers can be done by brute force, as can finding solutions to the n-queen problem. Finding either one without a brute force approach would be significant, but even trying to solve the n-queen problem would put you under pressure. You may think, "don't stop me now", that you're doing all right, and that the answer will be coming soon, but it'll leave you with blurred vision. I was going to go on weaving references to Queen songs into this, but they just have so MANY of them. I figured this party would misfire, so I figured I'd put out the fire before it gave me a sheer heart attack and left me wondering, "was it all worth it?"