Want to win a million dollars? Just solve this puzzle
What's the story
A lucrative offer is up for grabs for coders: if you can build a program to solve the age-old Queens Puzzle, you could win a million dollars.
However, researchers think it is impossible. If someone does make such a program, it could be used to decode the most complex challenges on earth to perhaps, decrypting the toughest security on the internet.
Challenge
What exactly do you have to do?
The Queens Puzzle was devised in 1850: you have to place eight queens on a standard 8x8 chessboard so that no two queens can attack each other.
For this challenge, the algorithm has to work on a 1,000x1,000 chessboard. The number of queens will go up accordingly.
Alternatively, you could prove no algorithm can solve the n-Queen Completion puzzle in reasonable time.
Do you know?
Interestingly, humans have solved the basic puzzle
Till now, humans have solved the problem on an 8x8 chessboard more than once: there are 92 solutions out of a possible 4,426,165,368 arrangements. However, once the board is scaled up, it starts becoming more and more complex.
AI
So why are computers failing?
To solve such problems, computers use 'backtracking'- every possible option is considered and then 'backed away' from till the solution is found.
But at 1,000, the number of options is so high that testing each one could take years; computers can't cope and sink into an eternal struggle.
If such a program is made, it could solve tasks currently considered impossible, researchers said.