Solve a 'Simple' Chess Puzzle, Win $1 Million (st-andrews.ac.uk)

An anonymous reader brings an important announcement: 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 $1 million 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 [PDF] 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 $1 million 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 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.

Comments

The actual content of the article

[Anonymous Coward]

Three researchers proved that the queen problem is NP-complete. The prize is the millennium prize for P=NP. The journal publication is at http://jair.org/papers/paper5512.html.

The story is mis-worded. You did it again editors.

[Jack9]

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

It's not the solution that gets you the prize, but the proof that the solution can be done quickly (without exploring nearly every permutation).