Why does the number of solutions for the $n$-Queen problem drop at $n = 6$ specifically?

Question

I was looking into determining the number of solutions to the $n$-Queens problem, admittedly to study DFS for a course.

During this study, I naturally found OEIS A000170, which lists the number of solutions. The solution count for $n = 6$ stood out, as it seems to be the only value of $n$ for which the value drops from its previous iteration.

Why does this specific board size seems to be so specific in its queen layout? Is there a nice mathematical explanation for this or is it just a neat coincidence?

When $n=7,$ I think the latin squares provide $28$ of the examples, and there are $12$ others.

Answer 1

This is a Soft Question.
Here is my thinking about it.

OBSERVATION 1 : When $a(n+1)$ can use some of the Solutions of $a(n)$ & then have additional Solutions , then we can have Increase in $a(n+1)$ compared to $a(n)$.

OBSERVATION 2 : Specifically , when the Diagonal is free , we can add the next row (+ column) & place the queen in the Diagonal. We have 4 Corners to include here.

That works in large $n$ Cases , hence $a(n)$ is generally Increasing.

Here is a Section given by https://oeis.org/A000170 :

Here , we can check that $n=4$ has the free Diagonal , hence that gives $n=5$ Solutions with the queen on the new row on the Diagonal. We have a new Independent Solution with the Diagonal in the middle , hence $n=5$ is still Increasing compared to $n=4$.
We have $a(4)=2$ which each of which gives $4$ Solutions (4 Diagonals) hence $2 \times 4 =8$ , then 2 new Independent Solutions with the Queen on the Diagonal in the middle. Hence $a(5)$ total is $8+2=10$ , where all use the Diagonal.

With all Solutions using the Diagonal , $n=6$ can not re-use the $n=5$ Solutions , hence we have a breakage here.
All Solutions of $n=6$ are new & Independent , not able to re-use the $n=5$ Solutions.
The new Solutions are not enough to Increase the Count. Hence the $a=6$ Case will have Decrease compared to $a(5)$.

Answer 2

You can take a configuration A and rotate it 180 degrees to get configuration B (which may equal A).

If $n$ is even, B is more likely to equal A than if $n$ is odd. (For $n=4$ and $n=6$, B always equals A). This is less likely to happen when $n$ is odd because configuration A would necessarily have to use the center square. So for odd $n$, that restriction means rotating a given configuration by 180 degrees is more often going to give you a new valid configuration.

So I think a part of the explanation is this general influence from parity of $n$, that as you move from an odd $n$ to an even $n$, there is an influence to reduce the count. Other combinatorial possibilities dominate this influence once $n$ is a bit larger than $6$.

Answer 3

First of all, it is very easy to find examples for $n>3$ odd and not divisible by $3.$

We start with the three orthogonal latin squares with rows and columns indexed by $\mathbb Z/n\mathbb Z$ and matrices $A,B,C$ with $$A_{ij}=i+j, B_{ij}=j-i, C_{ij}=j+3i.$$

For example, if $N=5,$

$$A=\begin{pmatrix}0&1&2&3&4\\1&2&3&4&0\\2&3&4&0&1\\3&4&0&1&2\\4&0&1&2&3\end{pmatrix},\\ B=\begin{pmatrix}0&1&2&3&4\\4&0&1&2&3\\3&4&0&1&2\\2&3&4&0&1\\1&2&3&4&0\end{pmatrix},\\ C=\begin{pmatrix}0&1&2&3&4\\3&4&0&1&2\\1&2&3&4&0\\4&0&1&2&3\\2&3&4&0&1\end{pmatrix}. $$

The key here is that if $i\neq i',j\neq j'$ and position $(i,j)$ attacks $(i',j')$ diagonally, then either $A_{ij}=A_{i'j'}$ or $B_{ij}=B_{i'j'}.$ (This is not true in reverse, but we are just constructing examples.)

So if we take all the positions from $C$ where $C_{ij}=c,$ we get ways to put the queens down.

$$c=0, \{(0,0),(1,2),(2,4),(3,1),(4,3)\}\\ c=1,\{(0,1),(1,3),(2,0),(3,2),(4,4)\}\\ c=2,\{(0,2),(1,4),(2,1),(3,3),(4,0)\}\\ c=3,\{(0,3),(1,0),(2,2),(3,4),(4,1)\}\\ c=4,\{(0,4),(1,1),(2,3),(3,0),(4,2)\}$$

The positions for $c=0,1,2,4$ are all rotations of each other. but reflectioons give us another four examples.

The positions for $c=3$ are rotationally fixed, but again, reflection gives us one more.

So we easily get all ten cases when $n=10.$

In general, if we have $n$ odd, then $C_{ij}=j+ai$ is a latin square orthogonal to $A,B$ iff $\gcd(a(a-1)(a+1),n)=1.$ For each such $a$ we get at least $n$ examples.

Now, we don't actually need $A,B$ orthogonal, we just need a latin square $C$ which is orthogonal to both $A$ and $B.$ So if we can find a latin square orthogonal to both $A$ and $B,$ we'd have more examples.

When $n=6,$ however, a well-known theorem says there is no pair of orthogonal latin squares for $n=6.$ So this approach gives us nothing.

It will be generally hard to find examples like this for $n=10,$ too, hence the small jump from $n=9$ and $n=10.$ It was long conjectured that there were no orthogonal latin squares for $n\equiv 2\pmod{4},$ only to be disproven, but even then, the number of such pairs is small, relative to other $n,$ and I don't know if there is a $C$ which works for $n=10.$

Now, of course, we don't require orthogonal latin squares to solve the $n$ queen problem, but what this shows is that when $n=6,$ the class of easy algebraic examples are missing.

---

The general solutions can be thought of in terms of permutations.

If we don't reduce modulo $n,$ and just do integer arithmetic, you can say positions $(i,j)$ and $(i',j')$ attack each other diagonally iff $i+j=i'+j'$ or $i-j=i'-j'.$ So we are seeking a permutation $\pi$ on $\{0,1,\dots,n-1\}$ such that $i+\pi(i)\neq j+\pi(j)$ and $i-\pi(i)\neq j-\pi(j)$ for any $i\neq j.$ This can be written more succinctly as: $$\pi(i)-\pi(j)\neq\pm (i-j)$$Then the points $\{(i,\pi(i)\}$ are a solution.

The examples generated by the latin squares are more specific cases where $\pi(i)-\pi(j)\not\equiv \pm(i-j)\pmod n.$

This can be considered as the special cases where the queen can also continue diagonally off one side of the board and onto another.

That gives additional symmetries - we can rotate the rows and columns, sending $(i,j)\mapsto(i+u,j+v)$ to get a new solution, as well as the eight symmetries of the sphere. So there are $n^2\cdot 8$ symmetries. So in these examples, you can potentially get a lot more examples.

In the case where $n=5,$ there is really only one orbit. Each example is fixed by $4n$ elements of the symmetry group, so there are $2n=10$ such examples.

A base answer when $n=6$ is $(0,1),(1,3),(2,5),(3,0),(4,2),(5,4).$ You can see that $2-\pi_2=-3\equiv 3= 3-\pi(3)\pmod 6,$ so this example can't come from a Latin square example. It has a 180 degree rotation symmetry, but that means it only gives $4$ examples.