Solve a chess problem, win a million dollars

by Frederic Friedel
9/4/2017 – It is an old puzzle, proposed in 1848: place eight queens on a chessboard so that none are attacking another one. The solution was published two years later, but the problem of n queens on an n x n chessboard (e.g. 100 queens on a 100 x 100 board) ramains illusive. Modern computers would take thousands of years to solve the puzzle for large numbers. If you can write a program that is much faster you can win a cool million dollars. Go for it!

Expanding the Eight Queens puzzle

You probably know the problem quite well: Place eight chess queens on a regualr 8×8 chessboard so that no two queens attack each other, i.e. no two queens can share the same row, column, or diagonal.

The problem was proposed by Max Bezzel in 1848, the first solutions were provided in 1850 by Franz Nauck, who extended the puzzle to n queens on a chessboard of n × n squares. Since that time many mathematicians, including Carl Friedrich Gauss, have worked on both the eight queens puzzle and its generalized n-queens version.

An infinite chessboard — image from this cool video Infinite Chess | Source: PBS Infinite Series YouTube channel

You can try solving the 8x8 problem on this great JavaScript board provided by Ronald Daenzer, which is available at The JavaScript Source (if the board does not appear on the left go here).

Be a little careful: it is all quite addictive and you can spend a lot of time trying different strategies. As mentioned in this article on the unforgotten Martin Gardner the Eight Queens problem has 92 destinct solutions — twelve if you discount those that differ only by symmetry operations (rotations and reflections) of the board.

 

All twelve solutions are given at the bottom of the page.

Gardner took the problem further: place three white queens and five black queens on a 5 x 5 chessboard so that no queen of one colour is attacking one of the other colour. There is only one solution to this problem, excluding reflections and rotations. You may want to try to find the solution to this one – although that is not the subject of today's article.

The million dollar challenge

The eight queens puzzle is an example of the more general "n queens problem", which requires placing n non-attacking queens on an n×n chessboard. Solutions exist for all natural numbers n (with the exception of n=2 and n=3).

Professor Ian Gent and Dr Peter Nightingale | Photo: Phys.org © Stuart Nicol

Now the computer scientists, Professor Ian Gent and Dr Peter Nightingale,  at the University of St Andrews in Scotland are challenging computer programmers to solve the problem for very large values of n. The solutions using brute force for 8x8 take microseconds, but the team found that once the chess board reached 100 x 100 squares, or 1000 by 1000, computer progams could no longer handle the very large numbers in a reasonable amount of time. In fact it would theoretically take 1000 years for current programs to solve.

So Gent and Nightingale are offering a $1,000,000 prize for anyone who can come up with a quicker solution. This is quite important because, according to Gent, "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."

Solutions

Here are the twelve solutions that exclude rotations and reflections:

Update, September 5:

In reponse to reader Aighearach's criticism in the comments (which is partly correct), here's a statement from the Clay Institute:

The new research concerns the n-Queens Completion Problem, where not only is the board larger, but also some queens have already been placed. That is, if some queens have already been placed on the n-by-n board, can you find a solution to the n-Queens puzzle without moving any of those queens?  The technical contribution claimed in this paper is that the n-Queens Completion Problem falls into the class known as NP-Complete.  If correct, this means that any algorithm that can solve the n-Queens Completion Problem can be used indirectly to solve any other problem in the NP class.  This does not apply to the original n-Queens puzzle, because the addition of pre-placed queens is critical.

"Unfortunately, some reports of our work have given the impression that solving the 8-queens puzzle, or the n-queens puzzle for all n, might result in the award of the Millennium Prize. This is not the case, for two reasons. First, as just mentioned, the paper is about the n-Queens Completion problem, not the original n-Queens puzzle. Second, even the discovery of an algorithmic solution to the n-Queens Completion puzzle for all n would not be enough. What would be necessary would be either a proof that there is an algorithm that can solve the n-Queens Completion puzzle in polynomial time, or a proof that no such algorithm exists.”

Links


Topics Puzzles , Mathematics

