Introduction
The eight queens problem relies on a very simple chess-based concept. However, no chess knowledge, other than this background, is required. Chess is a game plajghyed on a 8 by 8 grid of 64 squares. The grid is checkered with two colors, usually white and black, the bottom right hand corner being white. The players sit opposite of each other and have sixteen chess pieces that they use to attempt to win the game. The objective of the game is to use your sixteen chess pieces to checkmate the kingthat is, having the king in a situation where he is unable to move without being in threat of being captured by an opponents piece. Each chess piece has certain chess rules which governs the way each chess piece may move. One of the pieces is called the Queen.
The Queen is ultimate piece of the chess board being able to move in any direction and for any number of squares.2How many ways can eight queens be placed on a chess board so that no other queen will attack another? A queen can attack any other queen along the eight paths which extend from queen. These paths are vertically, horizontally, and diagonally.
Development
Some observations must be made before attempting to solve this problem. Since there is a 8 by 8 chess board and 8 queens, then there must be a queen on each row. Also, a chess board has four black, and four white squares in each row. That would mean that half of the queens must be placed on black squares and half of the queens must be placed on the white squares.5Each chess square will be labeled in the method shown in figure 1.
Figure 1Each coordinate on the chess board such as (4,5) or (x,y) will be referred to as being S. Again, a queen can attack anyone diagonally, vertically, or horizontally.6 Mathematically, a queens diagonal dominance can be described by using the coordinates and adding A or B to x and y, and A being a variable in the domain 1-1.7( X + A, Y + A ) right diagonal dominance of the queen( X + B, Y- B) left diagonal dominance( X, A ) vertical dominance of the queens domain( Y, A ) horizontal dominance of the queens domain.
When any other queens are placed on the chess board, it cannot be placed on any of the coordinates listed in Table 1 because it would fall into this queens dominance. This would be true for any other queen that will be placed on the board.8The second queen will have six squares from which it can be placed since two of them have been dominated by the first queen. The queen will be unable to be placed in the second row in the coordinates (2,2) or (1,2). The second queen is able to be placed on the squares with the coordinates (3,2), (4,2), (5,2), (6,2), (7,2), and (8,2). There are many factors that must be considered before placing the next queen. One goal is to leave as many squares open that do not vertically align with any other squares on any other rows. For example, if a queen is placed on (3,2) then it would leave four squares open on rows 3, 4, 5, 6, and 7.
Because there are only 8 squares across a chess board, four being left open in five rows would result in vertically aligned rows. Many of the squares would be eliminated quickly because many are aligned vertically together resulting in less squares made available than 8 because once a queen is placed in any of the remaining “free” squares, then the “free” vertically above and below that queen would be dominated along with the diagonal pathways that the queen would dominate also. Since this is true, then the next queen must leave the minimum number of spaces greater than one that do not align vertically and increase in the number of squares available for each ascending row. Keep in mind that half of the queens must be placed on white, and half of the queens must be placed on black. Table 2 shows the resulting “dominated” spaces for each possible placement of the second queen.
The next step is to determine where to place the next queen. If the next queen is placed on (3,2) then it would leave a maximum of five vertically aligned queens in a single column. The coordinate (4,2) will also leave a maximum number of five vertically aligned “free” spaces in a single column. The coordinate (5,2) will leave a maximum of four vertically aligned spaces. The coordinate (6,2) will leave a maximum of four vertically aligned. The coordinate (7,2) will leave a maximum number of four vertically aligned squares. The coordinate (8,2) will leave a maximum of 5 “free” squares. Since the minimum number of vertically aligned squares is four, then it can be assumed that the next queen can either be placed on (5,2), (6,2), or (7,2). The other factor that can be considered is since half of the queens must be on black, and the other half on white, the process can be made easier by choosing the black square. If a white square was chosen, it would make the next queen have a 50% chance of being on either a white or black square.
There are now six queens left to be placed on the board still. It is known that two more queens must be on black, and four more queens must be on eight. The likelihood of the next queen being on white is greater than the likelihood of the next queen being placed a black square. In order to determine the number of “free” squares in the third row, refer to Table 1 and Table 3. All coordinates linked with the third row show dominance. The squares dominated by the queens on the coordinates (1,1) and (6,2) in row three are (1,3), (3,3), (5,3), (6,3) and (7,3). This leaves the squares on (2,3), (4,3), and (8,3) “free.” Since all of the “free” squares are white, the maximum number of vertically aligned squares in each column resulting from each option of placement of the next queen must be checked.
The next queen has the choice of being placed on (2,4) (3,4) and (5,4). The coordinate (2,4) leaves a maximum of two vertically aligned squares. The coordinate (3,4) leaves a maximum number of two vertically aligned squares also, but the last coordinate leaves no number of vertically aligned squares meaning that it has a position where it will dominate enough spaces so that there will not be enough spaces four the remaining four queens. Chances are greater that the placement of this queen will be on white because 2/6 of the queens are on black already and 1/6 are on white. In most cases, there is only one solution to the fourth queen if the two factors are taken into consideration for each queen. The white square on (3,4) will be chosen leaving only one “free” square on the fifth row(7,5). Once the next queen is placed on the board at (7,5), it will leave only one “free square for the sixth row located at (4,6). Again, placing the queen at this location will only leave one “free” square in the next row at (2,7). Once the seventh queen is placed at the only remaining square in the seventh row, the last queen is left with only one choice located at (5,8).13
Conclusion
Using this method, the number of solutions can be found. The solutions starting with queens on (1,1), (2,1), (3,1), and (4,1) are just reflections of solutions that would be found on (8,1), (7,1), (6,1), and (5,1).
Also, all solutions found on the squares (2,1) through (7,1) can be rotated 90 degrees, -90 degrees, and 180 degrees to obtain the total count of all possible solutions. Or the number of solutions found on the squares (2,1) through (7,1) can be multiplied by four to obtain the same answer. After using this method of solving four eight queens, 12 solutions can be obtained with each queen beginning on (1,1) through (4,1). Figure 5 shows the twelve solutions found by using this method.14By multiplying the number of solutions found on the coordinates (1,1) through (4,1) by 2, then the other side of the board at (5,1) through (8,1) can be accounted for. Then, by multiplying the result, 24, by four, the answer is 96, but four must be subtracted because the solutions at the corners of the chess board cannot be rotated. The number of solutions to the eight queens problem is 92.15
