B The eight-queens chess puzzle and variations of it

  • Thread starter lpetrich
  • Start date
919
148
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.
 
Last edited:
14,692
4,400
Is there a question in there somewhere?
 
919
148
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.
 
242
37
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.
gre00.jpg
 

Attachments

919
148
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.
 
919
148
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.
 
Last edited:
919
148
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.
This problem is essentially a permutation problem, because arrangements of nonattacking rooks are equivalent to permutations.
 
919
148
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.
 
919
148
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.
 
919
148
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.
 
919
148
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.
 
919
148
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.
 
919
148
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.
 
919
148
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.
 
919
148
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) $$
 
919
148
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 x0 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.
 
919
148
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.
 

Want to reply to this thread?

"The eight-queens chess puzzle and variations of it" You must log in or register to reply here.

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving

Top Threads

Top