A Chess Puzzle, Part IV: A Group of Rooks

Part IV of A Mathematical Chess Puzzle:
- Part I: The Infinite Chess Board
- Part II: Ruminations
- Part III: The Pawns, Knights and Kings
- Part IV: A Group of Rooks
- Part V: Rooks and Topology
- Part VI: The Bishop
- Part VII Episode 1: The Fractal Queen
- Part VII Episode 2: The Rational Super Queen
- Part VIII Conclusion: The Transfinite Super Queen and Beyond
Review
We have been studying the (classic) “unguarded” chess puzzle, which is to say, of packing as many of one chess piece on a chess board without any of the pieces attacking any others. What we have been doing is to measure the “density”
In this post we will start to look at the other three pieces, Rooks, Bishops, and Queens, and will see how different things become. The reason things are different is that, unlike the Pawn, Knight and King, these remaining pieces have a “control region” which is unlimited, and extends out infinitely on an infinite board.
Our first clue that things are different may be seen by this analogous result from the previous post:
The Chess Density Theorem – Rooks, Bishops and Queens
DENSITY THEOREM 2: For Rooks, Bishops and Queens, their asymptotic density
In other words, on an infinite chess board, the fraction of squares you can cover with “friendly” Rooks, Bishops or Queens is vanishingly small. As a reminder, by “friendly” I mean that none of the pieces are threatening each other by standard chess rules. Also, if you were to throw a dart at the board with a densest packing of friendly pieces, the odds of hitting a nonempty square is zero.
PROOF: Unlike the Pawns, Knights and Kings, the proof of this theorem is practically a one liner, as we can easily show that for each piece X in the set {R,B,Q}, there is a constant C>0 so that if
And so the density
and so, since
For Rooks and Queens, the constant
Okay, so friendly Rooks, Bishops, and Queens have to be very sparse on the infinite board. But what do their solutions look like?
The Rook
From part one we already know at least what one unguarded Rook solution looks like on the 8-board:
Which immediately suggests a general solution on the infinite board:
On the infinite board the position looks like this (the diagonal line is infinitely thin):
We can readily see that this is indeed a solution, and it is also apparent that except for that infinitely thin line of rooks the board is empty. But are there any other solutions? There are, and they have a very interesting characteristic. At least for me…
Let’s start with a definition:
DEFINITION: A chess position
Obviously, any maximally unguarded Rook positions have the Rook property. But this is also a property of maximally unguarded Queens, so the definition is a bit more general.
If you think about it, if a position
Such functions
A group is simply a set
In any case, it can (easily) be proved that this relationship between
THE ROOK GROUP THEOREM: If
In particular, if consider only rook positions on a board
In fact, if you inspect the one example we showed for eight rooks on the standard 8-board, you can see that it corresponds to the identity element of Sym(8), ie,
This may all sound like gobbledegook, but it gives us some simple ways to cook up new examples of friendly Rook positions. For the eight board, all we need to do is write down a couple of permutations of the set {0,1,…8}.
For example consider the following two permutations:
(3,2,1,0,7,6,5,4) and (1,3,5,7,0,2,4,6).
These can be thought of as two functions, each being the ordered list of values you get by plugging in 0, then 1, then 2, and so on. The chess positions that correspond to them, are simply the graph of the functions on the board, like this:
To show how to “multiply” these two solutions to get a new one, you just compose their two permutations as functions. So for example, the first permutation takes 0 to 3, while the second permutations takes 3 to 7, so the composition of the two takes 0 to 7, and so on. We can show their group product graphically like this:
So how many solutions on the n-board are there? From our theorem above we know the answer, which is the same as the number of permutations of
Now how about
We will have to do some transfinite arithmetic. To specify a permutation
solutions. This is an uncountably infinite number of solutions, equal to c, the infinity of the continuum, the number of points on the real line.
Wow. That’s a lot of solutions.
As we will see later, the queen also has a similarly large collection of unguarded solutions, but the Rook is unique in being the only piece of the six whose solutions have a natural group structure.
In the later posts we’ll take a look at the Bishop and queen, and also start to examine fractals and even more infinite boards.