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.