'Simple' chess puzzle holds key to $1m prize

September 1, 2017
Credit: University of St Andrews

Researchers at the University of St Andrews have thrown down the gauntlet to computer programmers to find a solution to a "simple" chess puzzle which could, in fact, take thousands of years to solve and net a $1m prize.

Computer Scientist Professor Ian Gent and his colleagues, at the University of St Andrews, believe any program capable of solving the famous "Queens Puzzle" efficiently, would be so powerful, it would be capable of solving tasks currently considered impossible, such as decrypting the toughest security on the internet.

In a paper published in the Journal of Artificial Intelligence Research today, the team conclude the rewards to be reaped by such a program 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.

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 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 program can solve it.

Professor Gent and his colleagues, Senior Research Fellow Dr Peter Nightingale and Reader Dr Christopher Jefferson, all of the School of Computer Science at the University, first became intrigued by the after a friend challenged Professor Gent to solve it on Facebook.

The team found that once the chess board reached 1000 squares by 1000, computer progams could no longer cope with the vast number of options and sunk into a potentially eternal struggle akin to the fictional "super computer" Deep Thought in Douglas Adams' Hitchhiker's Guide to the Galaxy, which took seven and a half million years to provide an answer to the meaning of everything.

Professsor Gent said: "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.

"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."

The reason these problems are so difficult for programs, is that there are so many options to consider that it can take many years. This is due to a process of "backtracking" – an algorithm used in programming where every possible option is considered and then "backed away" from until the correct solution is found.

Dr Nightingale said: "However, this is all theoretical. 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."

Dr Jefferson added: "There is a $1,000,000 prize for anyone who can prove whether or not the Queens Puzzle can be solved quickly so the rewards are high."

Chess has long provided the source for puzzles such as the traditional fable of the servant who, when asked to choose a reward by his king, asked for one grain of rice to be placed on the first square of a standard 8x8 chessboard, doubled in the next and so on until it was found there was not enough rice in the entire world.

The fable indicates the huge numbers involved when using just a standard sized chess board. When the board size increases the numbers become vast.

Explore further: Institute offers public chess challenge to learn more about how we think (Update)

More information: Complexity of n-Queens Completion. Journal of Artificial Intelligence Research. DOI: DOI: 10.1613/jair.5512 , http://jair.org/papers/paper5512.html

Related Stories

Difficulty makes Candy Crush so addictive

March 13, 2014

It's been said that in a city, you're never more than two metres away from a rat. But it seems more likely that you're never more than two metres from someone playing the puzzle game Candy Crush Saga.

Recommended for you

Microbes help turn Greek yogurt waste into fuel

December 13, 2017

Consumers across the world enjoy Greek yogurt for its taste, texture, and protein-packed punch. Reaching that perfect formula, however, generates large volumes of food waste in the form of liquid whey. Now researchers in ...

17 comments

Adjust slider to filter visible comments by rank

Display comments: newest first

dirk_bruere
not rated yet Sep 01, 2017
Sounds like a problem for a quantum computer using simulated annealing
cturner3rd
5 / 5 (4) Sep 01, 2017
This is a restatement of the well-known P versus NP problem. The Clay Mathematics Institute has been offering $1M for a solution to this and several other problems for many years.
Hyperfuzzy
not rated yet Sep 01, 2017
Start by placing each a night move apart and toward and edge, trace backwards
baudrunner
not rated yet Sep 02, 2017
The solution is not hard, but it can seem so if no attempt at pattern recognition is considered. That actually makes the 8x8 board harder to populate than a 10x10 board. For the example of the 10x10 board, the pseudo code would look like this:

with the checkerboard rows counted from the top, columns left to right..

n = the row number
x = the tile number to place the queen

for even values of n beginning with row 2: x = n / 2 up to the last row, then to continue,
starting with row 1, and for all subsequent odd numbered rows: x = x + 1. You can see the pattern.

One solution for an 8 x 8 board (does not follow the above method): places the queens as follows..

row - column

1 - 6
2 - 1
3 - 5
4 - 2
5 - 8
6 - 3
7 - 7
8 - 4

Whydening Gyre
not rated yet Sep 02, 2017
The solution is not hard, but it can seem so if no attempt at pattern recognition is considered. That actually makes the 8x8 board harder to populate than a 10x10 board. For the example of the 10x10 board, the pseudo code would look like this:

with the checkerboard rows counted from the top, columns left to right..

n = the row number
x = the tile number to place the queen
...

The article already says in can be solved by humans.
It's just that programming a 'puter to recognize and check is really tuff...
And they're talking in context of 1000x1000, not 8x8 or 10x10.

