The eight-queens chess puzzle and variations of it

[lpetrich]

Eight queens puzzle - Wikipedia -- place eight chess queens on a chessboard so that none of them attack each other.

It turns out that there are 92 solutions, though when one counts together positions related by chessboard symmetries, there are only 12 solutions.

This problem has been modified and extended in a variety of ways.

Different-sized boards. The problem has been solved for board sizes up to 27. No formula is known for the number of solutions, not even its asymptotic behavior. But the size appears to increase factorially.

Different board geometries. This problem has been studied for periodic boundary conditions: toroidal topology.

Different numbers of dimensions. This problem has been studied for cubical boards and higher-dimensional ones.

Different chess pieces. This problem has been solved or at least studied for rooks (max n), bishops (max 2(n-1)), knights, and kings. Also for "fairy chess" pieces with different kinds of moves from the canonical pieces' moves.

 

[phinds]

Is there a question in there somewhere?

 

[lpetrich]

The recent thread on chess led me to this chess-related math conundrum, one which I think has lots of interesting math in it. Math like symmetries.

 

[Helios]

At the 5 x 5 level, there are 5 solutions. The non-inter-attacking-queens, is the same rule applied to latin squares. The Greco-latin square is an extension of the idea, that I show.

 

[lpetrich]

The eight-queens problem can be generalized to the problem of finding n queens on an n*n board, n being the most that is possible in general. The number of possible arrangements grows roughly factorially (A000170 - OEIS), but no formula is known for that number, or even for its asymptotic behavior.

Now to symmetries. The transforms of a chessboard are E (identity), R2 (180d rotation), R4 (90d rotation), R4i (inverse of it), Sx1, Sx2 (axial (horizontal, vertical) reflections), Sd1, Sd2 (diagonal reflections). The possible transform groups are:
C1: {E}, C2: {E, R2}, C4: {E, R4, R2, R4i}
D1x1: {E, Sx1}, D1x2: {E, Sx2}, D1d1: {E, Sd1}, D1d2: {E, Sd2}
D2x: {E, R2, Sx1, Sx2}, D2d: {E, R2, Sd1, Sd2}
D4: {E, R4, R2, R4i, Sx1, Sd1, Sx2, Sd2}

If the board has symmetry group G and a position symmetry group H, then H must be a subgroup of G, and the number of symmetry variants of the position is the index of H in G, or |G|/|H| -- |G| is the order of G, its number of elements. This offers a quick way of counting all the symmetry-related sets of positions.

The 1*1 position is fully symmetric (D4), but all larger positions have no reflection symmetries, because such symmetries would make queens attack each other. Thus, the only multiqueen symmetry groups are C1, C2, and C4.

For n odd and C2 or C4 symmetry, there is one queen in the center square, while for n even and C2 or C4 symmetry, there are no queens in the four center squares. For C4 symmetry, n can only be 4k or 4k+1, because every non-center queen must be part of a cycle of 4 queens.

 

[lpetrich]

Latin square get their name from Leonhard Euler using Latin or Roman letters in them, though one may use any symbol, including numbers. Graeco-Latin squares have two symbols, the name coming from a pairing of Greek and Latin letters, but otherwise working much like Latin squares. All of the symbols in each row and column must be different.

n-queen n*n boards are a subset of Latin squares, with one symbol being a queen and the others being empty.

The count of all solutions to within symmetries is A002562 - OEIS, all solutions with C2 or C4 symmetry, A032522 - OEIS, and all solutions with C4 symmetry, A033148 - OEIS. Related by symmetry are sets of 8 asymmetric (C1) solutions, 4 C2 solutions, and 2 C4 solutions. The latter is a solution and a mirror image of it in any direction allowed by the board.

 

[lpetrich]

Nonattacking rooks are a much simpler problem, and their positions form a superset of nonattacking-queens positions. For n rooks on a n*n board, the maximum, there are n! possible positions.

