1

Téma: Why the world's toughest maths problems are much harder than a chess p

The above picture shows a chessboard with two queens placed on it. As the queens do not share the same row, column or diagonal of the chess board they are not attacking each other. Can you place another six queens on the board so that none of the eight queens are attacking each other? And if it’s possible, how many ways are there to do it?

This illustrated puzzle using a typical chessboard, an example of what is called the 8-queens completion problem, is from 1850. Yet only now, in a paper written by Chris Jefferson, Peter Nightingale and me published in the Journal of Artificial Intelligence Research, have we confirmed the depth of complexity hidden within the puzzle when scaled up to allow for boards of any size, with any number of queens pre-placed in any arrangement on the board – a much harder version of the puzzle known as n-queens completion.

Unfortunately, due to misunderstandings when our paper was reported by the media (here for example, or here with correction) many people now think I am going to pay them US$1m. I am sorry to disappoint them, and hope here to put the record straight.





For More Animated Marketing Video