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

The n-queens problem

I'll return to regular solutions {k,m0+m*k} and calculate the effects of various symmetries.

  • rot 0d - {{1,0},{0,1}} - {0,0}
  • rot 90d - {{0,-1},{1,0}} - {n-1,0}
  • rot 180d - {{-1,0},{-1,0}} - {n-1,n-1}
  • rot 270d - {{0,1},{-1,0}} - {0,n-1}
  • rfl ax1 - {{-1,0},{0,1}} - {n-1,0}
  • rfl ax2 - {{1,0},{0,-1}} - {0,n-1}
  • rfl dg1 - {{0,1},{1,0}} - {0,0}
  • rfl dg2 - {{0,-1},{-1,0}} - {n-1,n-1}

A line along an axis: {k,m0} and {m0,k}
  • rot 0d - (1,2) k -> k, m0 -> m0
  • rot 90d - (1->2) k -> k, m0 -> n-1-m0 ; (2->1) k -> n-1-k, m0 -> m0
  • rot 180d - (1,2) k -> n-1-k, m0 -> n-1-m0
  • rot 270d - (1->2) k -> n-1-k, m0 -> m0 ; (2->1) k -> k, m0 -> n-1-m0
  • rfl ax1 - (1) k -> n-1-k, m0 -> m0 ; (2) m0 -> n-1-m0, k->k
  • rfl ax2 - (1) k -> k, m0 -> n-1-m0 ; (2) m0 -> m0, k ->n-1-k
  • rfl dg1 - (1->2, 2->1) k -> k, m0 -> m0
  • rfl dg2 - (1->2, 2->1) k -> n-1-k, m0 -> n-1-m0
In most cases, its only symmetry is being flipped along the axis that it parallels. Flipping along the other axis will move it to the opposite side of the board. But if m0 = (n-1)/2, meaning that n is odd and the pieces go through the center, then it can be flipped long both axes, and thus rotated 180d.

So in that case:
  • No flip - rot 0d, rot 180d, rfl ax1, rfl ax2
  • Flip - rot 90d, rot 270d, rfl dg1, rfl dg2
 
I now turn to all the other cases of regular solutions, {k,m0+m*k} where m is nonzero
  • rot 0d - k -> k, m0 -> m0, m -> m
  • rot 90d - k -> (n-1-m0) - m*k, m0 -> (n-1-m0)/m, m -> -1/m
  • rot 180d - k -> n-1-k, m0 -> (n-1)*(1-m) - m0, m -> m
  • rot 270d - k -> m0 + m*k, m0 -> (n-1)+m0/m, m -> -1/m
  • rfl ax1 - k-> (n-1) - k, m0 -> (n-1)*m + m0, m -> -m
  • rfl ax2 - k -> k, m0 -> n-1-m0, m -> -m
  • rfl dg1 - k -> m0 + m*k, m0 -> -m0/m, m -> 1/m
  • rfl dg2 - k -> (n-1-m0) - m*k, m0 -> (n-1)*(1-1/m) + m0/m, m -> 1/m
For rotation by 90d and 270d, one has to be more careful in handling cases where m evenly divides n, much like how one handles axis-line cases {k,m0} and {m0,k}.

For 180d rotation, m0 = (n-1)*(1-m)/2
For n odd, any m, for n even, m odd
If n is odd, there is a piece at the center of the board

For 90d and 270d rotation, m^2 = -1 (mod n, of course)
m0 = (n-1)/(m+1) = (n-1)*m/(m-1)
n = 4t+1 only

For axial reflections with m nonzero, m = n/2, meaning that n must be even. No first-axis reflections, but for second-axis reflections, m0 = (n-1)/2. That is not possible for even n, so there are no second-axis reflections either.
So the only solutions with axial-reflection symmetry are those where all the pieces are on a line along an axis.

For diagonal reflections, m^2 = 1. The solution m = n-1 will always exist, and in most cases, additional solutions will also exist. One can look at the group Zx(n) to find out how many will exist. It's 2^r where r is summed up over each distinct prime factor, r for 2 is 0, for 4 is 1, for 8 and higher powers of 2 is 2, and for a power of an odd prime is 1.

For the first diagonal, m0 = m*n/(m+1), and for the second diagonal, (m-1)/m*(m0 - (n-1)) = 0
 
I've found a general solution for the symmetries of regular solutions on a toroidal square board.

The regular solutions themselves are x = x0 + m*k where k is in Z(n) and m = (m1,m2) where m1 and m2 are relatively prime.

To go from regular solution m to regular solution mx requires a transform matrix T with property T.m = u*mx where u is in Zx(n), all of nonzero Z(n) relatively prime to n.

