More on the Mathematics of Chess

Figure 1: Book Cover

On Sunday, 6 January 2019, I published a post titled The Mathematics of Chess in which I discussed the number 25480 as the number of ways to place 2 non-attacking amazons (superqueens) on an 16 x 16 board. In that post, I made reference to Vaclav Kotesovec's magnum opus Non-attacking Chess Pieces that I have in my Calibre Library. Today I am reminded of its existence yet again because my diurnal age is 25792 and this turns out to be a member of OEIS A035288: the number of ways to place a non-attacking white and black bishop on n x n chessboard. 25792 arises when n=13.

This is a variation on the problem of how to place two non-attacking bishops on an n X n board. This problem is normally colour agnostic as shown in Figure 2.

Figure 2: two non-attacking bishops on an
8 x 8 board with both of the same colour

However, in the case of OEIS A035288, the two bishops are distinguishable because one is white and the other black as shown in Figure 3.

Figure 3: two non-attacking bishops on an 8 x 8 board
but with one white and the other black

OEIS A172123 deals with the number of ways to place 2 non-attacking bishops on an n x n board, where the bishops are not distinguishable from each other. The members of OEIS A035288 are simply twice the value of those in OEIS A172123. In Vaclav's book, it is these situations (where the pieces are indistinguishable) that are investigated. Figure 4 shows the table from page 241 of the book. The value of 12896 x 2 = 25792.

Figure 4: table of values for different numbers of
non-attacking bishops on varying sized boards

The author also provides generating functions for the different number of bishops and differently sized boards. I've just shown the first five in Figure 5 (taken from page 240 of the book).

Figure 5: generating function for two to five non-attacking bishops

In the case of two indistinguishable bishops, the generating function of interest is:$$-\frac{2x^2 \, (x+1) \, (x+2)}{(x-1)^5}$$This generating function can be used to generate the members of OEIS A172123. This is shown in Figure 6 for members of the sequence up to and including 12896:

Figure 6: SageMathCell code generating members of sequence A172123

The OEIS entry also lists a simple formula for determining the members of the sequence. It is:$$a(n) = \frac{n \,(n - 1) \, (3n^2 - n + 2)}{6}$$There is also a recursion formula:$$a(n) = 5 \,a(n-1)-10\, a(n-2)+10 \, a(n-3)-5 \,a(n-4)+a(n-5)$$It was good to be reminded of Vaclav's impressive book again but I also have in my possession another book titled Across the Board: The Mathematics of Chessboard Problems by John J. Watkins.

Figure 7: Book Cover

As the author says in this introduction:

... this book is about the game board itself, the simple grid of squares that forms such a common feature of games played around the world, and, more importantly, about the mathematics that arises from such an apparently simple structure.

The book contains much of interest that hopefully I'll be able to write about in later posts. Vaclav's book is really a reference source for a huge range of non-attacking pieces on various sized boards but Watkins looks a limited number of situations in detail. Figure 8 shows the very first problem that he deals with: Guarini's Problem that dates from 1520.

Figure 8: Guarini's Problem requires the white
and black knights to exchange positions

One solution involves reducing the board to a graph so that the situation is revealed more clearly. This is shown in Figure 9.

Figure 9: Guarini's Problem as a Graph

The graph clearly shows that four steps are involved, each step involving each of the four knights to advance to the next node (either clockwise or anticlockwise). If anticlockwise, then the knight on a will move to d, the knight on c will move to b, the knight on d will move to a and the knight on b will move to c.