7
$\begingroup$

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:

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Bass Jun 15 '18 at 11:00
8
$\begingroup$

Yes, this is always possible.

Method:

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

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

dsadasa
We now apply a neat algorithm:
fdgdf
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.

$\endgroup$

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.