Let dyad(x,y) be the outer product of vectors x, y: {{x1*y1,x1*y2},{x2*y1,x2*y2}}

Also define a vector c(m) = {c(m)1,c(m)2} that is a sort of conjugate of m: m and mn are linearly independent: both m1*c(m)2 - m2*c(m)1 and m1*c(m)1 + m2*c(m)2 are in Zx(n) mod n.

Also a sort of flip matrix: e = {{0,1},{-1,0}}.

Then the matrix T = u * dyad(mx,c(m)) + v * dyad(e.c(mx),e.m) + w * dyad(mx,e.m)

T.m = (c(m).m) * mx

The determinant det(T) = (c(m).m) * (c(mx).mx) * u * v

So u and v are in Zx(n) and w is in Z(n)

So I've solved the symmetries of the regular solutions on a toroidal board. The irregular solutions are more difficult, and for high n, there are typically many more irregular solutions than regular ones.
 
Product: T(mx,mw,u1,v1,w1).T(mw,m,u2,v2,w2) = T(mx,m,u12,v12,w12)
where u12 = u1*u2, v12 = v1*v2, w12 = v2*w1 + u1*w2
with m.c(m) = 1 for each m.

With this product operation, the (u,v,w) sets form a group.
Identity: (1,1,0)
Inverse: (1/u, 1/v, -w/(u*v))

I tried looking for patterns in the transform matrices for the irregular solutions, but I was not very successful.


I'll now consider one-step versions of rooks and bishops. The one-step version of the queen is the king.

For kings, the largest number on the board is ceiling(n/2)^2, arranged in a square grid, each one 2 squares from its neighbors. For toroidal ones, it's floor(n/2)^2, since the odd case is the next-smaller even case with buffer strips around it.

For one-square rooks, it is all squares of one color, with the odd toroidal case being like for kings.

For one-square bishops, it is strips along one axis (rows or columns), two squares apart, with the odd toroidal case being like for kings.
 
I've found some published papers on the n-queens problem

A survey of known results and research areas for n-queens - ScienceDirect
Jordan Bell, Brett Stevens
Discrete Mathematics, Volume 309, Issue 1, 6 January 2009, Pages 1-31

The n-Queens Problem: The American Mathematical Monthly: Vol 101, No 7
with reprint
rivin_1994.pdf
Igor Rivin, Ilan Vardi, Paul Zimmermann
The American Mathematical Monthly, Volume 101, 1994 - Issue 7

The RVP paper notes that one can compose a toroidal-queens solution for a (m*n) * (m*n) board by taking a m*m solution and a n*n solution, and placing the m*m solution at each queen of the n*n solution, and a blank m*m board elsewhere. One may be able to use different m*m solutions for different queens.

That composition works for rooks, but for toroidal bishops, one is restricted in what solution one can have at each bishop position.

The RVP paper gives several solutions for the plain n-queens problem, showing that solutions exist for every board size at least 4.
 
The RVP and BS papers repeat a proof by G. Pólya for which board sizes can have toroidal-queens olutions. The BS paper calls a toroidal board a modular board, after modular (modulo) arithmetic.

Each queen solution is also a rook solution, with with each row index having a different column index, thus being a permutation of column indices.

For a n*n board, the rows and columns vary from 0 to n-1, and row index i has column index c(i).

The sum over i of the c(i)'s is S1 = n(n-1)/2.

Since the queens are on different diagonals, both {c(i)+i over i} and {c(i)-i over i} are also permutations.

Summing over i, means that S1+ S1 = S1 and 0 = S1 both mod n.

If n = 2k, then the sum is k*(2k-1), and it is nonzero mod n.
If n = 2k+1, then the sum is k*(2k+1), and it is zero mod n.

So n must be odd.

Now do this with the sum of the squares of c(i)+i and c(i)-i. The sum of c(i)^2 over i is S2 = n(n-1)(2n-1)/6.

We also have S3 = sum of 2*i*c(i) over i.

For (c(i)+i)^2 and (c(i)-i)^2 we get
S2 + S3 + S2 = S2 and S2 - S3 + S2 = S2

So S3 = S2 and 2*S2 = 0 mod n.

Considering n(n-1)(2n-1)/3 with n = 6k+1, 6k+3, 6k+5, since n must be odd, I find
2k*(6k+1)*(12k-1) - divisible
2*(2k+1)*(3k+1)*(12k+5) - not divisible
2k*(6k+5)*(12k+9) - divisible

Thus, n = 6k+1 or 6k+5, meaning that n must be relatively prime to 6.

-

This is easy to prove in the regular case. Step (1,m) has m, m+1, and m-1 relatively prime to n.

