Win a Million Bucks

Seen on Slashdot.org ('News for nerds, stuff that matters'): Solve a 'Simple' Chess Puzzle, Win $1 Million. Sounds good to me! What's the catch?

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. [...] 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.

The catch is in that last sentence, 'the chess board increases to a large size'. As the original article, "Simple" chess puzzle holds key to $1m prize (st-andrews.ac.uk; August 2017), put it,

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.

A related paper, 'Complexity of n-Queens Completion' by Ian P. Gent, Christopher Jefferson, and Peter Nightingale (School of Computer Science, University of St Andrews), published in the Journal of Artificial Intelligence Research 59 (2017) explains everything. But be careful -- you'll need to be a math whiz just to get through the 'Abstract'.

Google image search on 'chess eight queens'

Even the 8-by-8 version isn't that easy to solve. An algorithmic approach of using the Knight's move to place the next Queen -- shown above in the top row, third from left (or bottom row, ditto) -- leaves two Queens on the long diagonal (a8-h1). 'Who Wants to Be a Millionaire?', indeed.