8 Lonely Rooks
Submitted by
on Wed, 07/02/2008 at 11:09am.
Chess is a mental playground for mathematicians. How many ways can you place 8 rooks on a chessboard such that none of them attacks another? This is similar to the 8 Lonely Queens problem that I discussed in another blog. For the rooks, there is only one solution for approximately every 109,776 different ways of placing the rooks on the board. However, if you drew the conclusion that there must not be very many solutions, you would be wrong. There are, in point of fact, 40,320 solutions to the rook problem.
This is easy to calculate. There are 8 ways of placing the first rook on file a. There are 7 ways of placing the second rook on file b. You only have to be careful not to place it on the same rank as the first rook. Thus, there are 8 * 7 = 56 different ways of placing the first two rooks on files a and b. With each rook on the board, the number of valid ways of placing the next rook is decreased by one. Continuing in this way there are 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 40,320 solutions.
The information in the first two paragraphs implies that there must be an amazingly large number of ways to place the 8 rooks onto the board. Again, the math is simple. There are 64 different squares on which to place the first rook. There are 63 other squares where you can place the second rook. Continuing with this pattern, there is the honking huge number of 64 * 63 * 62 * 61 * 60 * 59 *58 *57 = 178,462,987,637,760 different ways to place the 8 rooks on the chessboard.
But don’t honk just yet because I have deceived you in a sense. Consider the accompanying picture that shows the rooks all on a diagonal. If you rearrange the actual rooks in some way, but still keeping them on the same diagonal (e.g. swap the two rooks on the first two ranks), you would still have the same picture. If we eliminate all permutations due to swapping, then our number is significantly smaller – a mere 4,426,165,368.
Dividing this number by the number of rook solutions, and then rounding, gives us the 109,776 number cited in the first paragraph. That’s still a pretty large haystack to bury each solution in.
Returning to those solutions, a great many of them are either rotational or reflective transformations of the others. If we consider any such transformations as being equivalent then our 40,320 solutions reduces to 5,282 distinct solutions to the 8 Lonely Rooks problem – still a large number, especially when compared with the 12 distinct solutions for the 8 Lonely Queens problem.
But this should not be overly surprising since the queens problem involves the additional constraint that the queens cannot be on the same diagonal, which greatly reduces the number of possible solutions.
Your homework is to compile the 5,282 distinct rook solutions and publish them on the web. This assignment is not as hard as it might seem if you are a programmer. Extra credit will be given for identifying the 12 solutions that are configurationally identical to the 8 distinct queen solutions.
| 1585 reads | 9 comments