How 8 Queens Works

Now that we get the basic premise of the puzzle, we should establish why the problem is so unique. To do that, let's brush up on our chess basics. In a game of chess, the queen is a force to be reckoned with. She can move in a straight line vertically, horizontally or diagonally, as many spaces as she pleases. The one catch is that she can't jump pieces, so if a pawn is in her way, she must capture it and stop.

This is what makes the 8 Queens puzzle interesting. If queens can move up, down, left, right and diagonally, then how many warring royals can occupy the board without sharing the same row, column or diagonal line? Now, you might think it'd be a terrific idea to just place a queen on the board, trying different combinations before you hit on all of them. And sure, that's possible. But there are 4,426,165,368 potential solutions, so you might consider finding a shortcut.

Before we put our queens in 4 billion different squares, let's first acknowledge that somebody actually sat down one day and decided this would be a good way to waste an afternoon or two. Predictably, it wasn't someone who had reruns of "My Big Fat Gypsy Wedding" to catch up on -- it was a 19th-century German chess master and composer named Max Bezzel. (A chess composer is someone who makes up chess problems -- also known as puzzles -- to solve.) It first appeared in the German chess magazine DieSchachzeitung in 1848.

Bezzel wasn't so interested in solving the puzzle; he was satisfied with simply posing the question. However, in 1850, mathematician Franz Nauck wrote another article that discussed the problem. (The first solutions to the puzzle were eventually solved by Nauck.) That got the attention of Karl Gauss, a 19th-century mathematician known for discovering the fundamental theory of algebra. When Gauss took an interest in finding the solution, others followed, and different approaches to solving the puzzle began to emerge.

It's not much of a surprise that "eight" is the answer to our specific question of how many queens can be placed on a board without attacking one another. But let's explore how many ways eight queens can be placed and how that is established.

We talked about how brute-force computer programs are one way to solve the puzzle -- and testing out 4,426,165,368 possibilities manually would certainly qualify as brute force -- but there are easier ways to narrow down the solutions. One simplified method was provided when J.W.L Glaisher, another mathematician, published a paper in 1874 describing his use of determinants to find a solution. "Determinants" sounds a little tough, but all you really need to know is that Glaisher basically constructed a matrix, and -- using a system he derived from that matrix -- was able to narrow down the possible solutions to 92.

And 92 solutions it remains. But don't be fooled; you won't be able to line up 92 chessboards, each with a unique set of 8 queens settled peacefully, because there are actually only 12 unique solutions.

Confused? The difference between 12 unique solutions and 92 fundamental solutions rests, literally, on how you look at it. While you could set up 12 different boards distinctively with your eight queens, all it takes is for you to simply turn the board -- or even reflect it onto a mirror -- to make the boards technically look different and thus have a "different" solution. (This is called rotational and reflective symmetry operations.) So you take your 12 unique boards, turn them 90, 180, and 270 degrees and then reflect them at each rotation. But one more thing -- one unique board is symmetrical, so it looks the same from two angles. While all the other boards have eight variants, the symmetrical board only has four. So instead of 12 boards times 8 variations (96), we're actually subtracting the four that don't exist with the symmetrical board. What do we get? 92 fundamental solutions.

Now, don't let the math fool you. You can always find yourself a chessboard and attempt to ferret out some placements for yourself. (Finding one answer, of course, is a lot easier than finding all 12.) And there are even programs on the Web that let you suss out some different solutions. (Warning: they may make you feel stupid.)

Before you shuffle your queens around, check out the next page to learn more information.

Being a person less interested in an algorithm than an alphabet, I didn't have high hopes for understanding the 8 Queens puzzle. Although I was sure it had some sort of practical application, I wasn't able to see it. Ironically, it was when I understood the vastness of the problem that I started to see why it could be useful. Finding a set of solutions from a massive amount of possibilities is one reason code exists. The 8 Queens problem challenges programmers and mathematicians alike to discover novel techniques to simplify the search.

Related Links

Sources