• For at least C2 symmetry (C4, D2d), for n = 2k or 2k+1, the number of positions is 2^k * k! - A037223 - OEIS
• For C4 symmetry, the number of positions is (2k)! / k! - A037224 - OEIS
• For at least D1d1 or D1d2 symmetry (with D2d), the number of positions is a rather complicated function - A000085 - OEIS
• For D2d symmetry, i found combinatorics - Non Attacking Rooks With Symmetry On Both Diagonals - Mathematics Stack Exchange and A135401 - OEIS.

This problem is essentially a permutation problem, because arrangements of nonattacking rooks are equivalent to permutations.

 

[lpetrich]

Interpreting the possible positions of rooks as permutations of (1,...,n), one can express the symmetries in terms of the identity, E, inverses, I, and reverses (opposite order), R, with

• II = RR = E
• Sd1 = I
• Sx1 = R
• R4 = IR
• R4I = RI
• Sd2 = RIR
• Sx2 = IRI
• R2 = RIRI = IRIR

Here are the numbers for the two D1d's for size n:
$$ \sum_{k=0}^{\lfloor n/2 \rfloor} \frac{n!}{2^k k! (n-2k)!} $$
Its values N(n) satisfy recurrence N(n) = N(n-1) + (n-1)*N(n-2) with N(0) = 1.

For D2d with size 2n or 2n+1:
$$ \sum_{k=0}^{\lfloor n/2 \rfloor} 2^{n-2k} \frac{n!}{k! (n-2k)!} $$
Its values N(2n) = N(2n+1) = M(n) satisfy recurrence M(n) = 2*(M(n-1) + (n-1)*M(n-2)) with M(0) = 1.

 

[lpetrich]

Turning to bishops, for a n*n board, the maximum number of nonattacking ones is 2(n-1), with each color of square having (n-1) ones. The total number of positions is $2^n$, for even n, each color has $2^{n/2}$ positions, and for odd n, the colors have $2^{(n+1)/2}$ and $2^{(n-1)/2}$ positions each, with the more-square color having more positions (A002465 - OEIS).

The general solution has all the bishops on board edges, with all but two bishops paired by a 180d rotation. The two remaining two bishops are on the two long diagonals, one each. In coordinates 1 to n, the bishops' positions are:

• For each k from 2 to (n-1), a pair at (1,k) and (n,n-k+1), or else at (k,1) and (n-k+1,n).
• One at (1,1) or (n,n)
• One at (1,n) or (n,1)

The possible symmetries are limited. The two long-diagonal bishops break the 180d-rotation symmetry that the other bishops have, and nonattacking bishops cannot have diagonal-reflection symmetry. Thus, the only possible symmetry groups are C1, D1h, and D2h -- at most, reflection along one axis. With that symmetry, there are 2^ceiling(n/2) possible positions.

 

[lpetrich]

There are at most ceiling(n^2/2) nonattacking knights on an n*n board for n > 2, and n^2 for n <= 2 (A030978 - OEIS). The knights are all on squares of some color that includes some corner squares. Both colors for even n, one color for odd n.

There are at most (ceiling(n/2))^2 nonattacking kings on a n*n board. For odd n, there is only one position, while for even n, the number of positions grows roughly factorially (A018807 - OEIS). This happens because, for even n, the board can be divided into 2*2 blocks, with a king in each one. Kings in different blocks can have different positions in them, thus making all the overall positions.

 

[lpetrich]

An interesting variation is a toroidal chessboard, a chessboard with the topology of a torus or doughnut shape. It has periodic boundary conditions, with the right edge wrapping around to the left edge and the top edge to the bottom edge.

For n nonattacking queens on a n*n toroidal board, solutions only exist for n = 6k+1 or 6k+5 -- n must not be divisible by 2 or 3 (A051906 - OEIS).

The maximum number of nonattacking bishops on a n*n toroidal board is n, and the number of positions is $2^n ((n/2)!)^2$ for n even and $n!$ for n odd (A189790 - OEIS).

The maximum number of nonattacking kings is floor((n*floor(n/2))/2) (A189889 - OEIS). For n = 2k, this number is k^2, for n = 4k+1, this number is k*(4k+1), and for n = 4k+3, this number is (k+1)*(4k+1). For even n, the kings are arranged in a lattice with spacing 2.

