A $1 million prize has been announced for anyone who can solve an allegedly “simple” chess puzzle.
Clair Hart
August 31, 2017
A $1 million prize has been announced for anyone who can solve an allegedly “simple” chess puzzle.
Researchers have thrown down the gauntlet to computer programmers to find a solution to a chess puzzle — but it could take thousands of years to solve.
Computer scientist Professor Ian Gent and his colleagues at the University of St Andrews are now challenging computer programmers to solve it for $1 million (£776,478).
They believe any programme capable of solving it would be so powerful it would be able to solve impossible tasks – 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 programme can solve it.
The university researchers first became intrigued by the puzzle after a friend challenged Professor Gent to solve it on Facebook.
Professor Gent said: “If you could write a computer programme that could solve the problem really fast, you could adapt it to solve many of the most important problems that affect us all daily.
“This includes trivial challenges like working out the largest group of your Facebook friends who don’t know each other.
“Or very important ones like cracking the codes that keep all our online transactions safe.”
In a paper published in the Journal of Artificial Intelligence Research today (Thur), the team concludes the rewards to be reaped by such a programme would be immense.
Not least in financial terms with firms rushing to use it to offer technological solutions, and also a $1m prize offered by the Clay Mathematics Institute in America.
The reason these problems are so difficult for computer programmes is that there are so many options to consider – it can take years.
Dr Peter Nightingale said: “In practice, nobody has ever come close to writing a programme that can solve the problem quickly.
“So what our research has shown is that – for all practical purposes – it can’t be done.”
They’re completely bonkers.
Let’s say we want to do a Queens puzzle arrangement for a board with a side of length n squares, where n is for instance a big number prime.
Now if we can work out the solution for a normal chessboard of 8×8 squares we can generate a solution for a board of 64×64 squares simply by dividing that up into areas of 8×8 resembling the squares of a chessboard and then substituting the whole original chessboard for each of the 8×8 squares in the same pattern as the queens on the original chessboard and then you have a sort of reverse fractal pattern which also satisfies the criteria.
And then you can repeat the process over and over until you have a board with a side larger than the big number prime and then simply remove rows and columns until you get down to a board of size nxn and the pattern on that board should also meet the criteria.
James, I pretty much agree with you. The problem of solving the 8×8 case was solved a long time ago, there being 92 solutions, which reduces to 12 if one discounts rotations of the board and mirror images. If the problem is to find ONE solution on any NxN board, I don’t think the problem can be all that complex. The difficulty comes when trying to find ALL the solutions for any NxN board. That is a real challenge.