Depending on what circles you run in -- say, your best friend is a computer programmer and your sister is a chess prodigy -- you may already be familiar with the 8 Queens puzzle. For the rest of us, the 8 Queens puzzle (or problem or simply "8 Queens") is probably not something we spend a lot of our time thinking about.
The puzzle is simple enough. How can you place 8 queens on a chessboard so that no two attack each other? Alternately, the question is sometimes stated as "What is the maximum number of queens that can be placed on a chessboard, so that no two can attack each other," but this puzzle becomes a lot less hard when you Google that, and the term "the 8 Queens puzzle" comes up.
You might be asking yourself why on Earth anyone cares where you keep your eight queens. And yes, superficially, it is just a strategic puzzle. But (and this is where it's handy to have a best friend who codes computers) the 8 Queens puzzle is a great way to test the savvy and literacy of a programmer.
Now, don't be scared. You will not be forced to understand the intricacies of computer programming in order to keep reading. But you should know that solving the puzzle can be achieved using a programming code -- and some are more elegant than others. For instance, you can definitely find the solution using a "brute-force" program that might simply go through every possible placement, ruling out one at a time. But a sophisticated coder will be able to construct a program that has shortcuts using a more refined algorithm to find you a solution faster. Being able to come up with unusual or original ways to code a solution to a problem as broad as 8 Queens can be a great test for the savvy of a code-writer.
So while we won't be stringing 1s and 0s at you to explain how 8 Queens works, we will be giving you a few solutions to the puzzle.
Origin and Explanation of 8 Queens Puzzle
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 content is not compatible on this device.
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.
Solutions to 8 Queens
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.
- Alfed, Peter. "The N by N Queens Problem." University of Utah, Department of Mathematics. Sept. 03, 1997. (June 6, 2012) http://www.math.utah.edu/~alfeld/queens/queens.html
- Ball, Walter William Rouse. "Mathematical Recreations and Essays." Macmillan. 1919. (June, 6, 2012) http://books.google.com/books?id=hvDuAAAAMAAJ&pg=PA113&lpg=PA113&dq=franz+nauck&source=bl&ots=p3cbvU0VSQ&sig=2YOi6HdSBTv42PD74MHzY3QPBSw&hl=en&sa=X&ei=wd3OT-uoOYSG2gWZwtjFDA&ved=0CFYQ6AEwAw#v=onepage&q=franz%20nauck&f=false
- Becher, Michael. "The 8 Queens Problem." 2011. (June 6, 2012) http://www.eightqueen.becher-sundstroem.de/index.php
- Chatham, Doug. "The N+k Queens Problem Page." Morehead State University. Nov. 30, 2011. (June 6, 2012) http://people.moreheadstate.edu/fs/d.chatham/nkqueens.html
- Dealy, Sheldon. "Common Search Strategies and Heuristics with Respect to the N-Queens Problem." University of New Mexico Department of Computer Science. (June 6, 2012) http://www.cs.unm.edu/~sdealy/nqueens_presentation.pdf
- Dealy, Sheldon. "Common Search Strategies and Heuristics With Respect to the N-Queens Problem." University of New Mexico Department of Computer Science. Dec. 10, 2004. (June 6, 2012) http://www.cs.unm.edu/~sdealy/nqueens_proj.pdf
- Edwards, Jon. "Chess is Fun." Princeton University. (June 6, 2012) http://www.princeton.edu/~jedwards/cif/intro.html
- Glaisher, J.W.L. "Glaisher on the problems of the eight queens." Philosophical Magazine and Journal of Science. July-Dec. 1874. (June 6, 2012) http://books.google.com/books?id=nKxSCc5_cCcC&pg=PA457&lpg=PA457&dq=glaisher%20on%20the%20problem%20of%20the%20eight%20queens&source=bl&ots=3FsFz-lPDF&sig=66bdEtWGsZQy3jkzcR3VDgQEOyU&hl=en&ei=8Jl-TuijA4nWiALumYCYCQ&sa=X&oi=book_result&ct=result&resnum=2&ved=0CCYQ6AEwAQ#v=onepage&q=glaisher%20on%20the%20problem%20of%20the%20eight%20queens&f=false
- Godden, Kurt. "Eight Lonely Queens." Chess.com Blog. June 21, 2008. (June 6, 2012) http://blog.chess.com/kurtgodden/8-lonely-queens
- Hoffman, E.J., et al. "Constructions for the Solutions of the m Queens Problem." Mathematics Magazine. Vol. 42, no. 2. 66-72. March 1969. (June 6, 2012) http://penguin.ewu.edu/~trolfe/QueenLasVegas/Hoffman.pdf
- Schachclub Ansbach. "Max Frederick Wilhelm Bezzel (translated from German)." (June 6, 2012) http://www.schachclub-ansbach.de/chronik_bezzel.htm
- Shah, Karan. "8 Queens Problem (1st Lab)." Algorithm Lectures. Jan. 5, 2010. (June 6, 2012) http://bvmalgolectures.blogspot.com/2010/01/8-queens-problem1st-lab.html
- Spivey, Mike. "Solving n-Queens with determinants." Mathematics - StackExchange.com. Sept. 25, 2011. (June 6, 2012) http://math.stackexchange.com/questions/67236/solving-n-queens-with-determinants
- The Chess Store. "Rules for Playing Chess." 2012. (June 6, 2012) http://www.thechessstore.com/category/rulesofchess/
- Wall, Bill. "Great Chess Composers." Chess.com. Aug. 7, 2007. (June 6, 2012) http://www.chess.com/article/view/great-chess-composers
- Weisstein, Eric W. "Gauss, Karl Friedrich." Eric Weisstein's World of Science. 2007. (June 6, 2012) http://scienceworld.wolfram.com/biography/Gauss.html
- Weisstein, Eric W. "Queens Problem." From MathWorld--A Wolfram Web Resource. (June 6, 2012) http://mathworld.wolfram.com/QueensProblem.html