Computation

Queens on a torus, and the squares whose every diagonal is a transversal

Roll a chessboard into a torus so that its diagonals wrap round, and ask for n queens that do not attack. Pólya proved in 1918 that it can be done exactly when n shares no factor with 6, by two short sums. A Latin square whose every wrapped diagonal holds each symbol once — a Knut Vik design, from Norwegian field trials — is the same problem solved n times at once. Search finds 10, 28, 88 and 4,524 placements at 5, 7, 11 and 13; every one is a straight line until 13, where 4,394 are not.

Worth reading first: One cell short of a transversal · A field's worth of squares.

The eight queens puzzle asks for eight queens on a chessboard with no two in the same row, column or diagonal. It has 92 solutions, found by Gauss’s contemporaries in the 1850s, and its generalisation to nn queens on an n×nn \times n board has solutions for every nn except 2 and 3. A small change makes it much stricter. Roll the board into a torus, gluing the top edge to the bottom and the left to the right, so that a queen’s diagonal leaving the board on one side comes back on the other. Now every diagonal has exactly nn cells, there are nn of them in each direction, and the question is whether nn queens can occupy all nn rows, all nn columns, and nn different diagonals in each direction.

George Pólya answered it in 1918: exactly when nn is divisible by neither 2 nor 3. The proof of impossibility is two lines of arithmetic, and the construction for the possible sizes is one line more. This essay draws both, counts every solution up to n=13n = 13, and finds the problem hiding in an old question about Latin squares, where each symbol must appear once in every row, every column, and every wrapped diagonal.

A square whose diagonals are all transversals

A square whose every diagonal is a transversal. n=5 k=2: rows 01234 34012 12340 40123 23401
Fig. 1 A Latin square of order 5 in which every wrapped diagonal and anti-diagonal holds each symbol once. The cells holding 0 are five queens on a torus, no two attacking.

One cell short of a transversal defined a transversal of a Latin square: a choice of one cell in every row and every column with every symbol different. It also noticed that in the cyclic square, where the symbol at row ii and column jj is i+ji + j modulo nn, the cells holding one symbol lie on a wrapped diagonal, so a transversal is a placement of nn pieces attacking along rows, columns and one diagonal direction — semi-queens.

The hero turns that around. Here the square is chosen so that every wrapped diagonal and every wrapped anti-diagonal is itself a transversal: walking down any diagonal, wrapping at the edges, meets all five symbols, and so does walking down any anti-diagonal. The right-hand copy of the square shows one of each. In the 1920s the Norwegian agricultural scientist Knut Vik proposed field trials laid out this way — five varieties of a crop planted in a five-by-five grid of plots, each variety once in every row, column and diagonal — so that a fertility gradient running across the field in any of four directions affects every variety equally. Such squares are now called Knut Vik designs.

Look at the cells of one symbol, shaded on the left. There is one in every row and one in every column, since the square is Latin. And no two share a wrapped diagonal or anti-diagonal, since each of those holds the symbol only once. So the five cells are five non-attacking queens on a torus. Every symbol gives such a placement, and the five placements tile the board. A Knut Vik design of order nn is exactly a way of cutting the n×nn \times n torus into nn disjoint toroidal queen solutions, which is why the two problems have the same answer.

The hero’s square is built by one rule: the symbol at row ii and column jj is j−2ij - 2i modulo 5. Moving along a row changes jj and so runs through every symbol; moving down a column changes −2i-2i, which also runs through every symbol because 2 is invertible modulo 5. Along a diagonal both ii and jj increase by one, so the symbol changes by 1−2=−11 - 2 = -1 per step, and along an anti-diagonal by −1−2=−3-1 - 2 = -3 per step; both are invertible modulo 5, so both run through every symbol. The square works because the four numbers 11, 22, 2−12 - 1 and 2+12 + 1 — the row step, the column step and the two diagonal steps — are all units modulo 5.

Lines that work, and the sizes where they cannot

