Non-attacking Queens

 I came across this interesting tweet today. Figure 1 shows a snapshot of it.

Figure 1

Here is the Python code that was used:

from itertools import permutations

col = range(8)

for vec in permutations(col):

    if (8 == len(set(vec[i]+i for i in col) == len(set(vec[i]-i for i in col))):

        print(vec)

The algorithm works perfectly well. Here is the output:

(0, 4, 7, 5, 2, 6, 1, 3)

(0, 5, 7, 2, 6, 3, 1, 4)

(0, 6, 3, 5, 7, 1, 4, 2)

(0, 6, 4, 7, 1, 3, 5, 2)

(1, 3, 5, 7, 2, 0, 6, 4)

(1, 4, 6, 0, 2, 7, 5, 3)

(1, 4, 6, 3, 0, 7, 5, 2)

(1, 5, 0, 6, 3, 7, 2, 4)

(1, 5, 7, 2, 0, 3, 6, 4)

(1, 6, 2, 5, 7, 4, 0, 3)

(1, 6, 4, 7, 0, 3, 5, 2)

(1, 7, 5, 0, 2, 4, 6, 3)

(2, 0, 6, 4, 7, 1, 3, 5)

(2, 4, 1, 7, 0, 6, 3, 5)

(2, 4, 1, 7, 5, 3, 6, 0)

(2, 4, 6, 0, 3, 1, 7, 5)

(2, 4, 7, 3, 0, 6, 1, 5)

(2, 5, 1, 4, 7, 0, 6, 3)

(2, 5, 1, 6, 0, 3, 7, 4)

(2, 5, 1, 6, 4, 0, 7, 3)

(2, 5, 3, 0, 7, 4, 6, 1)

(2, 5, 3, 1, 7, 4, 6, 0)

(2, 5, 7, 0, 3, 6, 4, 1)

(2, 5, 7, 0, 4, 6, 1, 3)

(2, 5, 7, 1, 3, 0, 6, 4)

(2, 6, 1, 7, 4, 0, 3, 5)

(2, 6, 1, 7, 5, 3, 0, 4)

(2, 7, 3, 6, 0, 5, 1, 4)

(3, 0, 4, 7, 1, 6, 2, 5)

(3, 0, 4, 7, 5, 2, 6, 1)

(3, 1, 4, 7, 5, 0, 2, 6)

(3, 1, 6, 2, 5, 7, 0, 4)

(3, 1, 6, 2, 5, 7, 4, 0)

(3, 1, 6, 4, 0, 7, 5, 2)

(3, 1, 7, 4, 6, 0, 2, 5)

(3, 1, 7, 5, 0, 2, 4, 6)

(3, 5, 0, 4, 1, 7, 2, 6)

(3, 5, 7, 1, 6, 0, 2, 4)

(3, 5, 7, 2, 0, 6, 4, 1)

(3, 6, 0, 7, 4, 1, 5, 2)

(3, 6, 2, 7, 1, 4, 0, 5)

(3, 6, 4, 1, 5, 0, 2, 7)

(3, 6, 4, 2, 0, 5, 7, 1)

(3, 7, 0, 2, 5, 1, 6, 4)

(3, 7, 0, 4, 6, 1, 5, 2)

(3, 7, 4, 2, 0, 6, 1, 5)

(4, 0, 3, 5, 7, 1, 6, 2)

(4, 0, 7, 3, 1, 6, 2, 5)

(4, 0, 7, 5, 2, 6, 1, 3)

(4, 1, 3, 5, 7, 2, 0, 6)

(4, 1, 3, 6, 2, 7, 5, 0)

(4, 1, 5, 0, 6, 3, 7, 2)

(4, 1, 7, 0, 3, 6, 2, 5)

(4, 2, 0, 5, 7, 1, 3, 6)

(4, 2, 0, 6, 1, 7, 5, 3)

(4, 2, 7, 3, 6, 0, 5, 1)

(4, 6, 0, 2, 7, 5, 3, 1)

(4, 6, 0, 3, 1, 7, 5, 2)

(4, 6, 1, 3, 7, 0, 2, 5)

(4, 6, 1, 5, 2, 0, 3, 7)

(4, 6, 1, 5, 2, 0, 7, 3)

(4, 6, 3, 0, 2, 7, 5, 1)

(4, 7, 3, 0, 2, 5, 1, 6)

(4, 7, 3, 0, 6, 1, 5, 2)

(5, 0, 4, 1, 7, 2, 6, 3)

(5, 1, 6, 0, 2, 4, 7, 3)

(5, 1, 6, 0, 3, 7, 4, 2)

(5, 2, 0, 6, 4, 7, 1, 3)

(5, 2, 0, 7, 3, 1, 6, 4)

(5, 2, 0, 7, 4, 1, 3, 6)

(5, 2, 4, 6, 0, 3, 1, 7)

(5, 2, 4, 7, 0, 3, 1, 6)

(5, 2, 6, 1, 3, 7, 0, 4)

(5, 2, 6, 1, 7, 4, 0, 3)

(5, 2, 6, 3, 0, 7, 1, 4)

(5, 3, 0, 4, 7, 1, 6, 2)

(5, 3, 1, 7, 4, 6, 0, 2)

(5, 3, 6, 0, 2, 4, 1, 7)

(5, 3, 6, 0, 7, 1, 4, 2)

(5, 7, 1, 3, 0, 6, 4, 2)

(6, 0, 2, 7, 5, 3, 1, 4)

(6, 1, 3, 0, 7, 4, 2, 5)

(6, 1, 5, 2, 0, 3, 7, 4)

(6, 2, 0, 5, 7, 4, 1, 3)

(6, 2, 7, 1, 4, 0, 5, 3)

(6, 3, 1, 4, 7, 0, 2, 5)

(6, 3, 1, 7, 5, 0, 2, 4)

(6, 4, 2, 0, 5, 7, 1, 3)

(7, 1, 3, 0, 6, 4, 2, 5)

(7, 1, 4, 2, 0, 6, 3, 5)

(7, 2, 0, 5, 1, 4, 6, 3)

(7, 3, 0, 2, 5, 1, 6, 4)

In this output, 0 represents the first or bottom row, 1 the second and so on. The case of [0, 6, 3, 5, 7, 1, 4, 2], shown in the tweet, is highlighted above in bold red. I use the Mathematics specific SageMathCell which is built on top of Python and when using this the permutation function is built in (so no need to import) but it uses a capital P. Similarly, the set function uses a capital S. I've modified the code accordingly and have outputted the number of acceptable configurations. Here is the code (permalink):

L=[]
count=0
col = range(8)
for vec in Permutations(col):
    if (8 == len(Set(vec[i]+i for i in col)) == len(Set(vec[i]-i for i in col))):
        count+=1
        L.append(vec)
print("There are",count,"number of ways to arrange 8 non-attacking queens on a chessboard. They are:")
print()
for n in L:
    print(n)

The output is the same as for the Python code except that it displays the fact that there are 92 possible configurations (out of a total of 40320).

So what's going on in this algorithm. Well, let's start with col = 0, 1, 2, 3, 4, 5, 6, 7. Whatever our permutation, the elements in this range get added and subtracted sequentially to the elements in our permutation. Let's use [5, 2, 4, 6, 3, 0, 7, 1] as an example of a permutation that does equate to a successful configuration. This is shown in Figure 2 (created using a Google Worksheet). Note how the top row (Added) and the bottom row (Subtracted) each contain eight distinct numbers so that the set of both rows has a length of 8.

Figure 2

Let's now consider the permutation [5, 2, 4, 6, 3, 0, 7, 1] that does not lead to a successful configuration. This is shown in Figure 3 where it can be noted that both the top and bottom rows each contain duplicate numbers so that the length of the set is not equal to 8.

Figure 3

 It's quite a succinct and clever algorithm and it's easily modifiable to accommodate any size chess board. To investigate this further it's best to modify the algorithm slightly so that it's more flexible. Here we replace the number 8 with a variable called "size". Here is the modified algorithm with size = 7 (permalink).

L=[]
size=7
count=0
col = range(size)
for vec in Permutations(col): 

    if (size == len(Set(vec[i]+i for i in col))== len(Set(vec[i]-i for i in col))):
        count+=1
        L.append(vec)
print("There are",count,"number of ways to arrange",size,"non-attacking queens on a chessboard. They are:")
print()
for n in L:
    print(n)

The output reveals that there are 40 ways (out of a total of 5040) in which 7 non-attacking queens can be placed on a 7 x 7 chessboard. Here is the output:

 There are 40 number of ways to arrange 7 non-attacking queens on a chessboard. They are:

[0, 2, 4, 6, 1, 3, 5]

[0, 3, 6, 2, 5, 1, 4]

[0, 4, 1, 5, 2, 6, 3]

[0, 5, 3, 1, 6, 4, 2]

[1, 3, 0, 6, 4, 2, 5]

[1, 3, 5, 0, 2, 4, 6]

[1, 4, 0, 3, 6, 2, 5]

[1, 4, 2, 0, 6, 3, 5]

[1, 4, 6, 3, 0, 2, 5]

[1, 5, 2, 6, 3, 0, 4]

[1, 6, 4, 2, 0, 5, 3]

[2, 0, 5, 1, 4, 6, 3]

[2, 0, 5, 3, 1, 6, 4]

[2, 4, 6, 1, 3, 5, 0]

[2, 5, 1, 4, 0, 3, 6]

[2, 6, 1, 3, 5, 0, 4]

[2, 6, 3, 0, 4, 1, 5]

[3, 0, 2, 5, 1, 6, 4]

[3, 0, 4, 1, 5, 2, 6]

[3, 1, 6, 4, 2, 0, 5]

[3, 5, 0, 2, 4, 6, 1]

[3, 6, 2, 5, 1, 4, 0]

[3, 6, 4, 1, 5, 0, 2]

[4, 0, 3, 6, 2, 5, 1]

[4, 0, 5, 3, 1, 6, 2]

[4, 1, 5, 2, 6, 3, 0]

[4, 2, 0, 5, 3, 1, 6]

[4, 6, 1, 3, 5, 0, 2]

[4, 6, 1, 5, 2, 0, 3]

[5, 0, 2, 4, 6, 1, 3]

[5, 1, 4, 0, 3, 6, 2]

[5, 2, 0, 3, 6, 4, 1]

[5, 2, 4, 6, 0, 3, 1]

[5, 2, 6, 3, 0, 4, 1]

[5, 3, 1, 6, 4, 2, 0]

[5, 3, 6, 0, 2, 4, 1]

[6, 1, 3, 5, 0, 2, 4]

[6, 2, 5, 1, 4, 0, 3]

[6, 3, 0, 4, 1, 5, 2]

[6, 4, 2, 0, 5, 3, 1]

These numbers (92 for \(n\)=8, 40 for \(n\)=7 etc.) constitute OEIS A000170:

A000170

Number of ways of placing \(n\) nonattacking queens on an \(n \times n\) board.

The initial members of the sequence are:

• \(n=0\) --> \(1\)
• \(n=1\) --> \(1\)
• \(n=2\) --> \(0\)
• \(n=3\) --> \(0\)
• \(n=4\) --> \(2\)
• \(n=5\) --> \(10\)
• \(n=6\) --> \(4\)
• \(n=7\) --> \(40\)
• \(n=8\) --> \(92\)
• \(n=9\) --> \(352\)
• \(n=10\) --> \(724\)
• \(n=11\) --> \(2680\)
• \(n=12\) --> \(14200\)
• \(n=13\) --> \(73712 \)

One might struggle with the concept of a 0 x 0 sized chessboard but I guess it's a bit like 0!=1 and 1!=1. The algorithm, when run on SageMathCell, timed out for the cases of \(n=10\) and above.

Knight Tours

I've already made several posts relating mathematics and chess. These are:

• More on the Mathematics of Chess on Thursday, 14th November 2019
• The Mathematics of Chess on Sunday, 6th January 2019
• Hogben Numbers on Wednesday, 28th November 2018
• Chess960 on Monday, 12th February 2018
• The Mathematics of Chess Pairings on Sunday, 11th February 2018

Today I turned 25983 days old and my investigation of the number 25983 revealed an interesting chess connection. Suppose we number the squares on an infinite chess board starting with 0 and then counting in an anticlockwise spiral as shown in Figure 1.

Figure 1

Suppose we devise a Knight Tour such that the Knight starts on square 0 and then moves always to the unvisited square closest to the origin. "Closest to the origin" is meant in the sense of Euclidean distance, and in case of a tie, the square coming earliest on the spiral is chosen.

On the first move, the Knight could move to squares 9, 11, 13, 15, 17, 19, 21 or 23. All these squares are the same distance from the 0 square but 9 is chosen because it comes first in the spiral. From 9, subsequent squares are 2, 5, 8, 3, 6, 1, 4, 7, 10, 13 and so on. 

These numbered squares form OEIS A326924:

A326924

Squares visited by a knight on a spirally numbered board, moving always to the unvisited square closest to the origin.

Figure 2 shows a slightly different depiction of the squares with more squares viewable:

Figure 2

The initial terms are of the sequence are:

0, 9, 2, 5, 8, 3, 6, 1, 4, 7, 10, 13, 28, 31, 14, 11, 26, 23, 44, 19, 22, 43, 40, 17, 34, 37, 18, 15, 32, 29, 52, 25, 46, 21, 76, 47, 50, 27, 12, 33, 16, 39, 20, 45, 24, 51, 48, 77, 114, 73, 70, 105, 38, 35, 60, 93, 30, 53, 84, 49, 78, 115, 74, 41, 68, 103, 36, 61, 94, 57, 54, 85, 124, 81, ...

What's really interesting about this tour is that the knight gets trapped at the 22325th move, where it can't reach any unvisited square. The square on which the Knight is stuck is 25983!

So nothing in this post of deep mathematical significance but it always strikes me as fascinating how numbers can be associated with such diverse phenomena. In this case, it is a Knight's tour of an infinite, spirally numbered chessboard.

For information on other Knight tours visit https://oeis.org/wiki/Knight_tours. 

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.