A toroidal board has not only rotation and reflection symmetry, but also translation symmetry along its axes, a symmetry that is cyclic. Thus, its symmetry group is a semdirect product of D4 (rot/refl) and Z(n)*Z(n) (trans), much like the Euclidean group and the Poincaré group, and especially the crystallographic space groups. Complete with a rather complicated subgroup structure.

 

[lpetrich]

Though a toroidal board has greater symmetry than an ordinary one, and though one might expect that to make solutions easier, the n-nonattacking-queens problem on that kind of board is as intractable as for the plain kind of board (A007705 - OEIS). To within symmetries, A053994 - OEIS. I have calculated how many with each symmetry type, rotation groups C1, C2, and C4, and translation group T, though I have not tried to find the translation steps in each group. Here goes:
1 (degenerate)
5
C4 x T: 1
7
C2 x T: 1
11
C2 x T: 2
13
C2: 5
C4: 3
C2 x T: 2
C4 x T: 1
17:
C1: 40
C2: 30
C4: 23
C2 x T: 3
C4 x T: 1
19:
C1: 218
C2: 132
C2 x T: 4
I extracted the numbers for various amounts of symmetry and I gave them to the OEIS. No success in finding series.

 

[lpetrich]

The toroidal-queens case has a simple solution that appears in all the solutions that I have calculated: queens having position (k,m*k) mod n, for k = 0 to (n-1). To be a valid solution, m-1, m, and m+1 must both be nonzero mod n and relatively prime to n. This means that n cannot be a multiple of 2 or 3.

From reflections, if m is a solution, then n-m is also a solution, and also m', where m*m' = +-1 mod n.

The solutions have at least C2 rotational symmetry, and if m^2 = -1 mod n, C4 rotational symmetry.

For what I'd listed,
5: 2*
7: 2
11: 2, 3
13: 2, 3, 5*
17: 2, 3, 4*, 5
19: 2, 3, 4, 7
The starred solutions have C4 rotational symmetry.

 

[lpetrich]

A group-based search for solutions of the n-queens problem - ScienceDirect -- gives additional symmetries of a toroidal board: scaling and affine.

In general, those symmetries are x' = D.x + T mod n, where D is a matrix, T is a vector, x is the input vector, and x' is the output vector.

Translation: D = I
Rotation/Reflection: D = {{+-1,0},{0,+-1}} or {{0,+-1},{+-1,0}}
Scaling: D = a * D(rot/refl), where a is nonzero and relatively prime to n.
Affine: D is any matrix over 0...(n-1) with a nonzero determinant relatively prime to n, and possibly additional constraints.

The scaling group is the semidirect product of Zx(n) / {1,-1} and the rotation/reflection group, in turn the semidirect product of rotations/reflections and translations. Zx(n) is the multiplicative group of numbers 1 ... (n-1) relatively prime to n.

 

[lpetrich]

The matrices in the elements of this affine group are all invertible 2*2 matrices with elements in $Z_n$, the ring of integers modulo n. These matrices all have nonzero determinant values that are relatively prime to n. Thus belonging in the group $Z^\times_n$. The matrices themselves thus belong in $GL(2,Z_n)$. The number of elements of this group for each in is given in A000252 - OEIS.

This result is readily generalized to a r-dimensional board, a board with $n^r$ line segments / squares / cubes / hypercubes. Its full symmetry group is all combinations (D,T) of invertible r*r matrices D over $Z_n$, and r-vectors T over $Z_n$. For input r-vector x and output r-vector x',
$$ x' = D.x + T \mod n $$
A matrix D over integers modulo n is invertible iff its determinant is nonzero and relatively prime to n, all modulo n. Thus being in $Z^\times_n$, the multiplicative modulo-n group. Matrices D form a group, $GL(r,Z_n)$.

