WorksComputer Science
How Unbalanced Must a Latin Rectangle Be?
Abstract
We view a Latin rectangle as points in the grid . Each symbol gives one point, whose coordinates are the columns it occupies. The rectangle is balanced when these points are pairwise equidistant in the metric. Its imbalance measures the distance from this ideal. We study the minimum imbalance from three sides. Constructively, we use a simulated annealing that moves symbols within rows and only penalises column clashes. Against the reference table of Voboril et al. (2025), it improves 33 of the 51 non-square values for , by up to 39.4%, and matches the rest. A cheap invariant, the row group, certifies that none of the 33 new rectangles is isotopic to rows of a group table, so the earlier column-swapping local search cannot reach any of them. Exactly, a computer-assisted branch and bound proves that the minimum imbalance of a rectangle is . Díaz et al. found this value, but its optimality was open. A sharper pruning bound, derived from the identity , reduces the search tree by a factor of to on the instances with that we solve. Asymptotically, the minimum imbalance is for every fixed . A pigeonhole argument gives a lower constant of order , and random rectangles give an upper constant of order . For , the limit of exists, a permuton attains it, and it lies between and . Perfect balance is an -equilateral problem, so it forces rows. For rectangles, single two-minute annealing runs improve five of the seven six-hour MIP upper bounds for . Finally, the Lean 4 kernel checks every rectangle reported in this paper against a 74-line specification that imports only Lean's core library. We also prove the pigeonhole lower bound in Lean with Mathlib.
Introduction
In an agricultural field trial, the treatments occupy a grid of plots. When some pairs of treatments are systematically planted closer together than others, spatial correlation in the soil can bias their comparison [14]. Latin designs remove the row and column effects, but not this one. Spatially balanced Latin squares ask, in addition, that every pair of treatments be equally far apart on average [5, 9]. Díaz et al. [3] posed the same question for rectangles, observed that perfect balance is then usually impossible, and asked instead for rectangles of minimum imbalance. Later work on the problem uses SAT encodings that prove optimal with checkable proof certificates [11] and mixed-integer programming [10]. It also uses streamliners written by large language models [16] and LLM agents that reformulate models [15]. Closest to our work, Xia et al. [17] use simulated annealing for spatially balanced Latin squares and reach the optimum for and in under a second. They also prove an lower bound on the imbalance of squares with , by a parity argument. The starting point of this paper is the reference table of Voboril et al. [16], which collects the best values that the methods above obtained for rectangles. To our knowledge, this table is still current. The later work [15] reports aggregate model comparisons but no per-instance values, and Xia et al. [17] treat only squares.
Here is the point of view of this paper. Record, for each symbol , the columns that it occupies in the rows. This gives a point . The distance between two symbols that the literature uses is exactly the distance . A balanced rectangle is therefore a set of points in a -dimensional grid that are pairwise equidistant in the taxicab metric. When is small compared with , the grid is too crowded for equidistance, and § 8 makes this quantitative. When there is room, consistent with the existence of balanced squares for infinitely many . The point picture also suggests a search that moves individual points, rather than one that rearranges a rigid algebraic pattern.
Contributions
New upper bounds (§ 4 and § 5). The search keeps each row a permutation and turns the column condition into a penalty with an adaptive weight. A move swaps two symbols within a row, and the search evaluates its effect exactly in time. Against the reference table of Voboril et al. [16], the search improves 33 of 51 instances and matches the other 18.
A new optimum (§ 6). A branch and bound that places one symbol at a time proves that the known value 56 is optimal for , which was open. It also independently reproduces the known optima for with and for and . A second, independent implementation with a sharper bound confirms the , and results and the and optima.
A certificate of non-group structure (§ 7). The permutation group generated by the ratios of the rows does not change under column operations. For rectangles taken from group tables, its order divides . For 32 of our 33 improved rectangles it is the full alternating or symmetric group, and for the last one it has order 46080. So local search that only permutes the columns of a cyclic rectangle [3] cannot reach any of them. The invariant does not separate our rectangles from the published SAT and streamliner rectangles, most of which are also far from group tables.
Cubic growth (§ 8). For every fixed , the minimum imbalance is . The lower constant is of order , while random rectangles give an upper constant . The right order in is open. Perfect balance also requires , by a classical bound on equilateral sets.
The case (§ 9). On the open instances , we compare a single-seed two-minute annealing run with the six-hour upper bounds of Mirka et al. [10]. The run improves the bound for , ties at and is worse at . The limit of exists and is the minimum of a continuous functional on permutations. We bracket it between and 0.1196, and we compute the upper value exactly for the permution of one rectangle.
6. A Lean formalisation (§ 10). Lean’s kernel certifies all 62 rectangles behind our upper bounds by evaluation. The check uses no native_decide and no Mathlib, only Lean’s core library, so it trusts only the kernel and a short specification. We prove the identity (1) and Theorem 5 in Lean with Mathlib. Each formalised statement names the Lean theorem that proves it.
None of the algorithmic ingredients is new by itself. Simulated annealing [7] is established, including for the square version of this problem [17]. So are row-preserving swaps with temporarily violated column constraints [18, 19] and adaptive penalties, also known as strategic oscillation [4]. What we add is their combination for rectangles, the resulting records, and the exact and asymptotic results.
Preliminaries
A Latin rectangle () is an array with entries in in which no symbol repeats in a row or in a column. Let denote the column of symbol in row and . Following Díaz et al. [3] and Peruvemba Ramaswamy and Szeider [11],
Each row contributes to the total distance, so is the average distance over all pairs. In particular the deviations sum to zero, and
The pairs that are too close and the pairs that are too far therefore contribute equally to the imbalance. This identity drives both the pruning bound of § 6 and the lower bound of § 8. (In Lean, the average is LatinRect.sum_dist and the identity is LatinRect.imbalance_eq_two_mul_sum_pos.) The quantity is an integer. As in the literature, we write imbalances as , and for , and .
Two dictionaries. We can read a rectangle through its rows or through its points. Through its rows it is a -tuple of bijections from columns to symbols, with for . Through its points it is a set in whose coordinate projections are bijections. The column condition says exactly that every point has distinct coordinates. The imbalance is invariant under relabelling symbols, permuting rows and reversing the order of the columns, , which preserves every distance. It is not invariant under general column permutations. After relabelling the symbols, we may assume .
Search: rows as permutations, columns as a penalty
The state of the search is a -tuple of permutations with . It need not be Latin. A move picks a row and two columns , and swaps the symbols and . In the point picture, the move exchanges the -th coordinates of the two points and , and nothing else moves.
Lemma 1 (Incremental evaluation). After the move, only the distances and with change, and with ,
Hence the exact change of is computable in integer operations.
Proof. The move only exchanges the -th coordinates of and . So does not change, and no pair without or is affected.
Penalty. Let be the number of excess occurrences of symbols in columns. Per-column counters maintain in time per move. The search minimises and records only states with . The weight starts at and stays in . Every proposals, the search multiplies by 1.02 if the current state has conflicts and by 0.99 otherwise. The search can therefore leave the Latin rectangles, pass through non-Latin states and return. By contrast, moves that permute whole columns never leave the Latin rectangles, and as § 7 shows, they never change the row group.
Schedule. The search starts from the cyclic rectangle . It accepts a move of change with probability . The temperature starts at (in units of ) and is multiplied by 0.9999995 per proposal. It never drops below 0.05, which it reaches after about proposals. Most of a run is therefore a low-temperature walk on plateaus. If the best Latin rectangle found so far does not improve for proposals, the search resets the temperature to . The search discards a proposal with but still counts it, and does not cool for it. Runs are single-threaded, and the search re-evaluates the reported rectangle from scratch.
An independent checker, written from the definition with exact rational arithmetic, verifies every reported rectangle. It also reproduces the imbalances reported for all fourteen rectangles printed in [11, 16]. Lean’s kernel also certifies every reported rectangle (§ 10).
Improved upper bounds
We take the 51 non-square instances , of Table 1 of [16], which also collects the earlier records. All runs used an Apple M3 laptop, one core per run. Each instance received independent runs of 1 and 5 CPU minutes. The larger instances (, ) also received a 10-minute run, so each instance used at most 16 CPU minutes. Table 1 reports the best of these runs. Of the 33 new values, 10 came first from the 1-minute run, 8 from the 5-minute run and 15 from the 10-minute run. The search improves 33 values, matches 18 and is worse on none. The mean improvement is 18.5% and the largest is 39.4% (12 × 13: 274.0 → 166.0). The search matches every record with or , every record with except 3 × 12, and the records for 4 × 10, 5 × 10 and 6 × 12. Several of these are proven optimal [10, 11], so matching is the best possible there.
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | |
| 8 | 40.0 | 36.0 | 32.0 | 30.0 | 24.0 | 28.0 | |||||
| 9 | 65.3 | 56.0 | 53.3 ~~56.0~~ | 48.6 ~~52.6~~ | 40.0 ~~48.0~~ | 43.3 ~~51.3~~ | 42.6 ~~53.3~~ | ||||
| 10 | 92.0 | 80.0 | 78.6 | 66.6 | 60.0 ~~70.0~~ | 58.0 ~~72.0~~ | 58.6 ~~70.0~~ | 64.0 ~~70.0~~ | |||
| 11 | 124.0 | 114.0 | 104.0 ~~112.0~~ | 94.0 ~~116.0~~ | 88.0 ~~108.0~~ | 84.0 ~~118.0~~ | 78.0 ~~114.0~~ | 84.0 ~~120.0~~ | 100.0 ~~110.0~~ | ||
| 12 | 168.0 | 152.0 ~~154.0~~ | 149.3 ~~154.6~~ | 140.0 ~~145.3~~ | 120.0 | 121.3 ~~164.0~~ | 116.6 ~~148.0~~ | 106.0 ~~154.0~~ | 124.0 ~~174.6~~ | 136.6 ~~147.3~~ | |
| 13 | 218.6 | 198.0 | 201.3 ~~211.3~~ | 191.3 ~~210.6~~ | 166.0 ~~204.0~~ | 164.0 ~~203.3~~ | 160.0 ~~220.6~~ | 152.0 ~~214.0~~ | 154.6 ~~240.6~~ | 168.0 ~~224.0~~ | 166.0 ~~274.0~~ |
Table 1. Table 1. Minimum known imbalance of Latin rectangles. Bold: new value from this work (best of the 1-, 5- and 10-minute runs), with the previous best value struck through below it. Previous values are those collected in Table 1 of Voboril et al. [16], which includes results of [3, 10, 11], of 4-hour Gurobi runs and of LLM-generated streamliners. Plain: a record that our search matches. Every bold or plain value is attained by a rectangle certified in Lean (Certificates.exists_k*_n*, § 10). The struck-through values are taken from the literature and are not certified.
Variability. Single runs are noisy. In 9 of the 33 improved cells, a longer run ended with a worse value than a shorter one. Across the three budgets, the final values of a cell differ by a median of 5% and at most 32.5%. The values in Table 1 are therefore upper bounds from a few runs, not estimates of typical performance.
Prior effort. Most previous values come from Voboril et al. [16]. They add LLM-generated streamlining constraints to a MiniZinc model and solve it with Gurobi. They run the streamliners either incrementally, warm-starting each round from the best solution so far, or with an evolutionary search. Their runs take 4 hours or more on dual 10-core Xeon nodes. The other previous values come from 4-hour Gurobi runs and earlier literature [3, 10, 11].
These runs used different hardware, different time limits and a general-purpose solver, so we compare values, not methods. Several previous values are attested by printed rectangles. For instance, the value 274.0 for 12 × 13 is the rectangle in Fig. 6h of [16], and our checker and Lean reproduce it. The amount of search behind each previous value also varies between cells. So the size of an improvement need not reflect the difficulty of an instance.
Speed. We reran the search with 5 fresh seeds on every improved instance, stopping when it beat the record (Figure 2b). All 165 runs succeeded. The median time to beat the previous record (not to reach our final value) was 0.12 CPU seconds and the maximum 143 seconds. For the reasons above we make no runtime comparison with earlier work. We measured these times on the Apple M3 laptop and did not archive their logs. An independent rerun of the same 165 runs used the original source on Linux x86-64 with GCC. It beat every record (pooled median 0.21 CPU seconds, maximum 280) and ended at the same values as the original runs. Its logs are in the validation/ directory of the repository.
Figure 2. The 33 improved instances. (a) Previous record (open circle) and new value (filled). (b) CPU time until the search first beats the record: median (dot) and range (bar) over 5 seeds, log scale.
Exact search and a new optimum
To complement the upper bounds, we wrote a branch and bound that decides whether a rectangle with exists for a given bound .
Branching. With fixed, the search places the symbols in the order . Placing a symbol means choosing its column in each row , subject to the Latin conditions. The search places symbol 1 in increasing columns of rows . This loses nothing. Relabelling the symbols makes , and permuting rows keeps . Symbol 1 occupies distinct columns in those rows, so exactly one such permutation makes its columns increase with the row index. Both operations preserve . A node is one choice of a column for a symbol in one row that passes the Latin check. When symbol is complete, the deviations for all are final, and the search adds them to the cost. We do not yet exploit the choice of the row that is fixed to the identity, or the column reversal of § 3. Together they offer up to another factor of symmetry.
Bounds. Every unplaced row adds at least 1 to any distance, because the two symbols occupy different columns, and at most . So, while the search places a symbol, each pair with has a known overshoot and a known shortfall . Here is the distance over the rows placed so far, and is the number of rows still to place. Let and be the sums of the positive and negative parts of the final deviations , so that the cost so far is . By (1), , so each of
is a lower bound on . The search prunes the node when their maximum reaches . The first version of our program used only . The other two terms cost a few additions per node. When a symbol is complete, the first program also adds for every pair that is not yet final. This is valid only for the first of the three bounds, because a pair’s deviation can lie on either side of . For and we have . A run with equal to three times the value of our rectangle either finds a better rectangle or proves that none exists.
Theorem 2 (computer-assisted). The minimum imbalance of a Latin rectangle is 56. The upper bound is the rectangle of Figure 1, certified in Lean as Paper.three_by_nine. The lower bound is not formalised (§ 10). With the first bound, the branch and bound explores nodes in 140 CPU seconds and finds no rectangle with . As a sanity check, a run with finds a rectangle of value 56. Díaz et al. [3] had already found the value 56 itself. To our knowledge, its optimality was not known. That paper does not prove it, and Table 1 of [16] lists it as unproven.
Figure 1. A rectangle of imbalance 56, which Theorem 2 proves optimal. (a) The rectangle, one colour per symbol. (b) The deviation of every pair from the average distance . Blue pairs are too far apart and red pairs too close. (c) Histogram of the 36 deviations. They sum to zero, and .
A second implementation. To reduce the dependence on a single program, we re-derived the result with a second implementation. It was written independently from the description above and uses the sharper bound. Restricted to the first bound, it explores the same number of nodes as the first program to the precision we recorded ( against for , against for ). With the sharper bound, it confirms the three results with using 2.4 to 3.3 times fewer nodes. It confirms the and optima with about 1.5 times fewer nodes (Table 2). Both programs share the branching scheme, so this guards against coding errors but not against an error in the scheme itself.
Table 2. Exact branch and bound, single core. Each run proves that no rectangle beats our upper bound. The sharper-bound node counts are from the second implementation. We omit its CPU times because they were measured on a shared machine. On all small instances with and the first program also reproduces the values reported in [3].
Table 2 summarises the runs. The method is deliberately plain: no symmetry beyond row order and symbol relabelling, and no learned bounds. With a 30-minute cap per instance and the first bound, the remaining open instances with stay undecided. Unlike the DRAT proofs of [11], our search does not emit a checkable certificate. Theorem 2 therefore rests on the correctness of two short programs. The first, which we publish, reproduces all the known optima listed above. The second, which is not yet in the repository, reproduces those for , , and . A certificate in the style of [11] is the natural next step, and the overshoot and shortfall bounds may be worth encoding there as redundant constraints.
A certificate that the new rectangles are not group-based
Díaz et al. [3] start their local search from random rows of the cyclic Latin square. They repeatedly swap two random columns, keep a swap only when it lowers the imbalance, and restart with fresh rows. They note that the method “never leaves its isotopic class”. Two rectangles are isotopic if permuting rows, columns and symbols turns one into the other. So permuting columns preserves the isotopy class by definition. The question is how to see that a given rectangle lies outside every such class. We give an invariant that is cheap to compute and detects whether a rectangle can come from a group table. It is not a complete isotopy invariant, and it does not by itself explain why one search outperforms another.
Definition 3. The row group of a Latin rectangle with rows is the permutation group on symbols
The element sends the symbol in column of row to the symbol in column of row . Since , the group is already generated by the ratios . In particular, for the row group is the cyclic group generated by , so it carries no information beyond the cycle type of one permutation.
Proposition 4.
(i) Permuting columns does not change . Permuting rows permutes its generators. Relabelling symbols by replaces it by . So the conjugacy class of is an isotopy invariant.
(ii) If is isotopic to rows of the Cayley table of a group of order , then is conjugate to a subgroup of the left-regular representation of . In particular it acts semiregularly (only the identity fixes a symbol) and divides .
(iii) For , a swap in row left-multiplies by a transposition and fixes the other generators. A single swap can therefore enlarge the row group.
Proof. (i) Replacing every row by gives . The other two statements are immediate. (ii) Up to isotopy, with and a bijection onto . Then maps to , so it is , where is left multiplication by . (iii) Swapping two symbols in row replaces by for a transposition .
So any search whose moves permute columns, starting from rows of a cyclic Latin square, stays among rectangles whose row group is cyclic of order dividing . Figure 3 shows the row groups of the best rectangles we found. Of the 33 improved rectangles, 29 have row group and 3 have (5 × 9, 8 × 9 and 3 × 12). The remaining one, 5 × 12, has a row group of order 46080 = , which does not divide 12. By Theorem 4(ii), none of the 33 rectangles is isotopic to rows of a group table. In particular, the column-swapping search of [3] cannot reach any of them. The row group of the 5 × 12 rectangle is the full centraliser of the pairing of symbols. This mirror symmetry also appears in the published 4 × 12 and 5 × 12 records.
Figure 3. Row groups of our best rectangles in the benchmark range. Shading shows the improvement over the previous best value, and grey cells are matched records. Each label gives the row group: or , otherwise its order. For the row group is cyclic, generated by one permutation. It still certifies non-group structure when its order does not divide .
What this does and does not show. The row group certifies that column-based local search cannot reach our rectangles. It does not explain why annealing finds better upper bounds than those reported by the exact solvers and streamliners, which supply most of the records we improve. Ten of the fourteen published SAT and streamliner rectangles also have row group . The SAT encodings aim at optimality proofs, while the streamliner approach searches a general-purpose model with a MIP solver under LLM-proposed restrictions. We have not isolated which ingredient of our search accounts for the better upper bounds.
Cubic growth for a fixed number of rows
Why does imbalance grow so quickly with (Table 1), and why can squares be perfectly balanced? The point picture gives a short answer. For fixed , there is not enough room in for points that are pairwise far apart.
Theorem 5 (Lean: cubic_lower_bound_ceil). Let be a Latin rectangle and
an integer, and put . Then
whenever , that is, . Consequently, for every fixed ,
Proof. Cut each axis of into intervals of at most consecutive values. This cuts the grid into boxes. Two points in the same box differ by at most in every coordinate, so their distance is at most . If box holds of the points, convexity gives
pairs that share a box. Each of them has . Inserting this into (1) proves the first claim. For the second, take for a fixed . Then and , and the bound becomes (lower_bound_explicit), which is (eventually_lower_bound). For the upper bound (imbalance_le), gives , and .
The Lean proof (§ 10) follows these lines and does the convexity step with the Cauchy–Schwarz inequality .
The upper constant is crude. Random rectangles do much better, though we have not formalised this.
Proposition 6. Let be independent and uniform on , put and . Then for every fixed , , and
In particular in Theorem 5.
Proof. Choose independently and uniformly from , ignoring the column condition. For a fixed pair the pairs are independent across and uniform over ordered pairs of distinct columns. Realise them as and conditioned on being distinct, an event of probability . Rounding changes each coordinate difference by less than 1. Conditioning on the events changes the joint law by in total variation, while . Together with , this gives . Summing over the pairs, . The number of clashes, that is, of triples with and the same symbol in column of rows and , has . Choose an outcome with .
Now repair the clashes one at a time. Suppose symbol sits in column of row and also of another row. Swap it with the symbol in a column of row with , chosen so that, in the other rows, does not occur in column and does not occur in column . At most columns are excluded, so such a exists once . The swap removes the clash of , creates none, and changes at most distances by at most each, so it changes by at most . After at most swaps the rectangle is Latin, with . Finally, and , so the Cauchy–Schwarz inequality gives . □
The proof of Theorem 5 is a pigeonhole argument, and Figure 4a shows it at work. Clustered points are expensive, and in a low-dimensional grid clustering is unavoidable. Three remarks put the theorem in context.
Figure 4. rectangles as point sets. (a) The proof of Theorem 5 for a rectangle with : a grid of boxes, and in red the pairs that share a box. Each such pair is closer than the average and costs imbalance. (b) The best rectangles found by annealing for larger (one 2-minute run each), rescaled to the unit square. Most points lie on a few long parallel diagonal runs, with scattered extra points.
Remark 7 (Constants). For , the maximum that defines is attained at , which gives (lowerConst_two_five, lowerConst_two_le). Also , the value for a uniformly random derangement. For , , attained at (lowerConst_four, lowerConst_le_four). Numerically, for large , for example and . So the lower constant is of order , and the upper one grows like . We do not know the right order in .
In the benchmark range, the finite- lower bound is weak. For it gives , against the true optimum , and for it becomes positive only at . Its message is asymptotic. For fixed , the average deviation per pair, , grows linearly in , the same order as the target itself. So rectangles are imperfect on average at the scale of .
Remark 8 (Squares). The bound is useless when grows with , and it must be. Spatially balanced Latin squares exist, for instance whenever is prime, by a construction that streamlined search itself discovered [9]. In there is room for equidistant points. For squares with , where perfect balance is impossible, Xia et al. [17] prove , an order rather than . The bound is attained for up to [17]. It is not known whether the minimum for squares is of order at most for every . The point picture raises a natural question, which we leave open: how does the minimum imbalance pass from order at fixed to these much smaller values at ?
Remark 9 (Equilateral sets). A perfectly balanced rectangle needs , so that is an integer. It is also a set of points in that are pairwise equidistant in , that is, an equilateral set of . Hence , the largest size of such a set. Kusner conjectured . The conjecture is known for , where the case is due to Koolen et al. [8]. In general, Alon and Pudlák [1] proved . The survey of Swanepoel [12] covers these results. So a perfectly balanced rectangle needs rows. For this gives , which recovers part of the case analysis of Díaz et al. [3]. Their arguments are sharper for . Their bound coincides with ours at and is vacuous for . The point sets of rectangles are far more special than general equilateral sets, because their coordinate projections are bijections onto . So we do not expect these bounds to be tight. We did not find this connection in the literature on balanced designs.
Two rows
For a rectangle is a derangement , and the points form its permutation diagram. Mirka et al. [10] solved to optimality with a clique-based MIP and reported bounds up to after six hours. Table 3 adds our two-minute annealing runs. They improve the upper bound for , tie at and lose at . At , the best bound of [10] came from eight parallel six-hour runs. Our runs are single runs with one seed, and the improvements are small (0.2–2%). The MIP also spends its time on lower bounds. So the comparison shows only that annealing is a strong source of incumbents. The lower bounds remain far away, and we did not try to improve them.
Table 3. rectangles beyond the proven range. The lower and upper bounds are the best over all methods and configurations in Tables 1, 2 and 4–7 of [10], from 6-hour runs. Annealing: one 2-minute single-core run. Bold: better than the previous upper bound. The lower bounds are those reached when the 6-hour limit expired, which is why they are not monotone in . The values 201.57 and 273.82 come from one instance with 32 threads in their Table 6 and are decimals as reported there. All other values use the , convention.
The shape of good permutations. Figure 4b shows the best permutations that annealing finds for . They are not known to be optimal, but they are far from random. Most points lie on a few long parallel segments of slope 1, cyclically shifted against one another, with a minority of scattered points.
A limit object. A permuton is a probability measure on with uniform marginals. Every permutation of defines one, , uniform on the squares . Put
where and are independent samples of .
Proposition 10. For , converges as to , where the minimum over permutons is attained.
Proof. Let , which is bounded and 1-Lipschitz for the norm on . If weakly then weakly, so is continuous. Permutons form a weakly closed subset of the compact space of probability measures on , so attains its minimum.
Fix a derangement of and take the rectangle with , whose points are the cells of . Write
Each ordered pair corresponds to a pair of cells of of weight . Within these cells, differs from by at most , and by at most . The diagonal cell pairs carry total weight and are absent from . Hence for an absolute constant , uniformly in . This gives .
Conversely, let attain the minimum. Sampling independent points from and taking the induced permutation gives permutations with almost surely [6]. Remove the fixed points of one at a time: if , exchange the values at and , where for and for . Then becomes and becomes , so no new fixed point is created. Each exchange moves two points by one cell, so it changes by at most , and there are at most of them. The resulting derangements satisfy .
The uniform permuton gives , the limit for a random derangement, and the diagonal (the cyclic rectangle) gives . Optimising numerically over permutons made of increasing or decreasing segments gives , and for . The permuton of our rectangle does better. On a pair of distinct cells, is a constant plus a sum of four independent uniform variables. So is a finite sum of explicit polynomial integrals, and exact rational arithmetic gives . This is our best upper bound for the limit. The rectangle itself has , so . The diagonal cells account for almost all of the difference . They contribute to , and the remaining 0.00005 comes from the within-cell smoothing and from . The finite values in Figure 5 therefore lie below the limit estimate by about .
Figure 5. Normalised imbalance for . Black: proven optima. Grey: interval between the best lower and upper bounds of [10]. Blue dots: our annealing values. Blue dashes: for our rectangle, an upper bound for the limit (Theorem 10). Red: Theorem 5 at each (solid) and its limit (dashed). A uniformly random derangement has (dotted).
Question. What is ? We know only that it lies between and 0.1196. Is the minimiser unique, and is it a finite union of segments?
Formal verification in Lean 4
Most computational results on balanced rectangles rest on unverified programs. The DRAT proofs of Peruvemba Ramaswamy and Szeider [11] are an exception, and for squares Xia et al. [17] verified their lower bound in Lean 4. We formalised the parts of this paper where formalisation is cheap and useful, in Lean 4 [2] with Mathlib [13]. The development has about 700 hand-written lines plus generated certificates. It is in the lean/ directory of the repository, and Table 4 maps the statements of the paper to Lean names.
| statement in the paper | Lean name | uses |
| all rectangles (Table 1 and Table 3, Figure 1) | Certificates.exists_k*_n* | core |
| ; is the mean distance | imbalance_eq_imb3, sum_dist | Mathlib |
| identity (1) | imbalance_eq_two_mul_sum_pos | Mathlib |
| Theorem 5, pigeonhole bound | cubic_lower_bound_ceil | Mathlib |
| Theorem 5, | eventually_lower_bound | Mathlib |
| Theorem 5, | imbalance_le | Mathlib |
lowerConst_two_five, lowerConst_two_le | Mathlib | |
| , | lowerConst_four, lowerConst_le_four | Mathlib |
| rectangles of [11, 16] | Certificates.exists_pub_* | core |
| spec = Latin arrays; non-vacuous | arrayEquiv, nonempty_of_le | Mathlib |
| optimality in Theorem 2 | not formalised | |
| Theorems 4, 6 and 10 | not formalised |
Table 4. Table 4. Formalised statements. Names are relative to the namespace BalancedLatin; theorems about a rectangle are in its sub-namespace LatinRect. “Core”: the proof uses only Lean’s core library and the 74-line specification Defs.lean; “Mathlib”: it also uses Mathlib. The certificates use only the axiom propext; the theorems use the three standard axioms propext, Classical.choice and Quot.sound. No statement uses sorry or native_decide.
Specification. The file Defs.lean contains the whole specification that the certificates rely on. It imports only Lean’s core library, not Mathlib. It uses the point picture of § 3: a rectangle is the function , with indices starting at 0.
structure LatinRect (k n : Nat) where
col : Fin k → Fin n → Fin n -- col i u = column of symbol u in row i
row_inj : ∀ i u v, col i u = col i v → u = v
col_inj : ∀ u i j, col i u = col j u → i = j
def dist (L : LatinRect k n) (u v : Fin n) : Nat := -- d(u, v) = ∑ᵢ |cᵢ(u) − cᵢ(v)|
fsum fun i => absDiff (L.col i u).val (L.col i v).val
def imb3 (L : LatinRect k n) : Nat := -- 3I = ∑ᵤ₍ᵥ |3d(u, v) − k(n + 1)|
fsum fun u => fsum fun v =>
if u < v then ((3 * L.dist u v : Int) - k * (n + 1)).natAbs else 0
Here fsum f is the sum of the list [f 0, ..., f (n-1)], and absDiff a b is , with truncated subtraction on N. We certify the integer , so that the kernel never handles fractions. In Cubic.lean, we define the imbalance over exactly as in § 3, and imbalance_eq_imb3 proves .
Certificates by kernel evaluation. A script copies each rectangle from its data file into Lean, after cross-checking the claimed value with the independent Python checker. For Figure 1 it produces
def rows_k3_n9 : List (List Nat) :=
[[1, 2, 3, 4, 5, 6, 7, 8, 9], [8, 3, 1, 6, 7, 4, 5, 9, 2], [4, 5, 8, 1, 9, 3, 2, 6, 7]]
def rect_k3_n9 : LatinRect 3 9 where
col := colOfRows rows_k3_n9
row_inj := by decide +kernel
col_inj := by decide +kernel
theorem imb3_k3_n9 : rect_k3_n9.imb3 = 168 := by decide +kernel
theorem exists_k3_n9 : ∃ L : LatinRect 3 9, L.imb3 = 168 := ⟨rect_k3_n9, imb3_k3_n9⟩
The tactic decide +kernel is proof by reflection. The proposition has a decision procedure, written in Lean, and the kernel itself reduces that procedure to true while type-checking the proof term. The alternative, native_decide, runs compiled code. It adds the axiom Lean.ofReduceBool, so it trusts the compiler and every implemented_by annotation. Our certificates avoid it, and #print axioms reports only propext.
The soundness of a statement such as exists_k3_n9 does not depend on the script or on how colOfRows reads the data. For any function passed as col, the kernel checks that it is a Latin rectangle with the stated value of . To tie each certificate to its data file, a further theorem faithful_k3_n9 checks that the entry of row in column col i u is the symbol of the file. Lean certifies all 62 rectangles: the 51 of Table 1 and the eleven rectangles with used in Table 3 and Figure 4 and Figure 5. The largest are and , which has 2016 pairs. Elaborating all of them takes about 50 s of CPU time on an Apple M3 laptop. As a negative test, changing the claimed value by one, placing a symbol twice in a column, or repeating a symbol in a row each makes the check fail.
Cubic growth. Cubic.lean (480 lines, 14 s) proves Theorem 5. The main statements read
theorem cubic_lower_bound (L : LatinRect k n) (s M : ℕ) (hs : 0 < s) (hM : n ≤ M * s)
(ht : (k : ℚ) * (s - 1) ≤ target k n) :
(n : ℚ) * (n / (M : ℚ) ^ k - 1) * (target k n - k * (s - 1)) ≤ L.imbalance
theorem eventually_lower_bound (k m : ℕ) (hm : 3 ≤ m) {ε : ℚ} (hε : 0 < ε) :
∀ n in Filter.atTop, ∀ L : LatinRect k n,
(lowerConst k m - ε) * (n : ℚ) ^ 3 ≤ L.imbalance
where target k n is and lowerConst k m is . The first is slightly more general than Theorem 5: it allows any intervals per axis with . Its instance , cubic_lower_bound_ceil, is Theorem 5 word for word. The second states the liminf bound in the eventually form, for each , so we do not have to define as a function of . The proof follows the paper. It reindexes along the row permutations (Fintype.sum_bijective) to show that is the average distance. It then symmetrises the sum over to one over ordered pairs, and uses Mathlib’s sq_sum_le_card_mul_sum_sq for Cauchy–Schwarz.
Is the specification the right one? A formal proof is only as good as its statement. A definition that differs subtly from the intended one would make every certificate meaningless. We guard against this in four ways. (i) Agreement with the literature. Lean certifies the 14 rectangles printed in [11, 16], of sizes to , with the imbalances that those papers report (Certificates.exists_pub_*). This tests the definitions of and against independent data, not against our own Python checker. (ii) Agreement with the textbook definition. arrayEquiv is a bijection between LatinRect k n and arrays (row , column ) whose rows are permutations and whose columns have no repeats. ofArray_col shows that col i u is the column of symbol in row , that is, . (iii) Non-vacuity. nonempty_of_le shows that LatinRect k n is inhabited for every , so the universally quantified theorems are not vacuous. (iv) Agreement with the paper. A test parses Table 1 and Table 3 and the values quoted in the text for , and , and compares them with the Lean statements. It also compares every rectangle printed in Section A, entry by entry, with the rows of its certificate. Changing one of these printed values makes it fail.
What is not formalised. The optimality half of Theorem 2 is the main gap. The branch and bound visits nodes, far more than kernel evaluation can handle. A certificate would need one of two routes. The first is a branch and bound written and proved correct in Lean and then run with native_decide, which moves the trust from our C program to Lean’s compiler. The second is a SAT encoding with an LRAT proof that a verified checker accepts. Either route also has to prove the symmetry reduction of § 6. Theorem 10 needs permutons and the sampling theorem of Hoppen et al. [6], which Mathlib does not have. Theorem 6 needs an asymptotic estimate of for discretised uniform variables. Theorem 9 rests on the theorem of Alon and Pudlák [1]. Theorem 4 is elementary, but we computed the row groups in Figure 3 with SymPy’s Schreier–Sims implementation, and they are not certified.
Discussion
The point picture says that balance is a packing problem in , so moving points is the natural search move. It also gives the right scale. For a fixed number of rows, imbalance is not a small defect that clever search will remove. It is a quantity of order , and its leading constant is the real object of study. The row group adds a cheap check that a rectangle is not built from a group table.
Limitations. The new upper bounds are best-of-runs from at most three runs per instance, and single runs vary by up to a third (§ 5). We did not isolate the effect of the adaptive penalty or rerun earlier local search head-to-head. We also make no runtime comparison with earlier work. The optimality of rests on two uncertified programs that share a branching scheme. In contrast, Lean checks every upper bound and the pigeonhole theorem. Our lower-bound constant is far from the observed values for and is negligible in the benchmark range.
Open problems
Certify Theorem 2, for instance with a DRAT-producing SAT encoding as in [11] or with a branch and bound verified in Lean (§ 10). Also settle to . The sharper bound and the unused column-reversal and row symmetries of § 6 are natural first steps. Our new upper bounds are natural starting incumbents for certified solvers. The mirror pairing seen in several records is a candidate streamliner in the sense of [16].
Close the gap between and . A sharper lower bound might weight each close pair by its shortfall instead of the worst case inside a box. The limit problem is a quadratic minimisation over permutons. One route to a certified lower bound is to discretise it to doubly stochastic matrices and apply a semidefinite relaxation.
Determine the minimising permuton for .
Find the order in of the constants in Theorem 5, between and . Also find how the minimum passes to order for squares.
Show directly that a perfectly balanced rectangle needs , using that its coordinate projections are bijections. This would follow from Kusner’s conjecture for , a long-standing problem in geometry, but it may be easier for these special point sets.
Data and code. Rectangles, the annealing code, the branch and bound, the exact checker, the Lean development and the scripts for every figure are at https://github.com/BrianLi009/Balanced-Latin-Rectangles. The new rectangles are listed in Section A, and all 62 are in the ancillary file anc/rectangles.txt.
The new rectangles
This appendix lists the 33 rectangles that improve Table 1 and the seven rectangles of Table 3. Rows are listed from top to bottom, entry of a row is the symbol in column , and the first row is always the identity. Each heading gives the new imbalance in bold and, in grey, the previous best value of [16] and the relative improvement. As in Figure 1, each symbol has its own colour, so every row shows all colours and no colour repeats within a column. Each rectangle is a file of the repository named by its size: the rectangle, for example, is results/rectangles/k4_n9.txt (the ones are in results/k2_large/). Lean certifies it as Certificates.exists_k4_n9, and Certificates.faithful_k4_n9 ties the certificate to the file (§ 10). A test in the repository checks this list against the certificates entry by entry. All 62 rectangles of the paper, including the matched records and the rectangles with , are in the ancillary file anc/rectangles.txt.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 5 | 1 | 7 | 3 | 9 | 2 | 6 | 4 | 8 |
| 2 | 7 | 8 | 5 | 4 | 3 | 9 | 1 | 6 |
| 3 | 8 | 5 | 6 | 2 | 9 | 1 | 7 | 4 |
Table 5. : 53.3 (56.0, −4.8%)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 9 | 4 | 5 | 2 | 7 | 1 | 8 | 3 | 6 |
| 2 | 6 | 9 | 1 | 8 | 4 | 5 | 7 | 3 |
| 7 | 1 | 4 | 6 | 9 | 3 | 2 | 5 | 8 |
| 4 | 8 | 2 | 7 | 3 | 9 | 6 | 1 | 5 |
Table 6. : 48.6 (52.6, −7.6%)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 3 | 8 | 4 | 1 | 7 | 2 | 9 | 5 | 6 |
| 7 | 4 | 5 | 9 | 3 | 1 | 2 | 6 | 8 |
| 4 | 9 | 1 | 8 | 6 | 5 | 3 | 7 | 2 |
| 9 | 3 | 6 | 2 | 4 | 7 | 8 | 1 | 5 |
| 6 | 1 | 7 | 3 | 9 | 8 | 5 | 2 | 4 |
Table 7. : 40.0 (48.0, −16.7%)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 6 | 1 | 9 | 3 | 4 | 8 | 5 | 2 | 7 |
| 2 | 9 | 4 | 8 | 6 | 5 | 3 | 7 | 1 |
| 9 | 3 | 5 | 7 | 1 | 2 | 4 | 6 | 8 |
| 8 | 5 | 1 | 9 | 2 | 7 | 6 | 3 | 4 |
| 3 | 8 | 2 | 6 | 7 | 9 | 1 | 4 | 5 |
| 7 | 4 | 8 | 1 | 9 | 3 | 2 | 5 | 6 |
Table 8. : 43.3 (51.3, −15.6%)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 8 | 4 | 2 | 9 | 7 | 3 | 5 | 1 | 6 |
| 4 | 5 | 6 | 2 | 9 | 7 | 1 | 3 | 8 |
| 9 | 3 | 7 | 5 | 1 | 4 | 8 | 6 | 2 |
| 7 | 6 | 4 | 3 | 8 | 1 | 2 | 9 | 5 |
| 6 | 9 | 1 | 8 | 4 | 5 | 3 | 2 | 7 |
| 5 | 7 | 8 | 1 | 6 | 2 | 9 | 4 | 3 |
| 3 | 8 | 5 | 6 | 2 | 9 | 4 | 7 | 1 |
Table 9. : 42.6 (53.3, −20.0%)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 8 | 3 | 6 | 9 | 2 | 7 | 5 | 4 | 10 | 1 |
| 3 | 7 | 10 | 5 | 1 | 8 | 9 | 2 | 6 | 4 |
| 5 | 8 | 4 | 3 | 9 | 10 | 2 | 1 | 7 | 6 |
| 9 | 5 | 1 | 6 | 3 | 4 | 10 | 7 | 8 | 2 |
| 7 | 4 | 9 | 1 | 8 | 3 | 6 | 10 | 2 | 5 |
Table 10. : 60.0 (70.0, −14.3%)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 6 | 4 | 7 | 9 | 1 | 2 | 10 | 3 | 8 | 5 |
| 3 | 10 | 4 | 1 | 7 | 8 | 9 | 5 | 6 | 2 |
| 8 | 1 | 9 | 6 | 3 | 5 | 4 | 10 | 2 | 7 |
| 5 | 7 | 1 | 3 | 9 | 10 | 6 | 2 | 4 | 8 |
| 9 | 3 | 2 | 7 | 8 | 4 | 5 | 6 | 10 | 1 |
| 4 | 9 | 5 | 10 | 2 | 1 | 8 | 7 | 3 | 6 |
Table 11. : 58.0 (72.0, −19.4%)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 8 | 6 | 4 | 2 | 9 | 1 | 10 | 3 | 5 | 7 |
| 7 | 1 | 10 | 6 | 8 | 3 | 4 | 9 | 2 | 5 |
| 2 | 7 | 6 | 9 | 4 | 10 | 3 | 5 | 8 | 1 |
| 10 | 8 | 2 | 5 | 3 | 7 | 6 | 4 | 1 | 9 |
| 3 | 9 | 8 | 7 | 6 | 5 | 1 | 2 | 10 | 4 |
| 6 | 5 | 9 | 1 | 10 | 8 | 2 | 7 | 4 | 3 |
| 5 | 4 | 7 | 8 | 1 | 2 | 9 | 10 | 3 | 6 |
Table 12. : 58.6 (82.6, −29.0%)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 7 | 1 | 10 | 9 | 3 | 4 | 8 | 5 | 6 | 2 |
| 9 | 6 | 2 | 7 | 1 | 5 | 3 | 10 | 4 | 8 |
| 6 | 8 | 1 | 5 | 10 | 3 | 9 | 7 | 2 | 4 |
| 10 | 3 | 6 | 2 | 7 | 8 | 4 | 1 | 5 | 9 |
| 4 | 5 | 7 | 10 | 6 | 9 | 2 | 3 | 8 | 1 |
| 3 | 9 | 4 | 6 | 8 | 7 | 1 | 2 | 10 | 5 |
| 2 | 10 | 9 | 8 | 4 | 1 | 5 | 6 | 7 | 3 |
| 8 | 7 | 5 | 3 | 9 | 2 | 10 | 4 | 1 | 6 |
Table 9 × 10. 9 × 10: 64.0 (70.0, −8.6%)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| 4 | 3 | 10 | 11 | 6 | 8 | 5 | 1 | 2 | 9 | 7 |
| 9 | 6 | 4 | 2 | 11 | 1 | 10 | 7 | 8 | 3 | 5 |
| 8 | 4 | 5 | 9 | 1 | 10 | 2 | 11 | 3 | 7 | 6 |
Table 4 × 11. 4 × 11: 104.0 (112.0, −7.1%)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| 8 | 3 | 2 | 11 | 7 | 4 | 6 | 10 | 1 | 5 | 9 |
| 3 | 10 | 7 | 5 | 1 | 11 | 8 | 6 | 2 | 9 | 4 |
| 7 | 1 | 8 | 9 | 2 | 10 | 3 | 5 | 4 | 11 | 6 |
| 10 | 8 | 4 | 1 | 6 | 3 | 9 | 11 | 7 | 2 | 5 |
Table 5 × 11. 5 × 11: 94.0 (116.0, −19.0%)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| 11 | 4 | 6 | 1 | 7 | 8 | 10 | 3 | 2 | 5 | 9 |
| 8 | 3 | 1 | 11 | 9 | 5 | 6 | 4 | 10 | 7 | 2 |
| 3 | 6 | 7 | 9 | 1 | 11 | 2 | 10 | 4 | 8 | 5 |
| 4 | 7 | 9 | 8 | 2 | 3 | 11 | 5 | 6 | 1 | 10 |
| 7 | 5 | 11 | 3 | 10 | 4 | 1 | 9 | 8 | 2 | 6 |
Table 6 × 11. 6 × 11: 88.0 (108.0, −18.5%)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| 3 | 5 | 10 | 11 | 1 | 4 | 6 | 7 | 2 | 9 | 8 |
| 6 | 11 | 4 | 3 | 9 | 8 | 1 | 5 | 10 | 2 | 7 |
| 9 | 1 | 7 | 6 | 10 | 3 | 5 | 4 | 8 | 11 | 2 |
| 5 | 6 | 9 | 2 | 11 | 7 | 3 | 10 | 1 | 8 | 4 |
| 8 | 3 | 6 | 10 | 2 | 1 | 11 | 9 | 7 | 4 | 5 |
| 10 | 4 | 2 | 9 | 6 | 5 | 8 | 1 | 11 | 7 | 3 |
Table 7 × 11. 7 × 11: 84.0 (118.0, −28.8%)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| 2 | 8 | 11 | 5 | 6 | 7 | 4 | 10 | 1 | 9 | 3 |
| 8 | 4 | 7 | 6 | 3 | 9 | 5 | 2 | 11 | 1 | 10 |
| 6 | 9 | 2 | 10 | 7 | 1 | 8 | 3 | 5 | 11 | 4 |
| 10 | 7 | 5 | 3 | 2 | 8 | 9 | 11 | 4 | 6 | 1 |
| 3 | 11 | 6 | 7 | 1 | 2 | 10 | 4 | 8 | 5 | 9 |
| 7 | 5 | 1 | 9 | 11 | 4 | 2 | 6 | 10 | 3 | 8 |
| 5 | 6 | 10 | 1 | 8 | 3 | 11 | 9 | 7 | 4 | 2 |
Table 8 × 11. 8 × 11: 78.0 (114.0, −31.6%)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| 7 | 3 | 6 | 10 | 8 | 1 | 9 | 5 | 4 | 11 | 2 |
| 6 | 8 | 2 | 5 | 7 | 9 | 11 | 10 | 3 | 4 | 1 |
| 3 | 11 | 7 | 2 | 9 | 8 | 4 | 1 | 10 | 6 | 5 |
| 8 | 4 | 5 | 11 | 3 | 10 | 6 | 2 | 1 | 9 | 7 |
| 5 | 7 | 10 | 1 | 11 | 2 | 8 | 4 | 6 | 3 | 9 |
| 11 | 6 | 1 | 9 | 4 | 7 | 5 | 3 | 8 | 2 | 10 |
| 9 | 5 | 8 | 3 | 1 | 11 | 10 | 6 | 2 | 7 | 4 |
| 4 | 10 | 9 | 6 | 2 | 5 | 3 | 11 | 7 | 1 | 8 |
Table 9 × 11. 9 × 11: 84.0 (120.0, −30.0%)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| 5 | 7 | 1 | 2 | 10 | 11 | 9 | 4 | 3 | 6 | 8 |
| 3 | 8 | 5 | 10 | 11 | 2 | 4 | 6 | 7 | 9 | 1 |
| 8 | 1 | 7 | 11 | 9 | 3 | 5 | 2 | 6 | 4 | 10 |
| 7 | 6 | 11 | 3 | 2 | 10 | 1 | 9 | 5 | 8 | 4 |
| 6 | 10 | 8 | 1 | 4 | 5 | 11 | 7 | 2 | 3 | 9 |
| 11 | 5 | 4 | 9 | 6 | 1 | 3 | 10 | 8 | 2 | 7 |
| 10 | 4 | 9 | 7 | 3 | 8 | 2 | 5 | 1 | 11 | 6 |
| 2 | 9 | 6 | 5 | 8 | 7 | 10 | 11 | 4 | 1 | 3 |
| 4 | 11 | 2 | 8 | 1 | 9 | 6 | 3 | 10 | 7 | 5 |
Table 10 × 11. 10 × 11: 100.0 (110.0, −9.1%)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 5 | 10 | 9 | 8 | 2 | 1 | 11 | 12 | 6 | 3 | 4 | 7 |
| 6 | 9 | 10 | 7 | 1 | 2 | 12 | 11 | 5 | 4 | 3 | 8 |
Table 3 × 12. 3 × 12: 152.0 (154.0, −1.3%)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 4 | 9 | 11 | 1 | 6 | 5 | 8 | 7 | 2 | 12 | 3 | 10 |
| 6 | 3 | 5 | 9 | 12 | 10 | 4 | 1 | 8 | 11 | 2 | 7 |
| 5 | 11 | 6 | 2 | 10 | 12 | 1 | 4 | 7 | 3 | 9 | 8 |
Table 4 × 12. 4 × 12: 149.3 (154.6, −3.4%)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 11 | 8 | 6 | 3 | 1 | 9 | 4 | 12 | 10 | 7 | 5 | 2 |
| 9 | 6 | 5 | 12 | 3 | 11 | 2 | 10 | 1 | 8 | 7 | 4 |
| 3 | 7 | 11 | 5 | 4 | 12 | 1 | 9 | 8 | 2 | 6 | 10 |
| 8 | 3 | 12 | 2 | 9 | 7 | 6 | 4 | 11 | 1 | 10 | 5 |
Table 5 × 12. 5 × 12: 140.0 (145.3, −3.7%)
: 121.3 (164.0, −26.0%)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 3 | 11 | 7 | 8 | 2 | 4 | 9 | 10 | 6 | 12 | 1 | 5 |
| 8 | 1 | 9 | 2 | 7 | 12 | 3 | 5 | 10 | 4 | 6 | 11 |
| 9 | 3 | 10 | 5 | 8 | 11 | 1 | 6 | 2 | 7 | 12 | 4 |
| 2 | 9 | 6 | 11 | 12 | 7 | 5 | 3 | 1 | 8 | 4 | 10 |
| 10 | 7 | 1 | 6 | 9 | 3 | 12 | 4 | 8 | 11 | 5 | 2 |
| 7 | 5 | 4 | 9 | 11 | 1 | 10 | 2 | 12 | 3 | 8 | 6 |
Table 13.
: 116.6 (148.0, −21.2%)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 7 | 3 | 9 | 11 | 1 | 12 | 6 | 5 | 4 | 2 | 10 | 8 |
| 3 | 5 | 10 | 6 | 12 | 2 | 9 | 7 | 11 | 4 | 8 | 1 |
| 10 | 1 | 6 | 9 | 7 | 5 | 4 | 12 | 2 | 8 | 3 | 11 |
| 8 | 6 | 12 | 3 | 4 | 9 | 1 | 2 | 10 | 11 | 5 | 7 |
| 9 | 4 | 5 | 8 | 10 | 3 | 11 | 1 | 6 | 12 | 7 | 2 |
| 6 | 11 | 4 | 7 | 2 | 10 | 3 | 9 | 8 | 1 | 12 | 5 |
| 4 | 12 | 7 | 10 | 3 | 1 | 8 | 11 | 5 | 6 | 2 | 9 |
Table 14.
: 106.0 (154.0, −31.2%)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 9 | 4 | 12 | 5 | 1 | 7 | 8 | 10 | 3 | 2 | 6 | 11 |
| 2 | 12 | 10 | 1 | 7 | 5 | 6 | 11 | 8 | 9 | 4 | 3 |
| 7 | 9 | 2 | 8 | 3 | 12 | 5 | 6 | 11 | 4 | 10 | 1 |
| 11 | 1 | 7 | 3 | 8 | 4 | 10 | 12 | 5 | 6 | 2 | 9 |
| 8 | 10 | 5 | 2 | 4 | 11 | 9 | 1 | 7 | 12 | 3 | 6 |
| 10 | 7 | 4 | 6 | 9 | 2 | 11 | 3 | 12 | 1 | 5 | 8 |
| 6 | 8 | 1 | 9 | 10 | 3 | 12 | 4 | 2 | 11 | 7 | 5 |
| 5 | 3 | 9 | 10 | 11 | 1 | 2 | 7 | 6 | 8 | 12 | 4 |
Table 15.
: 124.0 (174.6, −29.0%)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 12 | 1 | 6 | 8 | 2 | 10 | 9 | 11 | 5 | 3 | 7 | 4 |
| 4 | 8 | 12 | 3 | 9 | 1 | 5 | 10 | 11 | 2 | 6 | 7 |
| 8 | 6 | 7 | 9 | 3 | 5 | 10 | 2 | 12 | 11 | 4 | 1 |
| 5 | 11 | 9 | 1 | 6 | 7 | 12 | 3 | 4 | 8 | 10 | 2 |
| 9 | 7 | 4 | 2 | 10 | 11 | 8 | 6 | 1 | 12 | 3 | 5 |
| 6 | 4 | 5 | 10 | 12 | 9 | 2 | 7 | 3 | 1 | 8 | 11 |
| 10 | 5 | 8 | 7 | 1 | 4 | 11 | 12 | 2 | 6 | 9 | 3 |
| 7 | 12 | 2 | 5 | 11 | 8 | 3 | 4 | 6 | 9 | 1 | 10 |
| 3 | 10 | 11 | 6 | 7 | 12 | 4 | 1 | 8 | 5 | 2 | 9 |
Table 16.
: 136.6 (147.3, −7.2%)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 3 | 7 | 4 | 10 | 9 | 12 | 1 | 6 | 5 | 11 | 2 | 8 |
| 2 | 4 | 12 | 11 | 6 | 9 | 5 | 10 | 3 | 8 | 1 | 7 |
| 11 | 10 | 5 | 1 | 4 | 8 | 6 | 7 | 12 | 3 | 9 | 2 |
| 8 | 12 | 10 | 3 | 1 | 5 | 4 | 11 | 2 | 7 | 6 | 9 |
| 9 | 3 | 11 | 5 | 7 | 4 | 8 | 12 | 6 | 2 | 10 | 1 |
| 7 | 11 | 1 | 2 | 12 | 10 | 9 | 3 | 8 | 4 | 5 | 6 |
| 5 | 9 | 2 | 8 | 10 | 7 | 12 | 4 | 1 | 6 | 3 | 11 |
| 6 | 1 | 9 | 12 | 8 | 11 | 3 | 2 | 7 | 5 | 4 | 10 |
| 12 | 5 | 7 | 6 | 3 | 2 | 10 | 1 | 11 | 9 | 8 | 4 |
| 10 | 6 | 8 | 7 | 11 | 3 | 2 | 9 | 4 | 1 | 12 | 5 |
Table 17.
: 201.3 (211.3, −4.7%)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| 7 | 4 | 11 | 5 | 9 | 1 | 12 | 13 | 3 | 2 | 8 | 10 | 6 |
| 3 | 11 | 10 | 1 | 7 | 8 | 5 | 6 | 13 | 12 | 4 | 2 | 9 |
| 5 | 10 | 2 | 7 | 13 | 12 | 3 | 9 | 1 | 11 | 6 | 4 | 8 |
Table 18.
: 191.3 (210.6, −9.2%)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| 2 | 9 | 11 | 1 | 8 | 12 | 3 | 7 | 6 | 5 | 13 | 4 | 10 |
| 6 | 11 | 7 | 5 | 12 | 2 | 1 | 13 | 10 | 3 | 4 | 9 | 8 |
| 7 | 3 | 6 | 9 | 13 | 11 | 10 | 1 | 2 | 4 | 12 | 8 | 5 |
| 12 | 4 | 9 | 6 | 7 | 1 | 2 | 10 | 13 | 8 | 5 | 11 | 3 |
Table 19.
: 166.0 (204.0, −18.6%)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| 11 | 1 | 7 | 6 | 10 | 12 | 2 | 4 | 13 | 8 | 5 | 3 | 9 |
| 8 | 10 | 1 | 9 | 2 | 11 | 5 | 12 | 3 | 7 | 4 | 13 | 6 |
| 10 | 3 | 6 | 5 | 12 | 1 | 9 | 13 | 7 | 2 | 8 | 4 | 11 |
| 2 | 6 | 9 | 11 | 13 | 10 | 4 | 5 | 1 | 3 | 7 | 8 | 12 |
| 7 | 5 | 10 | 2 | 3 | 13 | 8 | 11 | 6 | 1 | 12 | 9 | 4 |
Table 20.
: 164.0 (203.3, −19.3%)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| 3 | 8 | 6 | 10 | 1 | 12 | 11 | 9 | 2 | 13 | 4 | 5 | 7 |
| 7 | 1 | 11 | 6 | 13 | 9 | 3 | 4 | 10 | 5 | 8 | 2 | 12 |
| 13 | 6 | 8 | 2 | 11 | 4 | 10 | 1 | 7 | 12 | 5 | 9 | 3 |
| 5 | 10 | 1 | 13 | 8 | 2 | 9 | 11 | 3 | 7 | 12 | 4 | 6 |
| 11 | 4 | 5 | 8 | 3 | 13 | 1 | 7 | 12 | 2 | 10 | 6 | 9 |
| 8 | 9 | 4 | 1 | 12 | 5 | 6 | 13 | 11 | 3 | 2 | 7 | 10 |
Table 21.
: 160.0 (220.6, −27.5%)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| 13 | 1 | 5 | 10 | 6 | 4 | 3 | 9 | 11 | 8 | 7 | 2 | 12 |
| 10 | 4 | 11 | 6 | 7 | 2 | 12 | 13 | 1 | 5 | 8 | 9 | 3 |
| 9 | 10 | 1 | 12 | 2 | 5 | 8 | 6 | 7 | 4 | 13 | 3 | 11 |
| 11 | 5 | 8 | 2 | 10 | 3 | 13 | 4 | 12 | 9 | 6 | 7 | 1 |
| 4 | 9 | 7 | 5 | 11 | 13 | 2 | 10 | 3 | 1 | 12 | 8 | 6 |
| 2 | 6 | 13 | 9 | 8 | 11 | 4 | 1 | 5 | 12 | 3 | 10 | 7 |
| 5 | 12 | 6 | 11 | 3 | 9 | 10 | 2 | 13 | 7 | 1 | 4 | 8 |
Table 22.
: 152.0 (214.0, −29.0%)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| 3 | 6 | 11 | 13 | 8 | 4 | 9 | 7 | 1 | 12 | 2 | 5 | 10 |
| 8 | 13 | 5 | 7 | 12 | 2 | 3 | 11 | 4 | 6 | 10 | 9 | 1 |
| 9 | 1 | 8 | 12 | 3 | 11 | 2 | 5 | 10 | 6 | 13 | 7 | 4 |
| 5 | 11 | 1 | 3 | 7 | 10 | 4 | 9 | 13 | 12 | 8 | 2 | 6 |
| 13 | 3 | 10 | 2 | 9 | 5 | 8 | 4 | 7 | 11 | 12 | 6 | 1 |
| 10 | 8 | 7 | 1 | 6 | 3 | 12 | 2 | 11 | 13 | 9 | 5 | 4 |
| 2 | 7 | 9 | 6 | 11 | 13 | 1 | 10 | 5 | 8 | 3 | 4 | 12 |
| 11 | 4 | 2 | 8 | 10 | 1 | 13 | 12 | 6 | 5 | 9 | 3 | 7 |
Table 23.
| 10 × 13: 154.6 (240.6, −35.7%) | ||||||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| 7 | 3 | 12 | 9 | 8 | 10 | 11 | 1 | 2 | 5 | 6 | 13 | 4 |
| 8 | 11 | 5 | 13 | 3 | 7 | 1 | 4 | 10 | 2 | 12 | 9 | 6 |
| 4 | 12 | 2 | 11 | 7 | 5 | 9 | 6 | 8 | 13 | 1 | 3 | 10 |
| 12 | 1 | 8 | 5 | 4 | 9 | 6 | 13 | 11 | 3 | 10 | 2 | 7 |
| 6 | 7 | 4 | 8 | 13 | 12 | 3 | 2 | 1 | 11 | 5 | 10 | 9 |
| 2 | 5 | 13 | 12 | 10 | 3 | 8 | 9 | 6 | 7 | 4 | 11 | 1 |
| 10 | 8 | 6 | 2 | 1 | 11 | 12 | 7 | 13 | 4 | 9 | 5 | 3 |
| 9 | 13 | 1 | 7 | 2 | 8 | 10 | 5 | 4 | 12 | 3 | 6 | 11 |
| 5 | 10 | 7 | 6 | 12 | 1 | 13 | 11 | 3 | 9 | 2 | 4 | 8 |
Table 24.
| 11 × 13: 168.0 (224.0, −25.0%) | ||||||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| 12 | 5 | 10 | 6 | 7 | 2 | 1 | 3 | 13 | 11 | 9 | 4 | 8 |
| 3 | 11 | 12 | 5 | 8 | 10 | 2 | 4 | 1 | 9 | 7 | 13 | 6 |
| 10 | 6 | 4 | 3 | 13 | 11 | 8 | 2 | 12 | 7 | 1 | 5 | 9 |
| 4 | 12 | 9 | 7 | 2 | 3 | 11 | 6 | 10 | 1 | 13 | 8 | 5 |
| 11 | 9 | 6 | 13 | 1 | 5 | 3 | 12 | 4 | 8 | 2 | 10 | 7 |
| 13 | 3 | 7 | 8 | 9 | 1 | 10 | 5 | 11 | 12 | 4 | 6 | 2 |
| 6 | 8 | 2 | 9 | 3 | 12 | 13 | 7 | 5 | 4 | 10 | 11 | 1 |
| 8 | 7 | 11 | 1 | 6 | 4 | 12 | 13 | 2 | 3 | 5 | 9 | 10 |
| 5 | 4 | 13 | 2 | 11 | 7 | 9 | 10 | 8 | 6 | 12 | 1 | 3 |
| 2 | 13 | 1 | 12 | 10 | 8 | 4 | 9 | 6 | 5 | 3 | 7 | 11 |
Table 25.
| 12 × 13: 166.0 (274.0, −39.4%) | ||||||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| 12 | 8 | 7 | 2 | 10 | 1 | 6 | 13 | 3 | 9 | 4 | 5 | 11 |
| 4 | 12 | 10 | 3 | 13 | 2 | 11 | 5 | 8 | 6 | 1 | 7 | 9 |
| 9 | 11 | 2 | 7 | 12 | 4 | 5 | 3 | 13 | 1 | 6 | 8 | 10 |
| 2 | 13 | 9 | 8 | 6 | 5 | 10 | 12 | 4 | 7 | 3 | 11 | 1 |
| 3 | 9 | 1 | 13 | 8 | 12 | 4 | 7 | 10 | 11 | 5 | 6 | 2 |
| 8 | 7 | 13 | 5 | 11 | 3 | 2 | 10 | 1 | 4 | 12 | 9 | 6 |
| 11 | 1 | 12 | 6 | 2 | 13 | 8 | 4 | 5 | 3 | 9 | 10 | 7 |
| 5 | 10 | 4 | 1 | 9 | 8 | 12 | 11 | 6 | 13 | 7 | 2 | 3 |
| 13 | 4 | 6 | 10 | 7 | 11 | 1 | 9 | 2 | 5 | 8 | 3 | 12 |
| 7 | 6 | 5 | 12 | 3 | 9 | 13 | 1 | 11 | 2 | 10 | 4 | 8 |
| 6 | 3 | 8 | 11 | 4 | 10 | 9 | 2 | 7 | 12 | 13 | 1 | 5 |
Table 26.
,
| 2 × 14: 268.0 | |||||||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 7 | 8 | 2 | 11 | 1 | 12 | 13 | 4 | 5 | 6 | 14 | 3 | 9 | 10 |
Table 27.
| 2 × 15: 344.6 | ||||||||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| 2 | 12 | 10 | 8 | 6 | 5 | 15 | 4 | 14 | 3 | 13 | 1 | 11 | 9 | 7 |
Table 28.
| 2 × 16: 422.0 | |||||||||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| 9 | 11 | 12 | 2 | 3 | 15 | 5 | 16 | 6 | 7 | 8 | 10 | 14 | 1 | 13 | 4 |
Table 29.
| 2 × 17: 498.0 | ||||||||||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
| 13 | 15 | 4 | 17 | 2 | 7 | 8 | 9 | 10 | 11 | 12 | 1 | 14 | 3 | 16 | 5 | 6 |
Table 30.
| 2 × 18: 610.6 | |||||||||||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
| 6 | 4 | 16 | 2 | 14 | 1 | 12 | 11 | 10 | 9 | 8 | 7 | 18 | 5 | 17 | 3 | 15 | 13 |
Table 31.
| 2 × 19: 722.6 | ||||||||||||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
| 6 | 5 | 17 | 16 | 2 | 1 | 13 | 12 | 11 | 9 | 10 | 8 | 7 | 19 | 18 | 4 | 3 | 15 | 14 |
Table 32.
| 2 × 20: 832.0 | |||||||||||||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
| 4 | 3 | 16 | 1 | 14 | 19 | 12 | 11 | 10 | 9 | 8 | 7 | 20 | 5 | 18 | 17 | 2 | 15 | 6 | 13 |
Table 33.
References
- [1]Noga Alon and Pavel Pudlák. Equilateral sets in lⁿₚ. Geometric and Functional Analysis, 13(3):467–482, 2003. doi: 10.1007/S00039-003-0418-7.
- [2]Leonardo de Moura and Sebastian Ullrich. The Lean 4 theorem prover and programming language. In Automated Deduction – CADE 28, volume 12699 of Lecture Notes in Computer Science, pages 625–635. Springer, 2021. doi: 10.1007/978-3-030-79876-5_37.
- [3]Mateo Díaz, Ronan Le Bras, and Carla P. Gomes. In search of balance: The challenge of generating balanced Latin rectangles. In Integration of AI and OR Techniques in Constraint Programming (CPAIOR 2017), volume 10335 of Lecture Notes in Computer Science, pages 68–76. Springer, 2017. doi: 10.1007/978-3-319-59776-8_6.DOI
- [4]Fred Glover and Jin-Kao Hao. The case for strategic oscillation. Annals of Operations Research, 183(1):163–173, 2011. doi: 10.1007/s10479-009-0597-1.
- [5]Carla P. Gomes and Meinolf Sellmann. Streamlined constraint reasoning. In Principles and Practice of Constraint Programming (CP 2004), volume 3258 of Lecture Notes in Computer Science, pages 274–289. Springer, 2004. doi: 10.1007/978-3-540-30201-8_22.DOI
- [6]Carlos Hoppen, Yoshiharu Kohayakawa, Carlos Gustavo Moreira, Balázs Ráth, and Rudini Menezes Sampaio. Limits of permutation sequences. Journal of Combinatorial Theory, Series B, 103(1):93–113, 2013. doi: 10.1016/j.jctb.2012.09.003.DOI
- [7]Scott Kirkpatrick, C. Daniel Gelatt, and Mario P. Vecchi. Optimization by simulated annealing. Science, 220(4598):671–680, 1983. doi: 10.1126/science.220.4598.671.DOI
- [8]Jack Koolen, Monique Laurent, and Alexander Schrijver. Equilateral dimension of the rectilinear space. Designs, Codes and Cryptography, 21:149–164, 2000. doi: 10.1023/A:1008391712305.DOI
- [9]Ronan Le Bras, Carla P. Gomes, and Bart Selman. From streamlined combinatorial search to efficient constructive procedures. In Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, pages 499–506, 2012. doi: 10.1609/aaai.v26i1.8147.
- [10]Renee Mirka, Laura Greenstreet, Marc Grimson, and Carla P. Gomes. A new approach to finding 2 × n partially spatially balanced Latin rectangles (short paper). In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023), volume 280 of LIPIcs, pages 47:1–47:11. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi: 10.4230/LIPIcs.CP.2023.47.DOI
- [11]Vaidyanathan Peruvemba Ramaswamy and Stefan Szeider. Proven optimally-balanced Latin rectangles with SAT (short paper). In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023), volume 280 of LIPIcs, pages 48:1–48:10. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi: 10.4230/LIPIcs.CP.2023.48.DOI
- [12]Konrad J. Swanepoel. Equilateral sets in finite-dimensional normed spaces, 2004. arXiv:math/0406264.DOI
- [13]The mathlib Community. The Lean mathematical library. In Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs (CPP 2020), pages 367–381. ACM, 2020. doi: 10.1145/3372885.3373824.DOI
- [14]H. M. van Es and C. L. van Es. Spatial nature of randomization and its effect on the outcome of field experiments. Agronomy Journal, 85(2):420–428, 1993. doi: 10.2134/agronj1993.00021962008500020046x.DOI
- [15]Florentina Voboril and Stefan Szeider. Improving constraint models with LLM agents, 2026. arXiv:2608.08127.arxiv.org/abs/2608.08127
- [16]Florentina Voboril, Vaidyanathan Peruvemba Ramaswamy, and Stefan Szeider. Balancing Latin rectangles with LLM-generated streamliners. In 31st International Conference on Principles and Practice of Constraint Programming (CP 2025), volume 340 of LIPIcs, pages 36:1–36:17. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. doi: 10.4230/LIPIcs.CP.2025.36.DOI
- [17]Hai Xia, Carla P. Gomes, Bart Selman, and Stefan Szeider. Agentic neurosymbolic collaboration for mathematical discovery: A case study in combinatorial design, 2026. arXiv:2603.08322.arxiv.org/abs/2603.08322
- [18]Zhenxuan Xie, Zhipeng Lü, Zhouxing Su, Chu-Min Li, Junwen Ding, and Yuxuan Wang. A swap relaxation-based local search for the Latin square completion problem. In Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-24), pages 7047–7055, 2024. doi: 10.24963/ijcai.2024/779.DOI
- [19]Cheng Zhang and Jianpeng Ma. Counting solutions for the N-queens and Latin square problems by efficient Monte Carlo simulations, 2008. arXiv:0808.4003.DOI