AlexisTM
not rated yet Sep 03, 2017
This is a pretty easy solution, It takes around 13 seconds for a 10000x10000 chessboard with the validity check and less than a second for the 1000x1000. Yet, to claim the price, you have to make a paper.
monstercolorfun
not rated yet Sep 03, 2017
They don't give the chess problem in the actual prize rules, they say fast and don't give a time limit of hours/days/weeks. Article is inaccurate: "A simple problem for programmers to figure out..." Hidden subscript: complext P - NP turing polynomial computability function that has nothing to do with the original chess problem, which is 2D... You have to read complex maths and publish in a maths journal to claim the prize. So it's not a question for programmers or ordinary puzzle solvers. I am good at the queen problem and i can figure how to optimize it on a computer. but they don't give the chess problem in the actual prize rules.
baudrunner
not rated yet Sep 05, 2017
It's just that programming a 'puter to recognize and check is really tuff...
..computers do what the programmers tell them to.

The 10x10 solution I provided is really easy to implement and is portable to all larger layouts, like I said, with some minor adaptations for even or odd numbers of rows - eg. a 100x100 cell layout, or a 11x11 layout. Population is immediate, and needs no verification from the software. There are military applications, example is distribution of drones over a large area.

The math groupies want a complex answer that they can't understand in order to get any respect from them. "The math groupie not a mathematician be."

Occam's razor, my friend.

They'll never give me the money, though. They're Scots!
baudrunner
not rated yet Sep 05, 2017
here's the chess board solution:

O O O O O M O O
M O O O O O O O
O O O O M O O O
O M O O O O O O
O O O O O O O M
O O M O O O O O
O O O O O O M O
O O O M O O O O
wetnose
not rated yet Sep 17, 2017
For 1000x1000 with a single preplaced queen (the hardest case for nQ completion) it takes 2.5-5 hours (depending on the queen location) to find the 1st solution on my Core i5-2500 3.3GHz (only one core of four is used). Is it fast enough?
gvnsreddy
not rated yet Sep 22, 2017
For 1000x1000 with a single preplaced queen (the hardest case for nQ completion) it takes 2.5-5 hours (depending on the queen location) to find the 1st solution on my Core i5-2500 3.3GHz (only one core of four is used). Is it fast enough?


Yes, it is fast enough.

Please publish the solution for a queen at (1,1) preplaced.

Please mention, what is the programming language used.
Hyperfuzzy
not rated yet Sep 22, 2017
For 1000x1000 with a single preplaced queen (the hardest case for nQ completion) it takes 2.5-5 hours (depending on the queen location) to find the 1st solution on my Core i5-2500 3.3GHz (only one core of four is used). Is it fast enough?


Yes, it is fast enough.

Please publish the solution for a queen at (1,1) preplaced.

Please mention, what is the programming language used.

Why would it take so long, each queen owns a set of squares, eliminated from search. The next location is obviously a Knight move away, in one direction until no more exist! A simple elimination game. By the way, count the number of retrys. The software you're using sounds very inefficient, it's simply an array filled game while maximizing the number of queens. You can see that the number of queen is always equal or less than the square-root of number of cells. So if an N sided board there are N^3 try's using a draconian method per queen on a decreasing set of plys, mirro
Hyperfuzzy
not rated yet Sep 22, 2017
So N^4 expected => most compares, speed? That is each queen on a square attacks a set to be blocked from another queen. So build your code to show the board, only place when true. Ta Da! I know code, first see what your doing! Simple, I hate coding. The tools are so archaic. Isn't there enough information to place the human interface in hardware, with logic and objective memory. I would go on to define the universal fuzzy object, but ...
Hyperfuzzy
not rated yet Sep 22, 2017
So this could run as
Initiate Constant Strings
a plys Q(a1), Q(a2). ... Q(nn); Note: each ply is a string of 1's and 0' or as N^2 Bit register.
For all plys
If rowA<>RowB and ColA<>ColB and no Match from StringA, StringB, keep
Display Board
Done once

Something like that ought to do it. Note: I would seek to eliminate the embedded loops.
Hyperfuzzy
not rated yet Sep 22, 2017
Or define each cell (Square) as an object with memory, so when adding a Queen the board will update itself with the possibility N queens as a set of possibilities. i.e. an intelligent board.
brosales
not rated yet Sep 24, 2017
I came up with a method of instantly creating 7 new solutions based on any existing solution. From my original 14 solutions, I've arrived at a total of 98 new & unique solutions for a total of 112 different solutions... 20 more than the stated "92 accepted solutions." Is this method worth $1 million?
Hyperfuzzy
not rated yet Sep 25, 2017
Select N Queens upon an NxN [partitioned withN[sets] of orthogonal lines equally space] Plane; report graphically. Please.

See what I just did, I let every square see every other square and they have a way of being choosy where a new neighbor lives, so these squares are off limits; so first square suggest a set and the set suggest ... only until no suggestions are left, report solution set. I know you gonna blow it first try, coding, so buggy, why do we do this to ourselves? Create human language interface. So what if you must be logical and tabulate what's omitted, ha, ha

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.