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.

More Wordle Statistics

My last post titled Wordle Statistics was long enough so I didn't want to add more newly found information to that and hence I'm making a fresh post. 3Blue1Brown has just created a YouTube video that involves a statistical analysis of Wordle.

There's a lot to digest in this video but my main takeaway after first viewing it was that CRANE was a good starting word! I clearly need to watch it again and again to fully absorb what he's saying. However, for today's Wordle I started with CRANE and the results were almost disastrous as can be seen in Figure 1.

Figure 1

Looking at Figure 1, it can be seen that I had a spectacular start with three letters in the correct positions. There were only two remaining letters to guess. However, I nearly failed because there were just so many possible words that could be made from *RA*E. 

Referring to kaggle, a database of English word frequencies, we can see that TRADE was a good second choice because it has by far the highest frequency. Had I known about word frequencies, my third choice would have been FRAME and I would have solved the puzzle in a mere three attempts.

CRANE: 4,888,961 FIFTH

                                        TRADE: 110,086,585 FIRST

                                        ERASE: 3,086,642 SIXTH

                                        GRACE: 17,642,126 THIRD

BRAKE: 9,321,885 FOURTH

                                        FRAME: 46,079,991 SECOND 

Using Google search with quotes e.g. "trade" yields the following statistics:

CRANE: 166,000,000 SIXTH

                                         TRADE: 1,930,000,000 SECOND

                                         ERASE:  242,000,000 FIFTH

                                         GRACE:  918,000,000 THIRD

 BRAKE:  503,000,000 FOURTH

                                         FRAME:   2,350,000,00 FIRST

Interestingly, using the Google search, FRAME and TRADE swap places with the former being markedly more frequent (in searches at least). CRANE and ERASE also swap positions in fifth and sixth places.

