Winning starts with what you know
The new version 18 offers completely new possibilities for chess training and analysis: playing style analysis, search for strategic themes, access to 6 billion Lichess games, player preparation by matching Lichess games, download Chess.com games with built-in API, built-in cloud engine and much more.
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 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."
Here are the twelve solutions that exclude rotations and reflections:
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.”
