# $16$ rooks on a chess board.

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.

• If there were a white rook at $(a_i,b_j)$ and a black rook at $(a_i,b_i)$, as you suggest, wouldn't they attack each other? – Misha Lavrov Jun 14 '18 at 0:23
• The problem statement is wholly unclear. – user14972 Jun 14 '18 at 0:25
• There black rooks can attack the white rooks (and vice versa) but black rooks can't attack black rooks. – abc... Jun 14 '18 at 0:53
• @abc... It's still unclear. What is an "attack" in this context? I'm guessing it's a white piece on the same row/column as a black piece. Are attacks not allowed? Maybe include an example picture of an acceptable configuration. – Theo Bendit Jun 14 '18 at 1:42
• I think @abc means that a black rook cannot be on the same row or column as another black rook, and similarly for a white rook. However, it is possible for a white rook to be on the same row or column as a black rook. An example configuration would be all of the white rooks on one diagonal and all of the black rooks on another diagonal – Vikram Jun 14 '18 at 1:54

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.

• Beautiful!${}{}{}{}{}$ – quasi Jun 14 '18 at 17:28
• But unfortunately I don't know about group theory. Could you give me an explanation with just basic combinatorics? – abc... Jun 17 '18 at 23:22
• @abc... See puzzling.stackexchange.com/a/67221/10615 – Mike Earnest Jun 18 '18 at 0:18

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.

• How do you know that you are always able to reach a 4 'squares' position? – quasi Jun 14 '18 at 6:58