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 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.143 n queens on an n x n board.## Mathematician Answers Chess Problem About Attacking Queens
This is being headlined as a " 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):
**Mike James**is the author of**The Programmerâ€™s Guide To Theory**which sets out to present the fundamental ideas of computer science in an informal and yet informative way and devotes a chapter to a discussion of what makes a problem NP-hard.
## More InformationTHE NUMBER OF n-QUEENS CONFIGURATIONS ## Related ArticlesN Queens Completion Is NP Complete Rubik's Cube Is Hard - NP Hard Column Subset Selection Is NP-complete Unshuffling A Square Is NP-Complete Classic Nintendo Games Are NP Hard To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.
## Comments
or email your comment to: comments@i-programmer.info |
|||

Last Updated ( Wednesday, 02 February 2022 ) |