8 Lonely Queens
In 1848 Max Bezzel published what has become one of the most famous chess puzzles in history. His article appeared in the German chess magazine Die Schachzeitung and introduced the ‘8 Queens’ problem. The task is to place 8 queens on the board such that none of them attack any other. In other words, no two queens share the same rank, file or diagonal. Before reading further, you may want to try to find a solution on your own by visiting this online practice board.
Since it was first introduced, the problem has captured the interest of many, including the famous mathematician Carl Friedrich Gauss. By 1850 Gauss and others had solved the 8 Queens problem, but it continues to be studied by mathematicians today and was generalized to that of placing N queens on an NxN board even in Gauss’ time.
It is no wonder that mathematicians became interested in the problem because it cannot reasonably be solved by simple enumeration of all possible placements of the queens since 4,426,165,368 such arrangements exist. Hidden within this rather bulky set of potential solutions are 92 actual solutions to the puzzle, but these 92 differ only in reflection and rotation from 12 base solutions.
More recently the 8 Queens problem also piqued the interest of computer scientists, again because the problem space is so large. In 1972 the renowned Dutch computer scientist Edsger Dijkstra used the 8 Queens problem in his classic study of structured programming, a free copy of which can be downloaded courtesy of the Association for Computing Machinery.
The problem remains a staple of computer programming classes to this day, and many versions of the code and demonstration applets are available on the web. For example, there is a nice animation of a recursive version of the algorithm at a site devoted to recursion animations.
If you slow the animation down, you can read the comments that accompany the code.
Below are pictured the three handsome intelligentsia, Bezzel, Gauss and Dijkstra who never met each other, but are entwined in history.