if m is even, then m+-1 must be odd. Likewise, if m is odd, then m+-1 must be even. Thus, n cannot be even.

Consider m = 3k, 3k+1, 3k+2. Then m, m+1, m-1 become
3k, 3k+1, 3k-1
3k+1, 3k+2, 3k
3k+2, 3(k+1), 3k+1
All divisible by 3, thus n cannot be divisible by 3.

Thus, n must be relatively prime to 6.

If m = 2, a solution will always exist, since m, m+1, m-1 = 2, 3, 1. Likewise for m = 3, m = n-2, and m = n-3, though for n = 5, these solutions are not all distinct.
 
From the BS paper, the Discrete Mathematics paper (BSDM?), is a result on how many nonattacking queens can fit onto a toroidal n*n board, a result by a certain P. Monsky.
  • There always exists a solution with (n-2) queens.
  • If n is not divisible by 3 or 4, there exists a solution with (n-1) queens.
  • If n is not divisible by 2 or 3, there exists a solution with n queens, the maximum number.
I'll now give the solutions of rooks and bishops.

Rooks have locations (i,c(i)) for rows i and columns c(i). The c(i) form a permutation. There are n! solutions.

Plain bishops are on the edges of the board. There is a bishop on one end of each long diagonal, and the other bishops are on opposite corners of rectangles formed by the other diagonals. For a n*n board, there are 2*(n-1) bishops.

Toroidal bishops are another story. There are n of them, and their distribution depends on whether n is odd or even.

For n odd, the bishops have locations (i+c(i),i-c(i)) mod n, where the i's and c's go over 0 to n-1 and the c's are a permutation.

For n even, each color of square has a separate distribution.

For the even squares, the bishops have locations (i+c(i)+(n/2)*b(i),i-c(i)-(n/2)*b(i)) mod n, where the i's and c's go over 0 to n/2 -1, the c's are a permutation, and the b's are individually 0 or 1.

For the odd squares, the bishops have (even-square bishop locations) + (1,0) mod n

Thus, for n odd, there are n! solutions and for n even, (2^(n/2)*(n/2)!)^2 solutions.

-

Regular solutions are easy for rooks: step (1,m) where m is relatively prime for n.

Regular solutions for toroidal bishops have that even-odd split.

For odd n, their step is (1+m,1-m) mod n where m is relatively prime to n.

For even n and one color, their step is (1+m+(n/2)*b,1-m-(n/2)*b) mod n, where m is relatively prime to (n/2) and b is 0 or 1

For even n and both colors, their step is (1+m+n*b,1-m-n*b)/2 mod n, where m is relatively prime to n and b is 0 or 1.
 
I'll find the symmetries of the regular solutions.

Rooks first. Their positions can be expressed as x(k) = (k,m*k+s)

Diagonal reflection 1: m^2 = 1, (m+1)*s = 0
m = 1, 2*s = 0
m = -1, all s

Diagonal reflection 2: m^2 = 1, (m-1)*(s+1) = 0
m = 1, all s
m = -1, 2*(s+1) = 0

180d rotation: m = 2*s + 1

90d rotation: m^2 + 1 = 0, 2*s^2 + 2*s + 1 = 0

For 90d rotations, n = 4k or n = 4k+1. In the latter case, there is always a piece in the center:
((n-1)/2, (n-1)/2) = ((n-1)/2, (n-1)/2*m + s)
 
Let's see which regular toroidal-queen solutions have 90d or fourfold rotation symmetry. Something that the BSDM paper called double symmetry.

6*(2k) + 1 = 4*(3k) + 1
6*(2k) + 5 = 4*(3k+1) + 1

So some of them will, some of them won't.


Turning to toroidal nightriders, it is much more difficult to find overall results. Nonattacking means that there is no solution for
(slk)*(sls) = (mvk)*(mvs) mod n
sls = solution step
mvs = move step
slk, mlk = numbers of steps

This has the consequence that (sls).(eps2).(mvs) mod n = k (relatively prime to n) for all move steps.

eps2 = {{0,1},{-1,0}} the 2D antisymmetric symbol.

For two move steps, one can find solution steps. Let (emvs) = (eps2).(mvs) for convenience.

(sls).(emvs1) = k1
(sls).(emvs2) = k2

Combine the steps into a matrix:
emsmat = {emvs1, emvs2}
Also the k's:
kvec = {k1, k2}

Then
(sls).(emsmat) = (kvec)
and
(sls) = (inverse(emsmat)) . (kvec)

Inversion of a 2*2 is easy. For A = {{a11, a12}, {a21, a22}}
inv(A) = 1/det(A) * {{a22, -a12}, {-a21, a11}}

