$16$ rooks on a chess board.

Question

Place $8$ pairwise non-attacking white rooks and black rooks on a $8\times8$ chess board. If one can swap rows and columns, is it possible for the black rooks to take the initial position of the white rooks and vice versa?

My attempt:

Let the rows be $a_1,a_2,...,a_8$ and columns $b_1,b_2,...,b_8$. If there are white rooks at ($a_i$,$b_j$) and ($a_j$,$b_a$) as well as black rooks at ($a_i$,$b_i$) and ($a_j$,$b_j$), then we can reduce it to a $2\times2$ and a $6\times6$.

I don't know what to do next. Any help appreciated.

Answer 1

Imagine you have two chessboards - one with the initial position and one with the final position (the one you wish to achieve). Assume that you perform the same row and column swaps on both boards. If, after some time, you are able to reach a position where:

• There is 4 'squares'
• Each square has two black rooks and two white rooks. The black rooks are at opposite corners and the white rooks are at opposite corners

then the answer would be yes, since you can just swap the rows that make up the square followed by the columns that make up the square in the first board, and you arrive at the position on the second board.

Answer 2

The answer is yes, it is possible. It is in fact true on any $n\times n$ chessboard. I have a solution which is easy enough to understand provided you know a little group theory. In particular, you need to be comfortable with the symmetric group.

Number the rows and columns of the board $1,2,\dots,n$. For every $i$, there is a single white rook in row $i$; let $\pi_i$ be the column of that rook. Similarly, let $\rho_i$ be the column of the black rook in row $i$. Then $\pi$ and $\rho$ are permutations.

We are allowed to permute the rows and columns of the board. Let $\sigma$ and $\tau$ represent the permutations of the rows and columns. These are valid solutions if and only if $$ \sigma\pi\tau=\rho\qquad \text{and}\qquad \sigma \rho \tau=\pi $$ Solving the first equation for $\tau$, and plugging that expression into the second equation, we get $$ \sigma\rho\pi^{-1}\sigma^{-1}\rho=\pi $$ or $$ \sigma(\pi\rho^{-1})^{-1}\sigma^{-1}=\pi\rho^{-1}\tag1 $$ Equation $(1)$ is satisfiable if and only if the permutation $\pi\rho^{-1}$ is conjugate to its inverse. But every permutation is conjugate to its inverse, as any permutation $\alpha$ and its inverse $\alpha^{-1}$ have the same cycle structure. The inverse of a permutation is found by reversing the elements of each cycle, which does not affect the structure.