• Welcome to the new Internet Infidels Discussion Board, formerly Talk Freethought.

The n-queens problem

lpetrich

lpetrich

Contributor
Joined
Jul 27, 2000
Messages
25,327
Location
Eugene, OR
Gender
Male
Basic Beliefs
Atheist
For a n*n chessboard, find how many ways one can place n chess queens on them so that none of them attack each other.

I once saw that problem used as a benchmark, and I've written versions of it in a variety of programming languages. The algorithm that I used is depth-first. It stars with looping over placing a queen on each square of it, and for each placement , it does that for the next rank toward the other end. It checks the second queen for legitimate placement, then continues to the third rank and the third queen. The queen placement stops when one has reached the other end of the board. I then do statistics on the resulting position.

On my computer, a 2.3-GHz Intel Core i5 iMac, I've found that my C++ version takes about a minute and a half, finding 14772512 valid solutions.

Here is up to 27 queens: 1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 73712, 365596, 2279184, 14772512, 95815104, 666090624, 4968057848, 39029188884, 314666222712, 2691008701644, 24233937684440, 227514171973736, 2207893435808352, 22317699616364044, 234907967154122528

A 1*1 board has one queen as a valid solution, and I will ignore that case in my discussion of solutions' symmetries.

Some solutions have symmetries, and the possible ones are twofold and fourfold. Twofold symmetry is symmetry under rotating by 180d, and fourfold symmetry is symmetry under rotating by 90d, 180d, or 270d. No solutions have reflection symmetry, as can easily be shown.

Some solutions have twofold symmetry, looking the same under rotation by 180d and some fourfold symmetry, but it's easy to prove that no solution can have reflection symmetry. For some queen, the corresponding reflected queen is offset from the original by a rank, a file, or a diagonal, and the two queens are thus mutually attacking.

Each fourfold solution has a related solution, a mirror-image one. Each twofold solution has three related ones, rotation by 90d, reflection in an axial (rank, file) direction, and reflection in a diagonal direction. Each no-symmetry solution has seven related ones, rotation by 90d, 180d, 270d, and reflection along each axis and each diagonal.

No symmetry, distinct: 0, 0, 0, 0, 1, 0, 4, 11, 42, 89, 329, 1765, 9197, 45647, 284743, 1846189, 11975869, 83259065, 621001708, 4878630533, 39333230881, 336375931369, 3029241762900, 28439270037332, 275986675209470, 2789712437580722, 29363495854214938

Twofold symmetry, distinct: 0, 0, 0, 0, 0, 1, 2, 1, 4, 3, 12, 18, 32, 105, 310, 734, 2006, 4526, 11046, 36035, 93740, 312673, 895310, 2917938, 8532332, 28929567, 80100756, 312717136, 900007828, 3647359506, 10816583674, 45313494882

Fourfold symmetry: distinct: 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 4, 4, 0, 0, 32, 64, 0, 0, 240, 352, 0, 0, 1664, 1632, 0, 0, 16448, 21888, 0, 0, 203392, 333952, 0, 0, 2922752, 4325376, 0, 0, 38592000, 50746368, 0, 0, 630794240, 897616896, 0, 0, 10758713344, 17514086400, 0, 0, 203437559808, 326022221824, 0, 0, 4306790547456, 6265275064320, 0, 0, 97204813266944, 145913049251840, 0, 0

For fourfold symmetry, there are solutions for sizes 4k and 4k+1, but not for sizes 4k+2 or 4k+3.

For twofold and fourfold symmetry and odd size, then one queen is in the center.

Four twofold symmetry, the rotations relate two queens, except for a queen in the center. Likewise, for fourfold symmetry, the rotations related four queens, except for a queen in the center. That accounts for what sizes are possible.
 
Let us consider a toroidal board, a board with periodic boundary conditions, a board where each edge wraps around to the opposite edge.

All the toroidal solutions: 1, 0, 0, 0, 10, 0, 28, 0, 0, 0, 88, 0, 4524, 0, 0, 0, 140692, 0, 820496, 0, 0, 0, 128850048, 0, 1957725000, 0, 0, 0, 605917055356, 0, 13404947681712, 0, 0, 0