where determinant
det(A) = a11*a22 - a12*a21
 
In general, kvec = {k1,k2}. But one can scale it and (sls) by (1/k1), since that division is meaningful because k1 is relatively prime to n. Since k1 is in Zx(n), (1/k1) is also. So kvec becomes {1,k} where k = k2/k1.

For rooks, {0,1},
emsmat = {{1,0},{0,1}}

This gives solution (sls) = {1,k}

For bishops, {1,1},
emsmat = {{1,1},{1,-1}}

Its inverse is (1/2)*{{1,1},{1,-1}}

For odd n, one can scale out the (1/2), and one gets solution {1+k,1-k}

But for even n, one cannot, and one gets {1+k',1-k'}/2, where k' = k + b*n where b = 0, 1
Since k is r.p. to n, it is odd, and thus k' is odd. That makes k'+1 and k'-1 even. One can then divide by 2.


Queens are rook * bishop, and one can start with rook solutions, {1,k} and impose bishop conditions. That makes k+1 and k-1 r.p. to n, alongside k.
 
I will now take on nightriders, {1,2}

Within signs and flips, there are three main types of emmat, exemplified by

{{1,2},{1,-2}} and {{1,2},{2,1}} and {{1,2},{2,-1}}

Their inverses are

(1/4){{2,2},{1,-1}} and (1/3){{-1,2},{2,-1}} and (1/5){{1,2},{2,-1}}

That means that one can use any of these three unless n is divisible by 30 = 2*3*5, where I use 2 because it divides 4.


The rook solutions include diagonal ones, the bishop ones include axial ones (along an axis: horizontal and vertical), and the queen ones include steps (1,2) and (1,3), so I will check on what the nightriders have.

For axial solutions, the products with the move steps are +-1 and +-2. That means that n must be odd.

For diagonal solutions, the products with the move steps are +-1 and +-3. That means that n must not be divisible by 3.
 
For rook + nightrider, one can start with the rook solutions (1,k) and add the nightrider conditions. So all these must be relatively prime to n:
1, k, 2k+1, 2k-1, k+2, k-2

For k = 3m,
1, 3m, 6m+1, 3(2m-1)+2,3m+2,3(m-1)+1
k = 3m+1
1, 3m+1, 3(3m+1), 6m+1, 3(m+1), 3(m-1)+2
k = 3m+2
1, 3m+2, 3(2m+1)+2, 3(2m+1),3(m+1)+1,3m

So n must not be divisible by 3. But a solution always exists for n not divisible by 3: diagonal or (1,1)


For bishop + nightrider, one can start with the bishop solutions (1/2) (1+k,1-k) and add the nightrider conditions. Let us first consider the case of n even, Then k must be odd, k = 2k'+1, and we have solution step (1+k',-k'). Adding the nightrider conditions gives
k'-1, k'+2, 3k'+1, 3k'+2

This is a mixture of even and odd numbers, and thus there are no solutions for n even.

So n must be odd, though a solution always exists in that case: axial or (1,0)
 
Now consider a super piece, a hybrid of the bishop, rook, and nightrider: (1,0), (1,1), (1,2).

Starting with the rook solution (1,k), we find that all these quantities must be relatively prime to n:
k, k+-1, k+-2, 2k+-1

Calculating for k = 0 to m-1 mod m,

m = 2
{{0, 1, 1, 0, 0, 1, 1}, {1, 0, 0, 1, 1, 1, 1}}

m = 3
{{0, 1, 2, 2, 1, 1, 2}, {1, 2, 0, 0, 2, 0, 1}, {2, 0, 1, 1, 0, 2, 0}}

m = 5
{{0, 1, 4, 2, 3, 1, 4}, {1, 2, 0, 3, 4, 3, 1}, {2, 3, 1, 4, 0, 0, 3}, {3, 4, 2, 0, 1, 2, 0}, {4, 0, 3, 1, 2, 4, 2}}

m = 7
{{0, 1, 6, 2, 5, 1, 6}, {1, 2, 0, 3, 6, 3, 1}, {2, 3, 1, 4, 0, 5, 3}, {3, 4, 2, 5, 1, 0, 5}, {4, 5, 3, 6, 2, 2, 0}, {5, 6, 4, 0, 3, 4, 2}, {6, 0, 5, 1, 4, 6, 4}}

So n must not be divisible by 2, 3, 5, or 7 - product 210

But if it is not divisible by any of these primes, then solution (1,3) and (1,4) will always exist.
(1,3) - {3, 4, 2, 5, 1, 7, 5}
(1,4) - {4, 5, 3, 6, 2, 9, 7}
Not divisible by any other primes.
 
You must log in or register to reply here.
Back
Top Bottom