|Eight Queens Solved!|
|Written by Mike James|
|Tuesday, 01 February 2022|
Well not really - but it is still an interesting move in the right direction to understand this most simple of configuration problems.
The eight queens problem is well known and of major use as an example of recursively solving a problem. It was first proposed in 1848 in a German chess magazine, but I first encountered it in an elegant account by Dijkstra in his Notes On Structured Programming. It was used as an example of how recursion-based backtracking can be used to solve a problem far more easily than any other approach. I can't say I've thought about it much since, apart from using it as an advanced example of recursion.
For eight queens on a standard 8 x 8 chess board there are 92 possible solutions, but there are only 12 fundamental solutions - the others are derived from symmetry. There is also only one symmetric solution, as shown below:
A more interesting problem is the generalization to n queens placed on an n x n board. Finding how many configurations there are for general n was recently proved to be NP-hard and so any solution, even approximations, are interesting. We know the exact numbers for n < 28. Beyond this our computers cannot take us - for now.
The latest news is that Michael Simkin, a postdoctoral fellow at Harvard's Center of Mathematical Sciences and Applications, has the result that there are about (0.143n)n different arrangements of n queens on an n x n board.
Mathematician Answers Chess Problem About Attacking Queens
This is being headlined as a "solution", but of course the detail is in the use of the word "about". This result is not an upper or lower bound, but an approximate order as n gets bigger. The approximation makes use of the fact that not all squares on a finite board are of equal value in placing the queen. The square in the middle makes more positions unavailable to another queen than a square on the edge. What this means is that solutions tend to use edge squares rather than central squares. The distribution of queens in a solution can be visualized as:
The techniques developed in the arXiv paper might well lead on to more results (Q(n) is the number of ways of placing n queens on an n x n board):
"This paper combined the entropy method and a randomized algorithm to determine the first and second order terms of log(Q(n)). We wonder whether similar methods might succeed in obtaining more accurate estimates. More generally, for many classes of combinatorial designs (such as Steiner systems and high-dimensional permutations), denoting by X(n) the number of order-n objects, the first and second order terms of log(X(n)) have been determined using similar methods. It would be very interesting to improve these estimates."
THE NUMBER OF n-QUEENS CONFIGURATIONS
or email your comment to: email@example.com
|Last Updated ( Wednesday, 02 February 2022 )|