Queens on a torus, and the squares whose every diagonal is a transversal
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 queens on an board has solutions for every 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 cells, there are of them in each direction, and the question is whether queens can occupy all rows, all columns, and different diagonals in each direction.
George Pólya answered it in 1918: exactly when 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 , 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
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 and column is modulo , the cells holding one symbol lie on a wrapped diagonal, so a transversal is a placement of 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 is exactly a way of cutting the torus into 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 and column is modulo 5. Moving along a row changes and so runs through every symbol; moving down a column changes , which also runs through every symbol because 2 is invertible modulo 5. Along a diagonal both and increase by one, so the symbol changes by per step, and along an anti-diagonal by per step; both are invertible modulo 5, so both run through every symbol. The square works because the four numbers , , and — 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 at column modulo , for a fixed slope and offset . The queens occupy different columns when is a unit modulo ; different diagonals, which are indexed by column minus row, when is a unit; and different anti-diagonals, indexed by column plus row, when is a unit. So a linear solution exists exactly when there is a with , and all sharing no factor with . Three consecutive numbers include an even one and a multiple of three, so if 2 or 3 divides no slope works. If neither does, 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, over a field, and the overlap is not an accident. At a prime order the squares for different admissible slopes 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, and modulo 5, and combine them into one square of numbers, . Because the two designs are orthogonal, every pair of symbols occurs exactly once, so 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 adds up to the same total, .
So 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 mutually orthogonal squares at every prime order, and those with admissible slopes give 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 and, independently, a second factor — a fertiliser, say — by the orthogonal design 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
Linear solutions fail when 2 or 3 divides , but that does not rule out cleverer, non-linear ones. Pólya’s proof does. Suppose is any solution, with the queen in row at column . Since the queens use every column once, is a rearrangement of . Since they use every anti-diagonal once, the numbers are all different modulo , so they are a rearrangement of too. Add them up two ways:
So must be a multiple of , which means is a whole number, which means 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 run over every residue, and so do the differences , 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, . But expanding and summing gives . Hence must be a multiple of . When 3 divides it is not: 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
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 from 2 to 12 that shares a factor with 6, as the sums require. For the others it finds 10 at , 28 at , 88 at and 4,524 at .
The first three counts are exactly the linear solutions. At there are two admissible slopes and five offsets, ; at , ; at , . 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
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 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 -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
When 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 , as it must be. At every multiple of three searched — 3, 6, 9 and 12 — the most is . At the even sizes not divisible by three, it is at 2, 10 and 14, and 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, queens fit for every 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 -queens problem the growth rate was determined in 2021 by Michael Simkin, who showed that the count is about , 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.
- A mate is rare until order ten — both name exhaustive search, latin square, orthogonal latin squares, transversal
- Sixteen of five hundred and seventy-six — both name exhaustive search, latin square, orthogonal latin squares, transversal
- Ten digits need a symmetry that does not commute — both name exhaustive search, latin square, modular arithmetic, transversal
- The best of thirty-four thousand scramblings — both name exhaustive search, latin square, transversal
- A code that survives a lost bit — both name exhaustive search, modular arithmetic
- A Latin square with boxes — both name exhaustive search, latin square
Named objects
A dashed tag is an object no other essay names yet.
Exhaustive searchLatin squareModular arithmeticOrthogonal latin squaresTorusTransversal