Queen Polynomials

Given that rooks capture along rows and columns, and given that bishops attack along diagonals, it only seems natural that non-taking queen placements on a board are somehow related to non-taking rook and bishop placements on the same board. We’ve been working with Rook Polynomials and Bishop Polynomials, so maybe we can combine the two in some way to give us a Queen Polynomial. We’ve also figured out how to calculate a Chess Multinomial involving rooks and bishops. How is this multinomial related to Queen Polynomials. Let’s see what we can figure out.

Capture Patterns

The obvious starting point is to get a grip on queen capture patterns. Once we place a queen on a board, which squares can be attacked, and which squares are safe? Perhaps a 3-by-3 board doesn’t help us visualize the pattern as easily as a 5-by-5 board, so let’s see what happens when we use a 5-by-5 board.

Lots of cells are being attacked by the queen, so we expect that we’ll be able to place relatively few queens on a board. Just as we’ve been doing, we can use cell decomposition to calculate the Queen Polynomial. Instead of working through an example by hand, I’m going to just jump straight to adding functionality to the script I’ve been working on, as described in this post.

Updating the Chess Polynomial Script

I’ve already made a somewhat general polynomial calculation function in Python as can be seen in the GitHub page for my script, so we just have to program the queen capture pattern in code. Seeing as a queen is just essentially a rook and a bishop rolled into one piece, and since the capture functionality for rooks and bishops was already programmed, most of the work has already been done. Here is the function that implements the queen capture pattern.

I’ve made slight modifications to the method used to print polynomials. Essentially, the new method adds a new string parameter that allows the programmer to specify which variable will be used in the printing of the polynomial. Before, it would just print out the polynomial in the variable x. Now, we can specify which letter to use for the variable.

Whenever we want to print a Rook Polynomial, we can pass in the character ‘r’. Whenever we want to print a Bishop Polynomial, we can pass in the character ‘b’. For our purposes, we can pass in the character ‘q’ when we calculate the Queen Polynomial for our upcoming example.

Example: 4-by-4 Full Board

With the software ready to go, let’s go ahead and calculate the Queen Polynomial for the full 4-by-4 board.

After running the script, we get this result.

So, assuming the logic in the script is correct (it has been right in all examples tried so far, so perhaps it works well enough), the result we get is that there are two ways to place 4 queens on a 4-by-4 board in such a way that no queens attack each other.

Here are the two valid placements of 4 queens on the full 4-by-4 board.

Comparing Queen Polynomial to Rook and Bishop Multinomials

Let’s take a look at the rook and bishop Chess Multinomial for the full 4-by-4 board. I’ll defer to my script, and show the results in a grid format.

Multinomial	r0	r1	r2	r3	r4
b0	1	16	72	96	24
b1	16	88	116	24	0
b2	92	160	36	0	0
b3	232	120	8	0	0
b4	260	48	0	0	0
b5	112	8	0	0	0
b6	16	0	0	0	0

There are a couple of things we may immediately notice.

1 Rook + 1 Bishop vs. 2 Queens

Taking a look at the Queen Polynomial, we see that the coefficient of q² is 44, which is exactly half of 88, the coefficient of rb in the Chess Multinomial.

Let’s look at what’s happening with the rook and bishop by considering two example placements.

I used 5-by-5 boards instead of 4-by-4 boards to better illustrate what’s happening. Notice that if we disregard what color shading is used, all the exact same cells have been shaded. In either board, there are only 4 cells that are still totally open. Notice that there are two ways to place the rook and the bishop to achieve this same shading.

When placing two queens in the exact same positions, we see all of the same cells get shaded (again, disregarding color.) However there is only one way to place two queens in this configuration because they are indistinguishable. If however we color the queens with two different colors, then we get two different ways to place the colored queens.

This is why we see that the coefficient of rb is twice that of q². For every valid placement of one rook and one bishop, we can swap the rook and bishop to produce another valid placement. Each valid placement of two queens thus corresponds to two valid placements of one rook and one bishop.

2 Rooks + 2 Bishops vs. 4 Queens

Maybe there’s a pattern here. If we have 4 queens, will that correspond to having 2 rooks and 2 bishops.?

Looking at the Queen Polynomial, we see there are 2 ways to place 4 queens on the full 4-by-4 board. We saw both placements above.

However, looking at the Chess Multinomial, we see that there are 36 ways to place 2 rooks and 2 bishops. It doesn’t seem too obvious how 2 and 36 are (combinatorially) related. Here are two valid placements of 2 rooks and 2 bishops that correspond to the placements we saw earlier.

All the pieces are occupying the same cells that were occupied by the 4 queens from earlier. The problem is that there are other valid placements as well.

Notice that in this configuration, the (4, 1) is now occupied whereas it was not occupied in any of the valid queen placements. The (3, 1) cell is also now unoccupied. This arrangement does not correspond to any valid queen placement.

The issue here doesn’t seem to be associating every valid queen placement with a rook and bishop placement, which we could theoretically do with an appropriate coloring scheme. Fundamentally, because rooks and bishops capture less cells than queens, rooks and bishops allow for more valid placements than queens.

As far as I can tell right now, there is no obvious way glean any information about Queen Polynomials from a rook and bishop multinomial.

What’s Next?

Nothing. This was actually as far as I was able to get when doing my thesis for my bachelors degree. I thought I was onto something when I saw the relationship between 2 queens, and 1 rook and 1 bishop placements, but I ran into trouble trying to relate other parts of the polynomials and multinomials together.

I’ll still be updating the script I wrote to include more functionality, and to make the code more organized. If I ever discover more information, I’ll definitely share whatever I find.

I might now actually start talking about stuff not related to Rook Polynomials. I guess we’ll see!