Permuting rows and columns to switch white rooks with black rooks

Question

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:

Answer 1

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.