View all newsletters
Receive our newsletter - data, insights and analysis delivered to you
  1. Technology
  2. Software
August 31, 2017updated 01 Sep 2017 4:48pm

Could you win $1 million by solving ‘simple’ chess puzzle?

Can you solve the notorious Queen's Puzzle?

By Ellie Burns

Researchers at the University of St Andrews have thrown down the gauntlet to computer programmers, offering a $1 million prize to those who can solve the famous ‘Queen’s Puzzle’. However, before all you computer programmers get you hopes up for a big win, the ‘simple’ puzzle is by no means straightforward and could actually take thousands of years to solve.

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

Computer Scientist Professor Ian Gent and his colleagues, Senior Research Fellow Dr Peter Nightingale and Reader Dr Christopher Jefferson, found that once the chess board board reached 1000 squares by 1000, computer programs could no longer cope with the vast number of options.

Could you win $1 million by solving ‘simple’ chess puzzle?

The challenege was detailed in a paper published in the Journal of Artificial Intelligence Research, with the $1m prize offered by the Clay Mathematics Institute in America.

The team likened the potentially eternal struggle 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.

Although many may say that a solution to the puzzle will not bring about the answer to the meaning of life, the university researchers believe that any program capable of solving the problem would be so powerful that it would be capable of solving tasks currently considered impossible, such as decrypting the toughest security on the internet.

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

Content from our partners
Green for go: Transforming trade in the UK
Manufacturers are switching to personalised customer experience amid fierce competition
How many ends in end-to-end service orchestration?

Computer programs, however, have a problem with problems such as the Queen’s Puzzle due to the number of possibilities. Due to there being so many options to consider, a solution 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.”

Over to you computer programmers – think you can solve it?

Topics in this article :
Websites in our network
Select and enter your corporate email address Tech Monitor's research, insight and analysis examines the frontiers of digital transformation to help tech leaders navigate the future. Our Changelog newsletter delivers our best work to your inbox every week.
  • CIO
  • CTO
  • CISO
  • CSO
  • CFO
  • CDO
  • CEO
  • Architect Founder
  • MD
  • Director
  • Manager
  • Other
Visit our privacy policy for more information about our services, how New Statesman Media Group may use, process and share your personal data, including information on your rights in respect of your personal data and how you can unsubscribe from future marketing communications. Our services are intended for corporate subscribers and you warrant that the email address submitted is your corporate email address.