All the distinct ones, to within symmetries: 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 2, 0, 11, 0, 0, 0, 97, 0, 354, 0, 0, 0, 31381, 0, 395551, 0, 0, 0, 90120677, 0

Notice that there are solutions only for sizes 6k+1 and 6k+5.

Some of the toroidal solutions are "regular", with queen coordinates with form (k, a*k mod n) for k = 0 to (n-1), and some integer a. All of {a,a-1,a+1} must be nonzero mod n and relatively prime to n.

Solutions a and b are related by reflections if b = n - a and a*b = +-1 mod n. All solutions have twofold rotational symmetry, with a^2 = -1 mod n indicating fourfold symmetry.

Other pages on the n queens problem, and some comments and  Eight queens puzzle
 
Let's handle board symmetries more explicitly. There are two infinite families of point groups, groups of rotation and reflection around a point. These are cyclic (pure rotation) and dihedral (rotation and reflection). Cyclic n-fold: C(n) with n elements, dihedral n-fold: D(n) with 2n elements, C(n) with n reflections. The rotation elements I will call R(angle) and the reflection elements S(direction) (German "Spiegel": "mirror").
  • 8: D4 - R(0) R(90d) R(180d) R(270d) S(a1) S(a2) S(d1) S(d2) - C4 D2a D2d
  • 4: C4 - R(0) R(90d) R(180d) R(270d) - C2
  • 4: D2a - R(0) R(180d) S(a1) S(a2) - C2 D1a1 D1a2
  • 4: D2d - R(0) R(180d) S(d1) S(d2) - C2 D1d1 D1d2
  • 2: C2 - R(0) R(180d) - C1
  • 2: D1a1 - R(0) S(a1) - C1
  • 2: D1a2 - R(0) S(a2) - C1
  • 2: D1d1 - R(0) S(d1) - C1
  • 2: D1d2 - R(0) S(d2) - C1
  • 1: C1 - R(0)
a = axial directions: horizontal, vertical
d = diagonal directions
R(0) = identity element
C1 = identity group

The n-queens problem has symmetries C1, C2, C4 for its solutions.
 
The symmetries for the toroidal case are more complicated. The transforms have a homogeneous part, R, and a translation or shift, D. R includes rotations, reflections, scaling, and skews. R is a 2*2 matrix and D a 2-vector, with elements 0 to n-1 mod n.

Position x becomes position x' -- x' = R.x + D

Mappings (homomorphisms):
(R,D) -> R -> det(R) (determinant)

Kernels: (I,D), R with det(R) = 1

Determinant values are nonzero and relatively prime to n. They form a group:  Multiplicative group of integers modulo n

One can get constraints on the D's by moving the board to place one queen at (0,0). This means that all the nonzero D's map the (0,0) queen onto other queens, though not necessarily all of the other queens.

From the axial constraints, for D = (d1,d2), all the distinct D's have different d1's, and also different d2's, and from the diagonal constraints, we get further constraints.
 
I'll look at other chess pieces.

The king is an easy one. The maximum number of non-attacking ones is ceiling(n/2)^2. The kings are on a square grid with neighboring ones separated by 2 squares.

For rooks, the maximum number present is n and the number of possible solutions is n! - the number of permutations of n symbols.

There are no solutions with axial reflections - horizontal and vertical ones - because such reflections place rooks on the same row or column (rank or file). But there are solutions with diagonal reflections.

For at least twofold symmetry, C2, if n = 2m or 2m+1, then the number of solutions is 2^m*m!

For at least fourfold symmetry, C4, if n = 4m or 4m+1, then the number of solutions is (2m)!/m!
But if n = 4m+2 or 4m+3, then there are no solutions, by the argument I'd mentioned for queens

For a a diagonal reflection in either direction, D1d, then the number of solutions is
sum over k from 0 to floor(n/2) of n!/((n-2k)!*2^k*k!)

If there are both diagonal reflections, D2d, then for n = 2m or 2m+1,
sum over k from 0 to floor(m/2) of (2^m*m!)/((m-2k)!*4^k*k!)
 