Editor-in-Chief of the ChessBase News Page. Studied Philosophy and Linguistics at the University of Hamburg and Oxford, graduating with a thesis on speech act theory and moral language. He started a university career but switched to science journalism, producing documentaries for German TV. In 1986 he co-founded ChessBase.
Feedback and mail to our news service Please use this account if you want to contribute to or comment on our news page service



Discuss

Rules for reader comments

 
 

Not registered yet? Register

RayLopez RayLopez 9/4/2017 07:12
Sounds like a P equals NP problem. Arguably if you can solve this it's worth more than $1M if you keep it a trade secret and apply it to industry.
DrAlexanderSchmidt DrAlexanderSchmidt 9/4/2017 08:48
Exactly, Ray...
Aighearach Aighearach 9/4/2017 08:53
I wasn't surprised to see this earlier on various "tech" sites, but seeing it here is really shocking; on the tech sites the link was heavily panned because it isn't even a chess problem; I'm a bit shocked that one sailed so easily passed you. But the spoilers for people mislead by this "story:"

1. Not a chess problem, it could be done just with checkers, and you don't even need a chessboard a go board and stones work as well, because no moves are being made only placing identical items of a single type into a specified grid pattern.
2. The problem is solved. Solving the problem is also easy. Solving this problem does not win any prize at all.
3. There is no prize at all that is being offered in connection with this problem. None. The million dollar prize already existed, is given by somebody else, and is for something else. The claim is just a word game that some people play ever time another NP-complete problem is found. There are no shortage of those, it is not any meaningful, useful, or rare thing.

Even magazine editors can learn the moves of chess well enough to at least tell if a problem is a chess problem or not; but there is no excuse for an editor not even knowing what a story is about! They are NOT offering a prize! They're just playing a word game with an existing prize, and their very strong belief that any solution to P = NP must instantly solve every other P = NP problem, which is an untested hypothesis so their word game is pretty lame and not very sciencey.
rgorn rgorn 9/4/2017 08:58
Hoffman, E.J., Loessi, J.C. and Moore, R.C. (1969): Constructions for the Solution of the m Queens Problem, Mathematics Magazine, p. 66--72.

penguin.ewu.edu/~trolfe/QueenLasVegas/Hoffman.pdf

Or just as quick summary:

Bo Bernhardsson. 1991. Explicit solutions to the N-queens problem for all N. SIGART Bull. 2, 2 (February 1991), 7-

http://dl.acm.org/citation.cfm?id=122322
dengtianle dengtianle 9/5/2017 03:48
With the help of the javascript board, I solved it in 15sec! Amazing!
macauley macauley 9/5/2017 06:29
@ Aighearach - It's great to see that you're reading the article very closely and bringing your knowledge to the discussion! Indeed you're largely correct. I added an update to clarify what's new and what isn't.
kaareandersson kaareandersson 9/6/2017 07:44
Maybe chessbase can initiate a separate contest with some prizes of honour? I agree that solving for instance the 100x100 board problam likely isn't hard enough to merit one $million. I can't see that addition of pre-placed queens makes any big difference, provided the pattern is part of a bigger solution. While some solutions like affinative moves in a 3D-space or group theory based solutions may be of general interest a straightforward algorithm designed for speed will likely not be of any special interest except for in its own. Such an algorithm without optimization never seem to use any more than 0.5 seconds for a 100x100 board. Even there one can notice the complication of trap patterns which looks promising but require some kind of "simulated annealing" to be resolved. Now - how would a "proof" look like? For instance the trap patterns seem to be more common the larger the matrix. To put up an absolute proof around these kind of occurences without resorting to statistics must be close to impossible. In any case the judge can always dismiss the proof as insufficient to save their one $1000000 to another day.
wetnose wetnose 9/16/2017 06:08
For 1000x1000 with a single preplaced queen (the hardest case for nQ completion) it takes 2.5-5 hors (dependiong on the queen location) to find the 1st solution on my Core i5 3.3GHz (only one core of four is used).
1