$1,000,000 prize for a chess algorithm
-
https://www.digitaltrends.com/cool-tech/million-dollar-chess-challenge/[^] I swear, I thought we were done with chess.
-
https://www.digitaltrends.com/cool-tech/million-dollar-chess-challenge/[^] I swear, I thought we were done with chess.
You've been pawned...
-
https://www.digitaltrends.com/cool-tech/million-dollar-chess-challenge/[^] I swear, I thought we were done with chess.
This can't be real, there is a well known linear-time algorithm. It's even on [wikipedia](https://en.wikipedia.org/wiki/Eight\_queens\_puzzle#Explicit\_solutions)! E: in the [actual paper](http://jair.org/papers/paper5512.html) it is clear that what they did here is prove that a specific variant (where some queens are pre-placed) is NP-complete, so you get the prize by solving the P?=NP question.
-
https://www.digitaltrends.com/cool-tech/million-dollar-chess-challenge/[^] I swear, I thought we were done with chess.
Interesting. They mention that the problem has been expanded to a chessboard that's 1000 by 1000. But they don't mention if there has been a corresponding increase in the number of queens. It would seem that on such a large chessboard, it would be easy to place eight queens so that no two can attack each other.
The difficult we do right away... ...the impossible takes slightly longer.
-
This can't be real, there is a well known linear-time algorithm. It's even on [wikipedia](https://en.wikipedia.org/wiki/Eight\_queens\_puzzle#Explicit\_solutions)! E: in the [actual paper](http://jair.org/papers/paper5512.html) it is clear that what they did here is prove that a specific variant (where some queens are pre-placed) is NP-complete, so you get the prize by solving the P?=NP question.
Well, It would take thousands of years to solve the problem on really huge grids... say 2500x2500 The whole point of the challenge is to come up with a new faster method for solving the problem. It also takes a lot of RAM... my depth-first implementation runs out of memory on really huge grids somewhere above 900x900. I didn't spend any time optimizing so I could probably fix this with file-backed memory. Best Wishes, -David Delaune
-
Interesting. They mention that the problem has been expanded to a chessboard that's 1000 by 1000. But they don't mention if there has been a corresponding increase in the number of queens. It would seem that on such a large chessboard, it would be easy to place eight queens so that no two can attack each other.
The difficult we do right away... ...the impossible takes slightly longer.
-
Well, It would take thousands of years to solve the problem on really huge grids... say 2500x2500 The whole point of the challenge is to come up with a new faster method for solving the problem. It also takes a lot of RAM... my depth-first implementation runs out of memory on really huge grids somewhere above 900x900. I didn't spend any time optimizing so I could probably fix this with file-backed memory. Best Wishes, -David Delaune
It's already linear time, what more do you want?
Wikipedia wrote:
If the goal is to find a single solution then explicit solutions exist for all n ≥ 4, requiring no combinatorial search whatsoever.
.. some formulas to calculate the placement follow, all of them trivial arithmetic.
-
Interesting. They mention that the problem has been expanded to a chessboard that's 1000 by 1000. But they don't mention if there has been a corresponding increase in the number of queens. It would seem that on such a large chessboard, it would be easy to place eight queens so that no two can attack each other.
The difficult we do right away... ...the impossible takes slightly longer.
Richard Andrew x64 wrote:
But they don't mention if there has been a corresponding increase in the number of queens
The article itself is incomplete. The synopsis of the actual paper has the real description. "The n-Queens problem is to place n chess queens on an n by n chessboard"
Richard Andrew x64 wrote:
it would be easy to place eight queens so that no two can attack each other.
I wonder if it is a solvable problem to figure out how many possible positions eight queens could be done on a 1000x1000 board. Without using years on a computer.
-
Richard Andrew x64 wrote:
But they don't mention if there has been a corresponding increase in the number of queens
The article itself is incomplete. The synopsis of the actual paper has the real description. "The n-Queens problem is to place n chess queens on an n by n chessboard"
Richard Andrew x64 wrote:
it would be easy to place eight queens so that no two can attack each other.
I wonder if it is a solvable problem to figure out how many possible positions eight queens could be done on a 1000x1000 board. Without using years on a computer.
jschell wrote:
I wonder if it is a solvable problem to figure out how many possible positions eight queens could be done on a 1000x1000 board
42 ;)
Latest Article - Class-less Coding - Minimalist C# and Why F# and Function Programming Has Some Advantages Learning to code with python is like learning to swim with those little arm floaties. It gives you undeserved confidence and will eventually drown you. - DangerBunny Artificial intelligence is the only remedy for natural stupidity. - CDP1802
-
https://www.digitaltrends.com/cool-tech/million-dollar-chess-challenge/[^] I swear, I thought we were done with chess.
I imagine one could generalize on the knight-pattern that is required of any solution to solve any n-sized board, to find at least one solution. I'll ponder it, but one of the things these people love to do is spout permutations, which look daunting, but there are ways to solve problems other than by "smart" permutations. Finding required patterns is one of them.
Latest Article - Class-less Coding - Minimalist C# and Why F# and Function Programming Has Some Advantages Learning to code with python is like learning to swim with those little arm floaties. It gives you undeserved confidence and will eventually drown you. - DangerBunny Artificial intelligence is the only remedy for natural stupidity. - CDP1802
-
Richard Andrew x64 wrote:
But they don't mention if there has been a corresponding increase in the number of queens
The article itself is incomplete. The synopsis of the actual paper has the real description. "The n-Queens problem is to place n chess queens on an n by n chessboard"
Richard Andrew x64 wrote:
it would be easy to place eight queens so that no two can attack each other.
I wonder if it is a solvable problem to figure out how many possible positions eight queens could be done on a 1000x1000 board. Without using years on a computer.
jschell wrote:
"The n-Queens problem is to place n chess queens on an n by n chessboard"
Thank you for that clarification! :)
The difficult we do right away... ...the impossible takes slightly longer.
-
I imagine one could generalize on the knight-pattern that is required of any solution to solve any n-sized board, to find at least one solution. I'll ponder it, but one of the things these people love to do is spout permutations, which look daunting, but there are ways to solve problems other than by "smart" permutations. Finding required patterns is one of them.
Latest Article - Class-less Coding - Minimalist C# and Why F# and Function Programming Has Some Advantages Learning to code with python is like learning to swim with those little arm floaties. It gives you undeserved confidence and will eventually drown you. - DangerBunny Artificial intelligence is the only remedy for natural stupidity. - CDP1802
since we are on this subject... The smallest board with a possible solutions is 4x4 right? I don't think it is possible to solve a 3x3. :~ I'm sure a 2x2 is unsolvable. Why does google say that it took 1ms to solve a 1x1 board? Also, their grid makes it look like it took 0ms to solve the 3x3 and 4x4 but I believe they are trying to say they're unsolvable. They really should've been more clear: The N-queens Problem Optimization: Google Developers[^] Look at their chart all the way at the bottom. EDIT Oh, I stared at the chart longer... It is actually just that the data is unaligned with the headers at the top of the chart. They are actually saying there are 0 solutions for board sizes 2 and 3. I'm using Chrome, you'd think their chart would look right. :)
-
Well, It would take thousands of years to solve the problem on really huge grids... say 2500x2500 The whole point of the challenge is to come up with a new faster method for solving the problem. It also takes a lot of RAM... my depth-first implementation runs out of memory on really huge grids somewhere above 900x900. I didn't spend any time optimizing so I could probably fix this with file-backed memory. Best Wishes, -David Delaune
Mine doesn't chew up memory as it works; it allocates all it needs at the beginning and then just uses it. As n increases, it doesn't complete in a usable amount of time of course. I don't know whether or not I let it run to completion on a large n. Re: nQueens algorithm - Algorithms Discussion Boards[^]