What the rotations and reflections look like as matrices:
  • R(0) = {{1,0},{0,1}}
  • R(90) = {{0,-1},{1,0}}
  • R(180) = {{-1,0},{0,-1}}
  • R(270) = {{0,1},{-1,0}}
  • S(a1) = {{-1,0},{0,1}}
  • S(a2) = {{1,0},{0,-1}}
  • S(d1) = {{0,1},{1,0}}
  • S(d2) = {{0,-1},{-1,0}}
Scaling looks like this: {{s1,0},{0,s2}}
Skews look like these: {{1,s},{0,1}} (horizontal), {{1,0},{s,1}} (vertical)


Now to bishops. There is one on one end of each long diagonal, and two on one set of opposite vertices of each diagonal rectangle with the vertices at the edges of the board. There are this 2n-2 bishops and 2^n solutions.

There are 2^(ceiling(n/2)+1) solutions with one axial-reflection symmetry, and no solutions with any other symmetries.

Since bishops move only on one color, let us consider the colors separately. For even-sized boards, each color has one long diagonal, and the two colors' squares are mirror images. But for odd-sized boards, one color has both long diagonals and the other color has neither of them.

For size 2m, both colors have 2^m solutions, with no symmetries, except for m=1 (one bishop on either square)

For size 2m+1, the squares with long diagonals have 2^(m+1) solutions, and the squares without LD's have 2^m solutions.

Turning to symmetries, the squares with LD's have 2^(floor(m/2)+2) with one axial-reflection symmetry: D1a

The squares without LD's have more kinds of symmetry. All the solutions have twofold symmetry, C2. Of these, 2^(floor(m/2)) have both axial reflections, D2a, and if m is even, then 2^(m/2) have fourfold symmetry, C4.
 
For a toroidal board, one can only place n bishops, and for an n even, the number of solutions is 2^n*((n/2)!)^2, and for n odd, n!.

For n even, the boundary conditions continue the color pattern, so each color has its own solutions. Number (n = 2*m): 2^m * m!

For n odd, the boundary conditions map each color onto the other color, making effectively one color for all squares.

In the even case and bishops on only one color, no solution has any symmetries except for the 2*2 board, with only 1 bishop.

In the even case and bishops on both colors (n = 2*m), there are 2^(m+1) * m! solutions with one axial-reflection symmetry, the only symmetric ones.

In the odd case (n = 2*m+1), we get the same numbers as for rooks, but with the rooks' diagonal-symmetry counts becoming the bishops' axial-symmetry counts.
 
For knights, the maximum number of nonattacking ones is A030978 - OEIS

The formula: n^2/2 for even n, (n^2+1)/2 for odd n
n = 1: 1
n = 2: 4

I can't find the comparable number for a toroidal board.

But a solution for an ordinary board is to place the knights on every square with one of the two colors. For odd n, one chooses that color that includes the two long diagonals.

This means that for a toroidal board, this solution is valid for even n, but not for odd n.

There is a big variety of alternative chess pieces that have been invented:  Fairy chess piece -  Fairy chess -  List of chess variants
 
Returning to general toroidal transforms, x' = R.x + D (R = rotation, reflection, scaling, skew, D = offset), I consider the structure of the group of R's. It is GL(2,Z(n)) - all 2*2 invertible matrices of integers modulo n.

GL = "general linear". In general, this group is GL(n,X) n*n matrices over some commutative ring X, though for 1*1 it can be a group.

Consider group R(X), all elements of X with reciprocals. For Z(n), integers modulo n, it is Zx(n), the multiplicative group of integers modulo n, containing all positive integers relatively prime to n. The order (number of elements) of that group is the Euler phi function of n.

GL(n,X) has subgroup SL(n,X) - "special linear" - with determinant 1. Their quotient group is R(X)

GL(n,X) has subgroup x*I for all x in R(X). Their quotient group is PGL(n,X) - "projective general linear"

SL(n,X) has subgroup x*I for all x such that x^n = 1. Their quotient group is PSL(n,X) - "projective special linear"

The group D(4) has elements {{+-1, 0}, {0, +-1}} and {{0, +-1}, {+-1, 0}}
It can be generalized to arbitrary rings with 0 = additive identity, 1 = multiplicative identity, -1 = additive inverse of 1. It can readily be shown that (-1)^2 = 1 in this general case as well as with numbers.