This matrix group contains a generalization of D4, the hypercube or cross-polytope symmetry group. It has elements (permutation matrix) . (diagonal matrix with +-1's in the diagonal) . It also has a scaled version, with the matrices multiplied by scalars in $Z^\times_n$.

Returning to $GL(r,Z_n)$, it is a subset of the ring $M(r,Z_n)$ of r*r matrices over $Z_n$. According to Combinatorics of Vector Spaces over Finite Fields, this ring factorizes into a product of rings over the prime factors of n. If $n = \prod_p p^m$ for primes p, then $M(r,Z_n) = \prod_p M(r,Z_{p^m})$, and thus, $GL(r,Z_n) = \prod_p GL(r,Z_{p^m})$. The order of the prime-power group is given by
$$ |GL(r,Z_{p^m})| = p^{r^2(m-1)} |GL(r,Z_p)| = p^{r^2(m-1)} \prod_{i=0}^{r-1} (p^r - p^i) = p^{r^2 m} \prod_{i=1}^{r} \left( 1 - \frac{1}{p^i} \right) $$
Thus,
$$ |GL(r,Z_n)| = n^{r^2} \prod_{p ,\ i=1}^{i=r} \left( 1 - \frac{1}{p^i} \right) $$

 

[lpetrich]

The group $GL(r,Z_n)$ is the automorphism group of the group $(Z_n)^r$. Not surprisingly, $GL(1,Z_n) ~ Z^\times_n$. One can define projective and special variants of this group, as one can do for other GL(n,X).

Getting back to the original problem, let us find how toroidal-queen solutions are related by affine transforms. They fall into three categories: regular, with full translation symmetry, semiregular, with partial translation symmetry, and irregular, with no translation symmetry. The regular ones have queen positions given by $x = x_0 + k (1,m) \mod n$ for k from 0 to (n-1) and m from 2 to (n-2). The starting point x₀ can be made (0,0), and the solution's translation symmetry is adding an arbitrary value to k. That symmetry has abstract group $Z_n$.

Let us apply an affine-transform matrix $\{\{a_{11} , a_{12}\},\{a_{21} , a_{22}\}\}$ to $k (1,m)$. It gives us $k (a_{11} + a_{12} m, a_{21} + a_{22} m)$. It is easy to show from this that all regular solutions are related. Take $a_{11} = a_{22} = 1$ and $a_{12} = 0$, and one gets $k (1, a_{21} + m)$.

The first irregular solutions appear for n = 13 and the first semiregular solutions for n = 25. Finding which ones are related by affine transforms will be a challenge.

 

[lpetrich]

Returning to $GL(r,,Z_{p^m})$ for some prime p, I conjecture that it contains $GL(r,Z_p)$. That is the case for r = 1, where $Z^\times_{p^m}$ is for odd primes $Z_{p^{m-1}(p-1)}$ and for p = 2, $Z_{2^{m-2}} \times Z_2$ (Multiplicative group of integers modulo n - Wikipedia).

For r > 1, this conjecture means that the only solvable groups of form $GL(r,Z_{p^m})$ have r = 2 and p = 2 or 3.

 

[lpetrich]

After some experimenting, I have composed a conjecture for the count of all regular nonattacking-queen solutions of a n*n toroidal board, RT(n). It is $RT(n) = \prod_p RT(p^m)$ where $n = \prod_p p^m$ for distinct prime factors p. In turn,
$$ RT(p^m) = \left\{ \begin{array}{ll} 0 & \text{for } p = 2, 3 \\ p^m (p-3) & \text{otherwise} \end{array} \right. $$
From translation symmetry, RT(n) is divisible by n, as is the total number of toroidal-queen solutions.

Regular solutions have the form $x = x_0 + k(1,m)$, where m is {2, 3} for 5, {2, 3, 4, 5} for 7, {2, 3, 12, 17, 18, 23, 32, 33} for 35, etc. I am unable to find any patterns in the regular solutions for composite sizes. Numbers that are relatively prime to composite numbers have a similar lack of patterns. For instance, {1, 2} for 3, {1, 3} for 4, {1, 2, 3, 4} for 5, {1, 5, 7, 11} for 12, and {1, 2, 4, 7, 8, 11, 13, 14} for 15. Taking products fails in both cases.

 

[lpetrich]

The toroidal n-queens problem has a problem that the ordinary n-queens problem does not. The full symmetry group of the toroidal case has elements that map some solutions onto non-solutions and vice versa, while for the ordinary case, every solution is mapped onto some solution, whether itself or another one.

So let us try to find the largest symmetry group whose elements will only map toroidal-queen solutions to themselves or to other ones. The toroidal-board symmetry group is GA(2,Z(n)), the general affine group with elements (R,D) that take vector x into vector y with
$$ y = R \cdot x + D $$
To see if a solution gets mapped onto a non-solution, we consider the positions of queens 1 and 2 and take their difference:
$$ (y_2 - y_1) = R \cdot (x_2 - x_1) $$
So we only have to consider the GL(2,Z(n)) part of GA(2,Z(n)). The above expression can be written in simplified form as $y = R \cdot x$.

 

[lpetrich]

For GL(2,field), one can compose every element from skew elements $\begin{pmatrix} 1 & 0 \\ a & 1 \end{pmatrix}$ and $\begin{pmatrix} 1 & a \\ 0 & 1 \end{pmatrix}$ and scaling element $\begin{pmatrix} a & 0 \\ 0 & b \end{pmatrix}$, where a and b are nonzero, but I don't know if that is possible for GL(2,ring).

Applying a skew to two queens on neighboring rows can bring them together to attack each other. So the symmetries do not include skews. I conjecture that the maximum symmetry that relates toroidal-queen solutions is the subgroup of GA(2,Z(n)) which has its matrices be the D4 matrices scaled by Zx(n) elements. Of that, the maximum symmetry of any solution is the C4 matrices (pure rotation) scaled by Zx(n) elements with the offsets being multiples of some base offset -- Z(n) instead of Z(n)^2.

 

[lpetrich]

Looking at the regular solutions again, k*(1,m) mod n for k = 0 to n-1, they all have twofold rotation symmetry, This is because they can be scaled by any factor that is relatively prime to n, and because the possible scale factors include -1 mod n, a 180-degree rotation.

Some of these solutions also have fourfold rotation symmetry, and that happens when m² = -1 mod n. This implies m⁴ = 1 mod n, meaning that m is an element with order 4 in Z^x(n). This is only possible if at least one prime factor of n has form 4k+1.

For n = 5, m = 2 is the only solution, and has fourfold symmetry. For n = 7, m = 2 and 3 and none of them have fourfold symmetry. For n = 11, m = 2, 3, 4, 5 with none fourfold.

For n = 13, m = 5 with fourfold symmetry and m = 2, 3, 4, 6 without. Irregular solutions first appear, and they have scaling-symmetry groups Z2 and Z4, with fourfold, and Z6, without fourfold.

For n = 17, m = 4 with fourfold symmetry and m = 2, 3, 5, 6, 7, 8 without. The irregular solutions have scaling-symmetry groups Z1, Z2, Z4, and Z8 with fourfold, and Z1, Z2, and Z8 without fourfold. Runtime: 2.3 seconds.

For n = 19, m = 2 to 9 with irregular-symmetry scaling groups Z1, Z2, Z6, and Z9. None have fourfold symmetry. Runtime: 48 seconds.

For n = 23, m = 2 to 11 with irregular-symmetry scaling groups Z1, Z2, and Z11. None have fourfold symmetry. Runtime: 53153 seconds = 14.7 hours.

Run on an iMac with a 2.3-GHz Intel Core i5.
Compiled with gcc from the most recent version of Apple Xcode: Apple LLVM version 10.0.1 (clang-1001.0.46.4)
Algorithm: search by rows with backtracking, occupied columns and diagonals cached. Some old benchmarking code modified for a toroidal board and with symmetry checking added.For n = 17, there are some solutions with fourfold symmetry and with scaling group Z1, the identity group. This is because that fourfold symmetry is associated with a scaling factor that is either 4 or 13. Both of them have squares -1 mod 17, and the square of a fourfold rotation also gives -1 mod 17 (it gives -1 mod n in general). The two together give 1 mod 17, the identity scaling.