I downloaded the CSV file of word frequencies from kaggle (it's only 5MB) and filtered out words that were not five letters in length. Here are the initial five letter words with the highest frequencies:

about 1,226,734,006

other 978,481,319

which 810,514,085

their         782,849,411

there 701,170,205

first         578,161,543

would 572,644,147

these 541,003,982

click         536,746,424

price         501,651,226

state         453,104,133

email 443,949,646

world 431,934,249

music 414,028,837

after         372,948,094

video 365,410,017

where 360,468,339

books 347,710,184

links         339,926,541

years 337,841,309

As can be seen, ABOUT comes out clearly on top with a frequency of over 1.2 billion! This might not be a bad starting word. Anyway, more food for thought went tackling Wordle.

Odds and Evens: Statistics

 This post won't make much sense unless my previous posts on this topic are read:

• Odds and Evens on June 17th 2021
• Attractors, Vortices and Captives on June 18th 2021
• Binary Odds and Evens on June 19th 2021

Figure 1

Figure 1 shows the sums of odd and even digits in the number systems from 10 down to 2. It also shows the ratio between the two sums. With even bases (10, 8, 6, 4 and 2), it can be seen that the sum of odd digits are larger than the sum of even digits. With odd bases (9, 7, 5 and 3), the situation is reversed.

In my previous post on Binary Odds and Evens, it was apparent that no vortices were possible and thus there were only captives and attractors. In base 10, captives could be captured by attractors and vortices. This same situation should prevail in the bases from 9 down to 3. However, the main focus of this post is to look at the first 100,000 integers and enumerate them according to the nomenclature that I have developed. What I discovered is that there are:

• 3725 attractors
• 58977 captives of these attractors
• 914 vortices with a total of 3975 vorticals
• 34223 captives of these vortices

Figure 1 shows a graphical representation of this data:

Figure 1: link

The average number of vorticals in a vortex is almost exactly four. The maximum size of a vortex in the range chosen is 11 and there are two of these:

• 81191, 81193, 81195, 81197, 81199, 81201, 81203, 81204, 81205, 81207, 81211 
• 18211, 18191, 18193, 18195, 18197, 18199, 18201, 18203, 18204, 18205, 18207

The minimum size is of course is two and there are many of these e.g. 198 --> 200 --> 198. 

Here is a permalink to the SageMathCell program that calculated this information. I did need to do a fair bit of tinkering to get it all to work but I'm very pleased with the final result.

The Chi-Square Statistic: \( \chi^{^2}_{_{_c}} \)

While perusing YouTube, the idea of a watching a video about the Chi-Square test popped into my head today and I decided to watch the video with the most views: 1,867,764 views uploaded on November 14th 2011, almost ten years ago.

I thought about how the test might be carried out in SageMath. My initial investigation didn't find anything conclusive so I turned to the trusty spreadsheet, specifically Google Sheets. I've tended to neglect spreadsheets since making use of SageMath and so this was an opportunity to revisit old territory.

What the chi-square statistic looks like is shown in Figure 1:

Figure 1

The \(c\) represents the numbers of degrees of freedom. O represents the observed frequencies and E represents the expected frequencies. For the 36 tosses of a fair die, the expected frequencies are all 6. Figure 2 shows what I came up with in Google Sheets.

Figure 2: link

The chi-square function takes the observed and expected frequencies and returns the probability that the results are due to chance alone. In the example shown in Figure 2, the probability is 0.0853 or a little over 8%. This falls short of the less than 5% that is usually regarded as the minimum requirement. 

In the worksheet, I've added superfluous information for the purpose of showing how things wre done in "the old days". I've calculated the differences between O and E, squared these and then divided by E as per the formula. The total is 9.67 and, looking at the black table in Figure 2, the cut-off point is 11.070 that appears in the 0.05 column with 5 degrees of freedom. 

Figure 3 shows the expected versus the observed results:

Figure 3

It's easy enough to get SageMath cell to carry out the necessary steps to arrive at the 9.67 result. Figure 4 shows a screenshot of the algorithm along with the permalink.

Figure 4: permalink

What I was looking for in SageMath was a function that would take the two lists as input and output the probability in the same way as the spreadsheet did. Perhaps it's possible. I'll keep investigating.

UPDATE on June 21st 2021

I just watched a video on YouTube demonstrating the application of the Chi-Square test using Excel. A manual method is used as well as making use of the built in Chi-Square function. The video does a good job of explaining the statistic using a 3 x 3 table as an example.

The Collatz Conjecture Revisited

Some time ago I posted about the Collatz Conjecture. Today's and yesterday's numbers (25183 and 25182 respectively) are connected to this conjecture. In general, these numbers arise because I'm tracking the number of days that I've been alive, numbering the day I was born (April 3rd 1949) as day zero and counting forward from there.

Both numbers appear in the Online Encyclopaedia of Integer Sequences (OEIS) A224303, whose members comprise numbers n for which number of iterations to reach the largest equals number of iterations to reach 1 from the largest in Collatz (3x+1) trajectory of n.

It's easy enough to set up a spreadsheet that calculates the number of steps to reach 1 and also the number of steps to reach the largest number in the trajectory. This is what I've done in Google Sheets and I've included a screenshot below for 25183.

As can be seen, 116 steps are required to get to the largest number (6,810,136) in the trajectory and then the same number of steps to reach 1, making for 232 steps in all. The steps for the previous number 25182 are the same. Here is a graph of the trajectory:

Looking at the sequence of such numbers, it's apparent that they tend to cluster and often appear in groups of two or more. Here is the list as it is shown in OEIS A224303 (with clusters shown in different colours):

1, 6, 120, 334, 335, 804, 1249, 2008, 2010, 2012, 2013, 6556, 6557, 6558, 6801, 6802, 6803, 7496, 7498, 7500, 7501, 7505, 10219, 22633, 25182, 25183, 27074, 27075, 27864, 27866, 27868, 31838, 31839, 32078, 36630, 36633, 36690, 36691, 36914, 39126, 39344

The second member of the sequence, 6, is given as an example: 6 is in the list because the Collatz trajectory of 6 is {6, 3, 10, 5, 16, 8, 4, 2, 1} and four steps are required to reach the largest number number (16) and four steps are required to reach 1 from 16:

6 --> 3 --> 10 --> 5 --> 16 and then 16 --> 8 --> 4 ---> 2 --> 1

Of course, there's a site on the Internet that will calculate the number of steps and graph the result. It also contains other interesting information relating to the Collatz conjecture. My spreadsheet will graph the trajectory but one has to manually alter the upper bound to get the best looking graph. I haven't figured out a way to adjust it automatically but I'll keep working on it.

Remember that the rule is to divide by 2 if the number is even and multiply by 3 and add 1 if the number is odd (hence the "3x+1 problem" as an alternative moniker). However, the site mentioned also allows one to customise the algorithm, so that for example instead of multiplying by 3, one can multiply by 2.

Interestingly, the trajectory still reaches 1 but it takes 669 steps and it's graph is quite different to that followed using the standard algorithm. Using larger multipliers like 4 doesn't seem to lead to convergence. For example after 10000 iterations using 4 as the multiplier, one gets 6,922,158,704,601,770. I'm not sure what happens with more iterations. The site also has a page for testing Lychrel numbers. I've looked at these sorts of numbers before but hadn't realised that they were called Lychrel numbers. I'd been referring to the algorithm to find them, namely reverse and add. See this post and this post to view.

See also: https://voodooguru23.blogspot.com/2018/03/the-px1-map.html

Read about Terence Tao's latest discovery: https://t.co/h8cMC9QKes