One can generalize D4 by generalizing 1,-1 to members of R(X): {{a, 0}, {0, b}} and {{0, a}, {b, 0}} -- rotations, reflections, and scaling, but no skews.
 
KnightsMax_700.gif

Love these posers.
Thanks for the maths Chess thread Ipetrich.
 
Yes, that's it - a solution with the maximum number of nonattacking knights.

I note for kings on a toroidal board, that the even-n solution carries over from the plain-board case, while the odd-n solution doesn't. Like for the knights.


Solutions can be divided into two main types, which I call regular and irregular. To within an overall shift, the regular solutions have form (k,m*k) mod n, for constant m and k over the entire range of 0 to n-1. These quantities must be nonzero and relatively prime to n for these pieces:
  • Rook, queen: m
  • Bishop, queen, m-1, m+1
All mod n, of course.

An allowable toroidal-bishop solution is all the bishops in a straight line either horizontally or vertically, collectively axially.
 
Let us see which symmetries a regular toroidal solution can have. With x = k*X and x' = k'*X, we have
k*(R.X) + D = k'*X

Letting k' = u*k + v, I find
R.X = u*X
D = v*X

u must be relatively prime to the board size n, while v can have any value in Z(n).

Continuing further, if R is pure scaled, then it has the same scale for both coordinates: a*I. If R is scaled and flipped - {{0,b},{a,0}} - u = a*m, b = a*m^2.

For rooks and bishops, irregular solutions first appear at board size 4, while for queens, they first appear at board size 13.
 
Considering counts of regular solutions in the non-attacking pieces problem, I find:

Rooks: Euler totient function phi(n) - number of positive integers relatively prime to positive integer n. A000010 - OEIS

\( n = \prod_p p^m ;\ \phi(n) = \prod_p p^{m-1} (p-1) \)

Bishops: modification of that formula. A002472 - OEIS
The (p-1) is replaced by 1 for p = 2, (p-2) for p > 2

Queens: modification of that formula. A123565 - OEIS
The (p-1) is replaced by 0 for p = 2, (p-3) for p > 2

No regular queen solutions for n divisible by 2 and/or 3.

Here is an ASCII-art diagram that shows which pieces have which regular solutions for each board size.
Code: 
  1  q
  2  b r
  3  b r r
  4  b r b r
  5  b r q q r
  6  b r . . . r
  7  b r q q q q r
  8  b r b r b r b r
  9  b r r b r r b r r
 10  b r b r . . . r b r
 11  b r q q q q q q q q r
 12  b r . . . r b r . . . r
 13  b r q q q q q q q q q q r
 14  b r b r b r . . . r b r b r
 15  b r r b r . . r r . . r b r r
 16  b r b r b r b r b r b r b r b r
 17  b r q q q q q q q q q q q q q q r
 18  b r . . . r b r . . . r b r . . . r
 19  b r q q q q q q q q q q q q q q q q r
 20  b r b r . . . r b r b r b r . . . r b r
 
 Fairy chess pieces

Here is a way of summarizing pieces' possible moves.

Each piece's possible moves is (number of steps) (possible moves per step). Each possible move per step I will summarize by its coordinate change. This summary in turn works for all combinations of coordinates and all directions. Thus the orthodox knight step I denote as (2,1). It is short for (+-2, +-1) and (+-1, +-2). where +- denotes going over both signs.

How many steps a piece can make before it runs into another piece I give as s (single) and m (multiple).

The orthodox pieces' moves:
  • King: s (1,0) (1,1)
  • Queen: m (1,0) (1,1)
  • Rook: m (1,0)
  • Bishop: m (1,1)
  • Knight: s (2,1)
The pawn is more complicated. From initial square, can move (0,2) forward, can be blocked. From any square, can move (0,1) forward, can capture (1,1) forward. En passant: if a pawn has moved past it, it can capture that pawn at its halfway spot on the next move.


I'll take a look at the nightrider. It is a fairy chess piece that is a multistep version of the knight: m (2,1)

I'll use a toroidal board, since that makes the analysis easier - no edge effects. For small boards, the nightrider moves like some other pieces.

