News, Culture & Society

Crack the Queens Puzzle to win a $1 million prize

A prize of $1 million (£776,478) could be taken home by anyone who can build an app to solve a supposedly ‘simple’ chess puzzle.

Computer scientists at the University of St Andrews are challenging coders to crack the maths behind the solution to grab the cash prize.

They believe a programme capable of achieving this would be so powerful it could accomplish nearly impossible tasks, including defeating online security measures.

Their latest research suggests that it could take the software thousands of years to complete the calculations, however.

 

Can you solve the Queens Puzzle? This game, programmed by Ronald Daenzer and provided viaMurderous Maths, gives you a helping hand 

THE QUEENS PUZZLE 

Devised in 1850, the Queens Puzzle originally challenged a player to place eight queens on a standard eight by eight square 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. 

There is more than one potential solution. 

The game has since been expanded as way of exploring complex mathematical computations. 

The St Andrew’s team found that when the chess board reached 1000 squares by 1000, computer programmes could no longer cope with the vast number of options.

This means that they sank into a potentially eternal struggle akin to the fictional super computer Deep Thought in Douglas Adams’ Hitchhiker’s Guide to the Galaxy.

Professor Ian Gent and his colleagues became interested in the Queens Puzzle after a friend challenged Professor Gent to solve it on Facebook.  

Although the problem has been solved by humans, once the chess board involved increases to a large size no computer software can solve it.

The team concluded that 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 to many modern problems.

The $1 million prize money itself is being offered by the Clay Mathematics Institute in Peterborough, New Hampshire.

The reason these problems are so difficult for computer programmes is that there are so many options to consider – it can take years.

They use a process called backtracking, an algorithm where every possible option is considered and then backed away from until the correct solution is found.

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

Devised in 1850, the Queens Puzzle originally challenged a player to place eight queens on a standard eight by eight square chessboard so that no two queens could attack each other.

Although the problem, called the Queens Puzzle, has been solved by human beings, once the chess board involved increases to a large size no computer software can solve it. Professor Ian Gent (L) with Dr Peter Nightingale (R)

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. 

There is more than one potential solution. 

The game has since been expanded to progressively larger theoretical board sizes, as a way of exploring complex mathematical computations.   

The St Andrew’s team found that when the chess board reached 1000 squares by 1000, computer programmes could no longer cope with the vast number of options.

This means that they sank into a potentially eternal struggle akin to the fictional ‘super computer’ Deep Thought in Douglas Adams’ Hitchhiker’s Guide to the Galaxy.

In the classic science fiction comedy series, the machine took seven and a half million years to provide an answer to the meaning of the universe.

Dr Peter Nightingale, part of the St Andrew’s team, added: ‘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.’ 

The full findings were published today in the Journal of Artificial Intelligence Research.

A prize of $1 million (£776,478) could be taken home by anyone who can build an app to solve a supposedly 'simple' chess puzzle. Professor Ian Gent (R) with Dr Peter Nightingale (L) from the University of St Andrew's believe the calculations involved would take thousands of years

A prize of $1 million (£776,478) could be taken home by anyone who can build an app to solve a supposedly ‘simple’ chess puzzle. Professor Ian Gent (R) with Dr Peter Nightingale (L) from the University of St Andrew’s believe the calculations involved would take thousands of years

Read more at DailyMail.co.uk


Do you like it? Share with your friends!


Comments are closed.