That observation gives every size for which a straight-line solution exists. Put the queen in row ii at column ki+ck i + c modulo nn, for a fixed slope kk and offset cc. The queens occupy different columns when kk is a unit modulo nn; different diagonals, which are indexed by column minus row, when k−1k - 1 is a unit; and different anti-diagonals, indexed by column plus row, when k+1k + 1 is a unit. So a linear solution exists exactly when there is a kk with k−1k - 1, kk and k+1k + 1 all sharing no factor with nn. Three consecutive numbers include an even one and a multiple of three, so if 2 or 3 divides nn no slope works. If neither does, k=2k = 2 works, since 1, 2 and 3 are all units.

A field’s worth of squares built orthogonal Latin squares from the same kind of rule, ki+jk i + j over a field, and the overlap is not an accident. At a prime order the squares j−kij - k i for different admissible slopes kk are mutually orthogonal, and each is a Knut Vik design. Order 5 has two admissible slopes, 2 and 3; order 7 has four, 2, 3, 4 and 5; order 11 has eight. The Knut Vik designs at these orders, counted up to renaming symbols, are exactly as many as the admissible slopes — 2, 4 and 8 — since the search below finds that every placement at these sizes is linear.

Two designs make a magic square

Orthogonality turns two Knut Vik designs into something older. Take the order-5 designs for slopes 2 and 3, A(i,j)=j−2iA(i, j) = j - 2i and B(i,j)=j−3iB(i, j) = j - 3i modulo 5, and combine them into one square of numbers, M=5A+B+1M = 5A + B + 1. Because the two designs are orthogonal, every pair of symbols occurs exactly once, so MM contains each of the numbers 1 to 25 exactly once. Its first row is 1, 7, 13, 19, 25 and its second 18, 24, 5, 6, 12. And because each design holds every symbol once along every row, column and wrapped diagonal, every one of those lines of MM adds up to the same total, 5⋅(0+1+2+3+4)+(0+1+2+3+4)+5=655 \cdot (0 + 1 + 2 + 3 + 4) + (0 + 1 + 2 + 3 + 4) + 5 = 65.

So MM is a pandiagonal magic square: not only its rows, columns and two main diagonals but all ten wrapped diagonals sum to 65. This is the method Philippe de la Hire described around 1705 for building magic squares from two “root” squares, and the magic squares are a space found that magic squares of a given order form a vector space in which the pandiagonal ones are a subspace. The construction here produces points of that subspace from pairs of orthogonal Knut Vik designs, and the impossibility of Knut Vik designs at orders 2, 3, 4 and 6 is one reason that pandiagonal magic squares of those orders are hard or impossible to make this way: at order 4 they exist by other means, while at orders 2, 3 and 6 none exist at all. At prime orders there is far more to choose from: the plane hiding in the squares found n−1n - 1 mutually orthogonal squares at every prime order, and those with admissible slopes give n−3n - 3 Knut Vik designs, any two of which make a pandiagonal magic square.

The same combination explains why Knut Vik’s field layout is good statistics. Placing varieties by the design AA and, independently, a second factor — a fertiliser, say — by the orthogonal design BB gives every combination of variety and fertiliser exactly once, with both factors balanced against gradients in four directions. Orthogonal squares are a code read the same balance as the distance of an error-correcting code: no two plots agree in more than one of their coordinates, so no confusion between factors can hide in the layout.

Two sums that rule the other sizes out

Two sums that rule out the even sizes and the multiples of three. 4:xs 5:ss 6:xx 7:ss 8:xs 9:sx 10:xs 11:ss
Fig. 2 Pólya’s two congruences for sizes 4 to 11. The sums rule out every even size; the sums of squares rule out the odd multiples of three. Only sizes prime to 6 pass both.

Linear solutions fail when 2 or 3 divides nn, but that does not rule out cleverer, non-linear ones. Pólya’s proof does. Suppose q(0),…,q(n−1)q(0), \ldots, q(n-1) is any solution, with the queen in row ii at column q(i)q(i). Since the queens use every column once, qq is a rearrangement of 0,…,n−10, \ldots, n - 1. Since they use every anti-diagonal once, the numbers i+q(i)i + q(i) are all different modulo nn, so they are a rearrangement of 0,…,n−10, \ldots, n-1 too. Add them up two ways:

∑i(i+q(i))=∑ii+∑iq(i)=2⋅n(n−1)2,∑i(i+q(i))≡0+1+⋯+(n−1)=n(n−1)2(modn).\sum_i (i + q(i)) = \sum_i i + \sum_i q(i) = 2 \cdot \frac{n(n-1)}{2}, \qquad \sum_i (i + q(i)) \equiv 0 + 1 + \cdots + (n - 1) = \frac{n(n-1)}{2} \pmod n.

So n(n−1)/2n(n-1)/2 must be a multiple of nn, which means (n−1)/2(n-1)/2 is a whole number, which means nn is odd. The figure tabulates the two sides for sizes 4 to 11, and every even size fails.

The multiples of three need squares. The numbers i+q(i)i + q(i) run over every residue, and so do the differences q(i)−iq(i) - i, since the queens also use every diagonal once. So the sum of the squares of both sets is twice the sum of the squares of all residues, 2⋅∑r22 \cdot \sum r^2. But expanding (i+q)2+(q−i)2=2i2+2q2(i + q)^2 + (q - i)^2 = 2i^2 + 2q^2 and summing gives 4∑r24 \sum r^2. Hence 2∑r=0n−1r2=n(n−1)(2n−1)/32 \sum_{r=0}^{n-1} r^2 = n(n-1)(2n-1)/3 must be a multiple of nn. When 3 divides nn it is not: (n−1)(2n−1)(n-1)(2n-1) is then not divisible by 3, and the fraction does not cancel. The figure’s last columns show the squares agreeing at 5, 7 and 11 and disagreeing at 9, the first odd multiple of three.

Together the two sums prove the theorem’s negative half for every size at once, and the construction proves the positive half. The proof never places a queen. It uses only that four families of lines — rows, columns, diagonals, anti-diagonals — are each hit exactly once, and asks what that forces about the first two power sums of the positions. The same method, with higher powers, rules out analogous placements in other settings, and it is the reason the impossible sizes are not merely sizes where nobody has found a solution.

Counting every placement

Queens on a torus, size by size. 2:0/0 3:0/0 4:0/0 5:10/10 6:0/0 7:28/28 8:0/0 9:0/0 10:0/0 11:88/88 12:0/0 13:4524/130
Fig. 3 Every toroidal placement of n queens for n from 2 to 13, and how many are linear. All of them are, until 13.

The theorem says when solutions exist. An exhaustive search says how many. It places queens row by row, rejecting any column, diagonal or anti-diagonal already used, and it finds no solution at all for any nn from 2 to 12 that shares a factor with 6, as the sums require. For the others it finds 10 at n=5n = 5, 28 at n=7n = 7, 88 at n=11n = 11 and 4,524 at n=13n = 13.

The first three counts are exactly the linear solutions. At n=5n = 5 there are two admissible slopes and five offsets, 2×5=102 \times 5 = 10; at n=7n = 7, 4×7=284 \times 7 = 28; at n=11n = 11, 8×11=888 \times 11 = 88. Every placement of queens on the 5, 7 or 11 torus is a straight line wrapped round it, and the arithmetic of the previous sections describes all of them. That is a surprise of its own: the ordinary eight-queens problem has solutions with no visible pattern at all, and the toroidal version, with its extra constraint, is rigid enough at small sizes to force every solution into the simplest possible form. Nine thousand four hundred and eight counted Latin squares and found the counts exploding from order five on; the squares with the Knut Vik property are so constrained that at orders 5, 7 and 11 they are all variants of one formula.

At 13 the rigidity breaks. There are ten admissible slopes, giving 130 linear placements, and the search finds 4,394 more. The torus of size 13 is the first on which queens can be arranged in a way that no line describes.

Thirteen queens that follow no line

Thirteen queens that follow no line. linear 0,2,4,6,8,10,12,1,3,5,7,9,11; non-linear 0,2,4,6,11,9,12,5,3,1,7,10,8
Fig. 4 Two placements of thirteen queens on the 13 × 13 torus. On the left each queen sits two columns right of the one above; on the right the steps vary. 4,394 of the 4,524 placements are of the second kind.