2*2 board: the NR is effectively (1,0) - a rook
3*3 board: the NR is effectively (1,1) - a bishop
4*4 and higher sizes of board - no reductions


There are a variety of chesslike games that have been played over the centuries, like Indian  Chaturanga,  Indian chess, Chinese  Xiangqi, Korean  Janggi, and Japanese  Shogi and they often have pieces that move different than Western ones.
 
There are a variety of chesslike games that have been played over the centuries, like Indian  Chaturanga,  Indian chess, Chinese  Xiangqi, Korean  Janggi, and Japanese  Shogi

I've found out how many R matrices there are. I did that by calculating the first 20 sizes with Mathematica, then going to oeis.org and finding a sequence that fits.

\( \bullet n = \prod_p p^m \text{ - prime factorization} \\ \bullet N(R) = \prod_p (p-1) p^{m-1} = \phi(n) = |Z^\times (n)| = |GL(1,Z_n)| \\ \bullet N(B) = \prod_p (p = 2: 1,\ p > 2: p-2) p^{m-1} \\ \bullet N(Q) = \prod_p (p = 2: 0,\ p > 2: p-3) p^{m-1} \\ \bullet |GL(2,Z_n)| = \prod_p (p-1)(p^2-1) p^{4m-3} = \phi(n) |SL(2,Z_n)| \\ \bullet |SL(2,Z_n)| = \prod_p (p^2-1) p^{3m-2} = |PGL(2,Z_n)| \\ \bullet |PSL(2,Z_n)| = \prod_p (p = 2: 1 ,\ p > 2: 1/2) (p^2-1) p^{3m-2} \)
 
This result suggests extensions to 3*3 matrices and larger.

In fact, OEIS has sizes for:
\( n = \prod_p p^m \\ |GL(k,Z_n)| = \prod_p |GL(k,Z_{p^k})| \\ |GL(k,Z_{p^k})| = \prod_{j=1}^k (p^j-1) p^{k^2 m - k(k+1)/2} \\ |SL(k,Z_n)| = |PGL(k,Z_n)| = |GL(k,Z_n)|/\phi(n) \\ |SL(k,Z_{p^m})| = |PGL(k,Z_{p^m})| = |GL(k,Z_{p^m})|/\phi(p^m) = \prod_{j=2}^k (p^j-1) p^{(k^2-1) m - k(k+1)/2+1} \)
To find |PSL(k,Z(n))|, one must find divide the order of |PGL(k,Z(n))| and |SL(k,Z(n))| by the number of elements with power k = 1 of Zx(n). But that number is multiplicative over powers of prime factors of n, like the other counts here.
 
Let's look at how the group Zx(n) decomposes by prime factors of n.

\( Z^\times(n) = \prod_p Z^\times(p^m) \\ Z^\times(2^m) = Z_2 \times Z(2^{m-2}) \ (m = 1: \text{ identity group}) \\ Z^\times(p^m) = Z_{p-1} \times Z(p^{m-1}) \ (p > 2) \)

The number of elements x of Z(n) where k of x = e is gcd(k,n)

So |SL(k,p^m)|/|PSL(k,p^m}| = gcd(k,2)*gcd(k,2^(m-2)) for p = 2, gcd(k,p-1)*gcd(k,p^(m-1)) for p > 2

|SL(k,n)|/|PSL(k,n)| = product of these


For k = 2 (chessboard case), this ratio is 2 to power (number of distinct prime factors greater than 2).

With general transforms x' = R.x + D, one finds that all regular solutions are equivalent, that there is always some (R,D) that turns one regular solution into another. That is also the case if one specializes to regular solutions with one piece at (0,0) and all D's equal to (0,0).

The number of R's that map a regular solution onto itself is |GL(2,n)|/N(regular) and that gets very large very quickly. |GL(2,n)| ~ n^4, and N(regular) ~ n.

Irregular solutions are another story, and they are harder to analyze.
 
For bishops, rooks, and nightriders, I find that the first irregular solutions appear at size 4. A nightrider does knight moves, but it can move repeatedly in some direction.

Rooks:
Code: 
R .
. R

