3
$\begingroup$

How many ways are there to arrange 8 rooks on an 8 by 8 chess board so that no two attack each other where 2 ways are counted as the same if they are equivalent under 1 of the 8 symmetries of the chessboard? We may take help of Burnside theorem regarding orbit stabiliser.

$\endgroup$
  • 2
    $\begingroup$ "Books" or "rooks"? XD $\endgroup$ – Franklin Pezzuti Dyer Jun 26 '17 at 18:55
  • $\begingroup$ You'll find the answer here math.stackexchange.com/questions/379882/… $\endgroup$ – Mike Jun 26 '17 at 19:00
  • 1
    $\begingroup$ You just need to divide by 8 to account for the 8 symmetries of the board. $\endgroup$ – Doug M Jun 26 '17 at 19:03
  • 2
    $\begingroup$ @DougM Don't think that's true. There are solutions which are fixed by those symmetries $\endgroup$ – user296355 Jun 26 '17 at 19:05
  • 2
    $\begingroup$ So have you tried applying Burnside's lemma? $\endgroup$ – alphacapture Jun 26 '17 at 19:07
2
$\begingroup$

The key step here is that for each of the eight symmetries of the chessboard, you want to count the number of non-attacking arrangements of rooks that are left unchanged by that symmetry.

There are no such arrangements of rooks for reflections around an axis parallel to a side of the board. I'll let you figure out why.

For the identity transformation, of course all non-attacking arrangements are unchanged so you count all of them.

For other transformations (the three non-identity rotations or the two diagonal reflections), choose a particular transformation $T$ and consider placing $8$ rooks one at a time onto an $8\times8$ chessboard in order to form a non-attacking arrangement that is invariant under $T.$

If $T$ is the $180$-degree rotation or diagonal reflections, each time you place a rook you have "occupied" not only the rank and file of that rook but also the rank and file of the image of that rook under the transformation. For the rotation or for a reflection (if the rook not on the diagonal), you can show that placing the remaining rooks reduces to the problem of finding a non-attacking arrangement, invariant under $T,$ of $6$ rooks on a $6\times6$ chessboard (the board that remains after you delete the ranks and files occupied by the first rook and its image). And each additional rook you place allows you to reduce the problem by another two ranks and files.

If $T$ is a diagonal reflection and you place a rook on the diagonal, however, the rook is its own image and "occupies" only one rank and file, so you do not immediately reduce the problem from $8\times8$ to $6\times6.$ You could consider it to be a reduction to $7\times7,$ but I think a simpler way is to observe that there must be an even number of rooks on the diagonal, so you just need to count the cases for no rooks on the diagonal, two rooks on the diagonal (which does reduce to a $6\times6$ case), four rooks, six rooks, and all rooks on the diagonal.

If $T$ is a rotation by $90$ degrees in either direction then the placement of the first rook "occupies" four ranks and four files. Starting with a $8\times8$ chessboard, after placing the first rook (which cannot be placed on either diagonal), the remaining choices come down to finding a non-attacking arrangement, invariant under $T,$ of four rooks on a $4\times4$ chessboard.

$\endgroup$
  • $\begingroup$ The 90 and 180 degree ones were easy. Any hint about counting the vertex flipping one will be appreciated. $\endgroup$ – CoffeeCCD Jun 27 '17 at 22:14
  • $\begingroup$ I think I oversimplified the diagonal case. I would deal with the cases where there are rooks on the diagonal separately from the cases where there are not. I have updated the answer with some details. $\endgroup$ – David K Jun 28 '17 at 14:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.