The figure compares a linear placement, with every step from one row to the next equal to 2, with one of the non-linear ones, whose steps run 2, 2, 2, 5, 11, 3, 6, 11, 11, 6, 3, 11, 5. The non-linear placement still has one queen in every row, column, diagonal and anti-diagonal, so it is just as valid; it simply does not repeat itself. Read round the cycle from one 5 to the other, the steps form a palindrome, 5, 11, 3, 6, 11, 11, 6, 3, 11, 5, and the three steps of 2 that remain are a stretch of the slope-2 line; the placement looks like a piece of a line spliced to a symmetric arc, joined where the splice happens not to create an attack.

The count grows quickly from here, while the linear solutions number only nn times the number of admissible slopes, so they become a vanishing fraction; at 13 they are already under 3%. One random path down a search tree estimated the ordinary nn-queens counts by sampling, because exhaustive search runs out of time quickly, and the toroidal counts beyond about 20 have the same difficulty.

Whether the non-linear placements at 13 can be fitted together, thirteen at a time, into a non-linear Knut Vik design is a finite question: it asks for thirteen of the 4,524 placements that are pairwise disjoint. A search over such combinations is far larger than the search for single placements, and it is not settled here. What is certain is that linear designs exist at 13, one for each of the ten admissible slopes, and that every design at 5, 7 and 11 is linear: the partitions of those boards into placements number exactly 2, 4 and 8, one per slope.

How close the impossible sizes come

How many queens the impossible sizes allow. 2:1 3:1 4:2 5:5 6:4 7:7 8:6 9:7 10:9 11:11 12:10 13:13 14:13
Fig. 5 The most non-attacking queens on the n × n torus, as a shortfall from n. Multiples of three fall two short; the other even sizes one short, except 4 and 8, which fall two short.

When nn queens cannot be placed, the natural next question is how many can. A branch-and-bound search answers it for every size up to 14. At the sizes prime to 6 the answer is nn, as it must be. At every multiple of three searched — 3, 6, 9 and 12 — the most is n−2n - 2. At the even sizes not divisible by three, it is n−1n - 1 at 2, 10 and 14, and n−2n - 2 at 4 and 8.

Pólya’s sums say why the shortfall cannot be zero but not why it is one or two, and the figure’s irregularity at 4 and 8 is a warning that small cases have their own behaviour. On the ordinary, unwrapped board, nn queens fit for every nn above 3; the torus removes the edges and in exchange imposes four exact constraints, and it is the exactness — every diagonal hit precisely once — that the sums exploit. With one queen fewer, one diagonal in each direction may be empty, the sums no longer have to balance, and the congruences lose their grip.

What the squares cannot show

The figures show solutions and count them, and the sums prove that no others exist at the impossible sizes. What none of them shows is a reason for the counts at the possible sizes — why 13 is the first size with non-linear placements, or how fast the counts grow. Those are properties of the search, not consequences of any argument given here, and the claim that every placement below 13 is linear rests on the search having been exhaustive, which it was, and on its rejecting attacks correctly, which is checked separately on every placement it returns.

The Latin-square side has a subtler limit. A Knut Vik design is a Latin square with extra conditions, and the thirty-six officers asked about Latin squares with an orthogonal mate. At a prime order every Knut Vik design built from a line has an orthogonal mate — the design for another slope — and so do all the designs at 5, 7 and 11, which are all linear. Whether every Knut Vik design at every order has a mate is not something the figures address; the agricultural motivation needed only one square, and the mathematical questions about the family as a whole were raised later.

Still open: how many, at every size

The number of toroidal queen placements is known only by computation, size by size, and no formula for it is known, nor even its rate of growth to within a constant factor in the exponent. For the ordinary nn-queens problem the growth rate was determined in 2021 by Michael Simkin, who showed that the count is about (0.143 n)n(0.143\,n)^n, using methods from the theory of random structures; the corresponding toroidal problem, with its arithmetic restriction to sizes prime to 6, is less well understood, though estimates of the same kind have since been proved for it. The Latin-square question is wider still: how many Knut Vik designs of each order exist, and how quickly do the non-linear ones come to dominate? The fewest entries that fix a Latin square found that even the smallest questions about Latin squares become search problems almost immediately, and the designs whose every diagonal is a transversal are no exception.

Shares its objects with

Essays that name at least two of the same things, and that neither author linked.

Named objects

A dashed tag is an object no other essay names yet.

Exhaustive searchLatin squareModular arithmeticOrthogonal latin squaresTorusTransversal