In this study, we suggest an algorithm for computing minimal and maximal numbers of transversals of diagonal Latin squares. According to this algorithm, we generate all diagonal Latin squares of a particular order, and for each square construct all its transversals and diagonal transversals. With the help of this algorithm, we computed minimal and maximal numbers of transversals for diagonal Latin squares of order at most 7 on a personal computer. The experiment for diagonal Latin squares of order 8 was performed in a volunteer computing project. We also give the estimation of the runtime required to solve the corresponding problem for diagonal Latin squares of order 9.
Latin squares represent a well studied combinatorial design [CD06]. They are used in various practical areas, such as cryptography, error correcting codes, etc. Also Latin squares are often used as a basis for mathematical puzzles, such as Sudoku and Magic squares. There are a lot of open problems regarding Latin squares. One class of such problems consists of enumerating problems – to enumerate all combinatorial objects (which deals with Latin squares) of the particular kind. This paper is focused on one problem from the mentioned class. In particular, we develop an algorithm for enumerating transversals of diagonal Latin squares of small order.
Let us give a brief outline of the paper. In Section 2 we describe some preliminaries on diagonal Latin squares and their transversals. In Section 3 we propose an algorithm for enumerating the number of transversals of diagonal Latin squares. In Section 4 we describe the results on enumeration of the number of transversals of diagonal Latin squares of order at most 8. In the rest of the paper we discuss related work and draw conclusions. 2
A Latin square (LS) of order N is a square table A = ||aij ||, i, j = 1, . . . , N , filled with elements aij from some set U , |U | = N (without the loss of generality, let us below assume that U = {0, 1, 2, . . . , N − 1}). By definition, in each row and each column of a Latin square every element from U appears exactly once: ∀i, j, k = 1, N , j 6= k : (aij 6= aik) ∧ (aji 6= aki).
For Diagonal Latin squares (DLS) which form a special case of LS, the definition is extended by two more conditions on the elements on Latin square main diagonal and main antidiagonal:
∀i, j = 1, N , i 6= j : (aii 6= ajj ) ∧ (ai,N−i+1 6= aj,N−j+1).
A diagonal Latin square is called normalized if the elements of its first row are in ascending order. It is easy to show that any DLS can be normalized by means of a bijective mapping (transposition) of elements from U . It follows from this fact that the corresponding set of diagonal Latin squares forms an equivalence class containing N ! members). For a number of problems (enumeration of LS and DLS [BR75, MR95, MW05, VZZ+16, VKZ17], finding couples and triples of (partially) orthogonal LS and DLS [ZVZM16, ZKS16, ZZKV16]) the squares within one equivalence class do not differ, since they all possess the same properties (they have or do not have an orthogonal mate, have the same number of transversals, etc.). This fact makes it possible to significantly reduce the runtime of any related computational experiment.
A set of N entries, one selected from each row and each column of a Latin square of order N such that no two entries contain the same symbol, is called a transversal. In other words, a transversal T of a Latin square A = ||aij || is a set of elements T = {t1, t2, . . . , tN } = {ai1,j1 , ai2,j2 , . . . , aiN ,jN }, in which all indices are different
We call a transversal T (d) diagonal if it contains exactly one element from main diagonal of a Latin square and exactly one element from its main antidiagonal (in the case of LS of odd order these elements can overlap as in the case of example at Figure 2):
∀k, l = 1, N , ∀m, n = 1, N , m 6= k, n 6= l : → (ik = jk) ∧ (il + jl = N + 1) ∧ (im = jm) ∧ (in + jn = N + 1).
A diagonal transversal is always a transveral of a general kind. An example of a Latin square and a set of its diagonal transversals if shown at Figure 2. and also all elements are different ∀k, l = 1, N , k 6= l : (ik 6= il) ∧ (jk 6= jl)
∀k, l = 1, N , k 6= l : aik,jk 6= ail,jl .
Vectors [i1, i2, . . . , iN ], [j1, j2, . . . , jN ] and [ai1,j1 , ai2,j2 , . . . , aiN ,jN ] form transpositions of elements from U . An example of a Latin square and the set of its transversals is shown in Figure 1. It is easy to see that both diagonals are transversals (T1 = {a11, a22, a33, a44, a55} and T2 = {a15, a24, a33, a42, a51}, and the third transversal T3 = {a12, a21, a33, a45, a54} is a diagonal one. (1) (2) (3) (4) (5)
In the example presented at Figure 1 all transversals are not orthogonal because they contain one common element a33. At the same time all diagonal transversals at Figure 2 are pairwise orthogonal.
The transverals are very useful when one needs to find systems of mutually orthogonal Latin squares or diagonal Latin squares (to which we refer below as systems of MOLS and MODLS, respectively). Two Latin squares A = ||aij || and B = ||bij || are called orthogonal if all ordered pairs [aij , bij ] are distinct. If this property is not satisfied for some of the pairs, then the corresponding Latin squares are said to be partially orthogonal, and the number of unique pairs (that do not repeat) is referred to as orthogonality characteristics. One of the most widely known currently unsolved problems in this area is to answer the question if there exists a triple of mutually orthogonal Latin squares of order 10. It is also unknown if there exists a triple of mutually orthogonal diagonal Latin squares of order 10. The best known result regarding the latter problem is the triple of squares A, B, C, where pairs A, B and A, C are orthogonal, and a pair B, C is partially orthogonal with characteristics of 74 [ZZKV16].
It is possible to construct pairs and triples of MODLS using brute force search combined with branch and bound method [LD60], or using SAT approach [ZKS16]. However, if one decides to employ transversals, it is possible to achieve much better performance compared to aforementioned approaches. In particular, it is known, that a Latin square A of order N has an orthogonal mate B if and only if A has N mutually orthogonal transversals (for diagonal Latin squares – N mutually orthogonal diagonal transversals). Having the corresponding set of N transversals it is easy to construct a square B: the elements corresponding to transversal Ti in square A are assigned with value i − 1 in square B (here we enumerate transversals starting from 1 and the values of Latin square elements starting from 0). At Figure 3 we show the steps leading to construction of an orthogonal mate for the diagonal Latin square from Figure 2. 3
From the constraint on the uniqueness of pairs of indices within a transversal (3) it is easy to construct the upper bound for their number, that is equal to the number N ! of transpositions of elements from U . The process of constructing transversals is quite similar to that of solving the widely known rooks puzzle. When we add the constraint (4), it significantly reduces the size of the search space, thus making it possible for a particular Latin square to effectively find the set of all its transversals and then search for sets of N mutually orthogonal transversals among them.
The number of transversals significantly differs from square to square. To the best of our knowledge, there are no known analytical results regarding how the minimal and maximal number of transversals depend on the order of a Latin square. For Latin squares and non-diagonal transversals the corresponding sequence of minimal/maximal numbers of transverals depending on the order N is presented in Online Encyclopedia of Integer Sequences entries A091323 (Minimal number of transversals in a Latin square of order 2n + 1) and A090741 (Maximum number of transversals in a Latin square of order n) [MMW06]. The question whether the maximal number of transversals for a Latin square of order 10 is 5504 is still considered an open problem [BCM+92].
Similar estimations of the numbers of transverals and diagonal transversals for diagonal Latin squares are unknown and can be determined in the course of computational experiment. For this purpose one needs to generate all possible DLS of order N , and for each DLS to construct the sets of its transversals and diagonal transversals. In order to generate all possible DLS it is possible to employ the highly efficient algorithm, developed by authors for this specific purpose. The algorithm has several special optimizations that take into account algorithmic features of this problem: it employs a specific order of filling Latin square elements based on the number of available variants [GB65]; it uses static data structures that help to avoid placing critical data into dynamic memory; it tracks the sets of possible variants of cell values for unfilled cells and terminates the exploration of branches of the search tree if there are square cells with empty sets of variants; it also employs auxiliary data structures (one-dimensional arrays) and bit arithmetic to determine the sets of possible variants fast [ZVZM16].
The construction of a set of diagonal transversals for a specific DLS is done using the following recurrent algorithm: 1. Initialization. Specify initial values for a set of transversals S := ∅, current recursion depth d := 0, set of available columns C := U , set of available elements values E := U . 2. Condition for recursion end. If D = N then add current transversal T to a set of found transversals
S := S ∩ {T }, decrease current recursion level d := d − 1, go to 3c. 3. For all values i = 1, N such that (i ∈ C) ∧ (adi ∈ E): (a) Add adi to transversal T : T [d] := i; mark i-th column as used: C := C\{i}; mark adi as used:
E := E\{adi}. (b) Recurrent descent Increase current recursion depth value: d := d + 1; go to 2.
(c) Mark i-th column as available: C := C ∪ {i}; mark adi as available: E := E ∪ {adi}. 4. End of algorithm.
In this algorithm we find all possible transversals of a given Latin square A. If it is necessary to find only diagonal transversals, then the corresponding checks (5) are added to the 2-nd point of the algorithm. In accordance with the branch and bound strategy, it is also possible (but not necessary) to add to paragraph 3 an additional condition (5), which checks whether the current transversal contains Latin square elements from its main diagonal and main antidiagonal. The latter can increase the algorithm by early rejection of non-diagonal transversals.
In Figure 3 we show how this algorithm works on an example of a Latin square of order 5. 4
We implemented the algorithm proposed in Section 3 and organized a computational experiment aimed at determining minimal and maximal number of transversals and diagonal transversals of diagonal Latin squares of small order.
The experiment for 1 ≤ N ≤ 7 was performed on one core of Intel Core i7-4770 (Haswell). The algorithm for estimating the number of transversals for DLS of order N = 8 has an average performance of about 350 DLS per second (for single-threaded implementation on Delphi programming language on one core of the mentioned CPU). Taking into account the fact that the number of DLS of order 8 is 7 447 587 840 [VZZ+16], this experiment is estimated to take about 246 days on one core or about 1 month on 8 cores. We performed this experiment in the BOINC-based volunteer computing project Gerasim@home [VVT15]. In total, 3 003 workunits were genereted for this purpose. In each workunit the first 5 elements of the second row were fixed. Thus, an original problem was decomposed on the server by varying these 5 elements. Average runtime of each workunit was about 1 hour on 1 CPU core. The computing application had to generate all normalized DLS with fixed 5 elements (obtained from the given workunit), and determine for them the required characteristics. The results of experiments for orders 1 ≤ N ≤ 8 are shown in Tables 1 and 2.
The estimation of the number of transversals for DLS of order N = 9 with an average performance of approximately 370 DLS per second will take about 900 years in a parallel computing system with performance of about 5 TFLOPs.
It is easy to see that for 1 ≤ N ≤ 8 the maximal number of transversals for DLS coincides with that for LS (sequence A090741 in OEIS), excluding the orders 2 and 3 for which there are no DLS. It is likely that this feature will be repeated for DLS of higher orders. The minimal number of transversals is a new sequence (1, 0, 0, 8, 3, 32, 7, 8) which has not yet been represented in OEIS.
When searching for diagonal transversals for DLS of order N = 8 the performance is about 440 DLS per second. It is significantly higher than for nondiagonal transversals. Apparently the reason for this is that there are more constraints and, because of this, less branches in the corresponding search trees. With this performance the corresponding experiment will take about 16 days using 8 threads. For N = 9 the corresponding performance is about 400 DLS per second and the runtme estimation is about 830 years using the same parallel computing system with performance of 5 TFLOPs.
The obtained sequences of minimal (1, 0, 0, 4, 1, 2, 0, 0) and maximal number of diagonal transversals (1, 0, 0, 4, 5, 6, 27, 120) have not been represented in OEIS before. 5
Papers [BR75, MR95, MW05] report on the number of Latin squares of orders 9, 10 and 11. The authors of the present paper developed an algorithm for generating diagonal Latin squares of special kind [ZZKV16]. In [MMW06] transversals for Latin squares of order at most 9 were enumerated. Their algorithm takes into account the fact, that the space of Latin squares can be divided into isotopy classes (115 618 721 533 classes for order 9). Transversals were enumerated for each representative, this allowed to calculate the number of transversals for each isotopy class. In the present paper we don’t deal with isotopy classes, because we work with diagonal Latin squares. So we had to generate all possible species of diagonal Latin squares of the considered orders.
There are several examples of application of high-performance computing to the search for combinatorial designs based on Latin squares. With the help of a computing cluster there was proven that there is no finite projective plane of order 10 [LTS89]. In the volunteer computing project SAT@home several dozen pairs of mutually orthogonal diagonal Latin squares were found [ZKS16]. In the volunteer computing project Gerasim@home, diagonal Latin squares of order 9 were enumerated [VKZ17]. A modern computing cluster was used to prove the hypothesis about the minimal number of clues in Sudoku [MTC14] (Sudoku problem is based on Latin squares). The volunteer computing project Sudoku@vtaiwan was used to confirm the solution of this problem [LW10].
In the present paper we enumerated transversals for diagonal Latin squares of order at most 8. The experiments were partially performed in a volunteer computing project. In future we plan to organize computational experiments aimed at extending the obtained results for larger orders of diagonal Latin squares.
We thank all Gerasim@home volunteers, whose computers took part in the experiment. [MMW06] Brendan D. McKay, Jeanette C. McLeod, and Ian M. Wanless. The number of transversals in a Latin square. Designs, Codes and Cryptography, 40(3):269–284, 2006.
Stanley E. Bammel and Jerome Rothstein. The number of 9 × 9 Latin squares. Discrete Math., 11(1):93–95, January 1975.
Charles J. Colbourn and Jeffrey H. Dinitz. Handbook of Combinatorial Designs, Second Edition (Discrete Mathematics and Its Applications). Chapman & Hall/CRC, 2006.
Solomon W. Golomb and Leonard D. Baumert. Backtrack programming. J. ACM, 12(4):516–524, October 1965.
A. H. Land and A. G. Doig. An automatic method for solving discrete programming problems. ECONOMETRICA, 28(3):497–520, 1960.