Scientists are offering a US$1 million prize to anybody who can solve a fiendishly complicated twist on a classic chess problem called the Queen’s Puzzle.
The beauty of the challenge is you don’t even really need to understand the rules of chess to take part, but that doesn’t mean it will be easy. In fact, the researchers say the solution is so mathematically complex that finding it could take thousands of years.
To put things in context, then, let’s start at the beginning.
The Queen’s Puzzle (aka the eight queens puzzle), was originally published in 1848, and charges you with placing eight queens on an 8 x 8 chess board, such that no two queens directly threaten one another.
If you know the rules of chess, you know the queen is the most powerful piece on the board, as it can move in eight directions – up, down, side to side, plus diagonally – and not only that, but the queen can also move an unlimited distance in any of these directions. Queenly fatigue is not a thing.
That unparalleled freedom of movement is why the Queen’s Puzzle is a beguiling challenge to chess players and mathematicians – albeit not one that’s overly difficult to solve.
In fact, there are 92 different ways to resolve the puzzle – out of about 4.5 billion potential arrangements of the eight queens on the board – which is why mathematicians have long sought to make things more interesting.
What if, say, instead of being limited to just an 8 x 8 standard-sized chess board with 64 squares in total, you expanded the dimensions of the problem to include virtually any number of queens?
In that case, you’d have to fit 20 queens on a 20 x 20 board, or 100 queens on a 100 x 100 board, and so on – and none of them can be positioned in the same row, column, or diagonal as their counterparts.
Once this variant of the puzzle, called the n-Queens puzzle – where n is the number of rows, columns, and queens – approaches very large numbers (like n = 1,000), things get really, really difficult to compute, even for very powerful computers, given the number of possibilities involved.
And the level of challenge gets even more ridiculous if you add in another bothersome twist: a clique of unmovable queens that already occupy set positions on the board.
“The new research concerns the n-Queens Completion Problem, where not only is the board larger, but also some queens have already been placed,” explains computer scientist Ian Gent from the University of St Andrews in the UK.
“That is, if some queens have already been placed on the n-by-n board, can you find a solution to the n-Queens puzzle without moving any of those queens?”
The problem may be easy to grasp in your mind, but figuring out ways to efficiently solve the puzzle – for any value of n – is actually one of the toughest gigs in computational complexity.
That’s why Gent and fellow researchers think a computer program capable of solving this inscrutable variant of the Queens Puzzle quickly – that is, not taking a millennium to calculate large values of n – would be powerful enough to solve all kinds of other mathematical problems with high variables that today’s computers struggle with.
“If you could write a computer program that could solve the problem really fast, you could adapt it to solve many of the most important problems that affect us all daily,” Gent says.
“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.”
That’s why the Clay Mathematics Institute is offering a $1 million prize to anybody who can solve the challenge as part of its Millennium Prize Problems – after Gent’s team established in a new paper that the n-Queens Completion Problem is an example of what’s called a P vs NP Problem.
“The technical contribution claimed in this paper is that the n-Queens Completion Problem falls into the class known as NP-Complete,” Gent explains.
“If correct, this means that any algorithm that can solve the n-Queens Completion Problem can be used indirectly to solve any other problem in the NP class.”
According to Gent, the prize can be won by either proving that no algorithm can solve the puzzle in a reasonable time, or by developing an algorithm that can solve it quickly – or, in mathematical parlance, what’s known as polynomial time.
If you’re after tips, Gent told Digital Trends that contestants will need to be brilliant, very, very lucky, and to have a PhD in computational complexity to have a chance at winning the prize.
But even then, it seems, the odds are likely against them.
“[T]his is all theoretical,” explains one of the team, Peter Nightingale.
“In practice, nobody has ever come close to writing a program that can solve the problem quickly. So what our research has shown is that – for all practical purposes – it can’t be done.”
Them’s fighting words. Anybody out there care to prove them wrong?
The findings are reported in the Journal of Artificial Intelligence Research.