# Permuting rows and columns to switch white rooks with black rooks

An adversary places eight white rooks and eight black rooks on sixteen squares of a chessboard, subject to these rules:

• In any row, there must be exactly two rooks, one of each color.
• In any column, there must be exactly two rooks, one of each color.

Your goal is then to apply a number of moves in order to achieve the same configuration, but with the colors reversed. Every valid move consists of switching two rows, or switching two columns.

Can you always succeed, no matter how the adversary places the pieces?

Click on the pictures to be taken to an online editor where you can play with the rooks.

A possible initial condition:

The result of switching rows 2 and 4:

The result of switching columns d and g:

The goal posiiton:

• Nice puzzle with a very clever solution! If I may offer a suggestion on the presentation (though there's really no way to beat Lichess's ease of use), tic-tac-toe pieces or go stones might have been a better fit for this puzzle: to me, at least, chess rooks always bring to mind their distinctive rules of movement, but in this puzzle, you aren't supposed to move the pieces like that.
– Bass
Commented Jun 15, 2018 at 11:00

Yes, this is always possible.

Method:

First we split the problem into one or more sub-problems by condensing chains of rooks:

This rook chain can be condensed into the following smaller problem:

We now apply a neat algorithm:

We first choose an arbitrary pair of rooks and switch them. This switch, done with either a row or column swap, will affect the positions of exactly two other rooks. These rooks align to a different diagonal of their bounding rectangle, in orange. This is simply a convenient intermediate step that allows us to finish switching these two rooks by another row/column swap. This once again displaces two other rooks, bounded in purple, and we rinse and repeat.
Simply repeat this algorithm for each rook chain, and we are done.