R . .
. R .
. . R

R . . .
. R . .
. . R .
. . . R

(irregular)
R . . .
. R . .
. . . R
. . R .
Bishops:
Code: 
B .
B .

B . .
B . .
B . .

B . . .
B . . .
B . . .
B . . .

(irregular)
B . . .
B . B .
B . . .
. . . .

B . B .
B . B .
. . . .
. . . .
Nightriders:
Code: 
N .
. N

N . .
N . .
N . .

N . . .
. N . .
. . N .
. . . N

(irregular)
N N . .
N N . .
. . . .
. . . .
 
For toroidal-symmetry matrices for regular solutions, I've found solutions.

The symmetry operation on position vector x is x' = R.x + D where R is a matrix and D is a vector an all operations are modulo n, the board size.

Regular solutions x = x0 + k*X where X = {1,m}. Symmetry operations that preserve that solution are:
R = {{u - m*x, x}, {m*u - m*t/u - m^2*x, t/u + m*x}}
where
R.X = u*X
det(R) = t
with x in Z(n) and t and u in Zx(n)

\( R = \begin{pmatrix} u - m x & x \\ m u - m t/u - m^2 x & t/u + m x \end{pmatrix} ,\ X = \begin{pmatrix} 1 \\ m \end{pmatrix} ,\ R \cdot X = u X ,\ \det R = t \)

For relating each regular solution to itself, the R's form a group with order n*(phi(n))^2 ~ O(n^3)


Symmetry operations that turn solution X ={1,m} into solution X' = {1,m'} are
R = {{u - m*x, x}, {m'*u - m*t/u - m*m'*x, t/u + m'*x}} for all x in Z(n)
where
R.X = u*X'
det(R) = t

\( R = \begin{pmatrix} u - m x & x \\ m' u - m t/u - m m' x & t/u + m' x \end{pmatrix} ,\ X = \begin{pmatrix} 1 \\ m \end{pmatrix} ,\ X' = \begin{pmatrix} 1 \\ m' \end{pmatrix} ,\ R \cdot X = u X' ,\ \det R = t \)

Flipping X' and getting {m',1} gives solution
R = {{m'*u + m*t/u - m*m'*x, -t/u + m'*x}, {-m*x + u, x}}

\( R = \begin{pmatrix} m' u + m t / u - m m' x & - t/u + m' x \\ u - m x & x \end{pmatrix} ,\ X = \begin{pmatrix} 1 \\ m \end{pmatrix} ,\ X' = \begin{pmatrix} m' \\ 1 \end{pmatrix} ,\ R \cdot X = u X' ,\ \det R = t \)

So they form a larger group, with order O(n^3) to O(n^4)
he order of all possible R's is O(n^4)
 
In summary, for toroidal-board queens and similar pieces, all the regular solutions are related by toroidal-board symmetries.

For irregular solutions, it is more difficult.

Being irregular means that at least some of the pieces are at non-collinear locations. To find a (R,D) solution, one needs three pieces mapped onto three pieces, whether the same ones or other ones or some mixture.

For (x1,x2,x3) to (x4,x5,x6), the denominators are (x2-x1).eps.(x3-x1) and for det(R), the numerator is (x5-x4).eps.(x6-x4), with similar numerators for the members of R and D. eps = {{0,1},{-1,0}} is the antisymmetric symbol.

Non-collinearity means (x2-x1).eps.(x3-x1) = 0 mod n. But modular arithmetic produces problems for division if n is composite. Let us consider the simplest case, n = 4, and let us consider dividing by 2, the only nontrivial divisor of 4. Division is defined as the solution of an equation. If x = a/b, then that means that b*x = a. So let us see what equation solutions we have.

2*{0, 2} = 0
2*{none} = 1
2*{1, 3} = 2
2*{none} = 3

A further problem is that to look through all the points requires calculating O(n^3) (R,D) sets and then checking them.

But to go through every possible value of R will take O(n^4) and every possible value of (R,D) O(n^6). Though if one finds D by taking R.x1 + D = x2 by fixing x1 and going through all the positions for x2, one can reduce that to O(n^5).
 
You must log in or register to reply here.
Back
Top Bottom