In this paper, we study the dependencies of the number of symmetric and doubly symmetric diagonal Latin squares on the order N. Using fast generator of diagonal Latin squares (augmented by symmetry checker), we determined these dependencies for order at most 8. We also found a number of doubly symmetric diagonal Latin squares of orders 12, 16 and 20.
Latin square (LS) of order N is a square table A = kaij k; i; j = 1; N , which
consists of elements from some set U; jU j = N [
DLS is normalized, if elements of its rst row are sorted in ascending order.
It is easy to show, that any DLS can be normalized using bijective
substitution (permutation) of its elements. Thus, we can de ne classi cation on the set
of all possible DLSs of a particular order: all DLSs, which can be reduced to
the same normalized DLS, form one equivalence class. This classi cation can be
used in application to some combinatorial problems (enumeration of LSs and
DLSs [
By symmetric LS we mean such LS, for which one-to-one correspondence occurs between all pairs of elements (aij ; ai;N j+1); i = 1; N ; j = 1; b N2 c. This symmetry occurs in the horizontal plane { with respect to the vertical line (across the central column for DLSs of odd order and between two central columns for DLSs of even order). By analogy, one can denote the symmetry in the vertical plane. For normalized DLS the condition of occurrence of symmetry in the horizontal plane can be rewritten in more simple form: aij + ai;N j+1 = N 1. Symmetric LSs have symmetric set of transversals, this can be employed for constructing pairs and triples of (partially) mutually orthogonal diagonal Latin squares. Examples of two symmetric DLSs (in the horizontal and vertical plane respectively) are depicted in Figure 1.
0 1 2 3 4 5 4 2 0 5 3 1 5 4 3 2 1 0 2 5 4 1 0 3 3 0 1 4 5 2 1 3 5 0 2 4 0 1 2 3 4 5 4 2 5 0 3 1 3 5 1 2 0 4 5 3 0 4 1 2 2 4 3 1 5 0 1 0 4 5 2 3
Dependence of the number of symmetric LSs with xed diagonal on order
N is represented by the sequence A003191 in Online Encyclopedia of Integer
Sequences (OEIS) [
Dependence of the number of symmetric DLSs on the order N is not presented in OEIS at the present moment, that is why determining of this dependence is of great importance. The most natural way to solve this problem for a given order N is to generate all DLSs, and perform symmetry checking for each of them. It is also possible to improve this approach by lling half of square's elements in combination with varying the order of lling elements based on principle of minimum feasibilities and the branch and bound method.
Generation of DLSs can be done by an e ective generator, which was
developed by authors of the present paper. This generator is based on some
algorithmic features of the considered problem. The following techniques made it
possible to achieve high e ciency of our generator (see [
{ Using the order of lling elements based on principle of minimal feasibilities. { Using static data structures instead of dynamic ones. { Taking into account the cardinality of the set of possible values for currently un lled square's cells in combination with early clipping unpromising branches of a combinatorial tree in the case of nding square's cells without any possible elements. { Applying auxiliary data structures (one-dimensional arrays) for fast construction of the set of possible elements.
{ Employing bit arithmetic. 4
In accordance with the rst strategy (see Section 3), we developed a program implementation, which was used to determine the dependence of the number of normalized symmetric DLSs on the order N . The results of the computational experiments are shown in Table 1.
At the present moment, the number of symmetric normalized DLSs of order 10 can not be calculated in a reasonable time. Let us consider an approach, which consists in the generation of the corresponding DLSs with symmetry checking of each generated DLS. The speed of the corresponding sequential program (written in Delphi) is about 200 000 DLSs per second on i7 4770 CPU. If we assume, that there are about 1022 normalized DLSs of order 10, than it will take about 1:6 109 years for this program to process all of them. A supercomputer with the performance of 1 tera ops will take about 160 years to perform the same experiment.
Besides that, there are also DLSs, which are symmetric in horizontal and vertical plane at the same time (further we will call them doubly symmetric). An example of such DLS is depicted in Figure 2. DLSs of this type are quite rare combinatorial objects. The dependence of the number of doubly symmetric normalized DLSs on the order N is shown in Table 2. For each considered order it was obtained by generating all DLSs with checking doubly symmetry for each of them.
0 1 2 3 4 5 6 7 6 2 3 7 0 4 5 1 4 5 1 0 7 6 2 3 5 6 7 4 3 0 1 2 7 3 6 2 5 1 4 0 2 7 4 1 6 3 0 5 3 0 5 6 1 2 7 4 1 4 0 5 2 7 3 6 According to results of the experiment, we can conclude, that for 2 N 8 there is are doubly symmetric DLSs for orders, which are not multiples of 4. For 9 N 20 we also could nd doubly symmetric DLSs only for N = 4n; n 2 N, i.e. for N = 12; 16; 20. However, in these additional experiments we did not use an exhaustive search { for each considered N its own 1-day random search based experiment was performed. We presume, that this feature holds true for all N 1.
Symmetric and doubly symmetric DLSs have a number of peculiarities, which are outlined below.
{ As a rule, they have a lot of transversals. { They usually (but not always) have a lot of orthogonal diagonal mates. { For N = 4 and N = 8 all known DLSs with maximal possible number of orthogonal mates, are doubly symmetric.
Let us show these doubly symmetric DLSs with maximal possible number of orthogonal mates. B@B13 02 31 20CAC ; BBBB75 63 57 41 36 20 14 02CCCC :
By analogy, we tried to nd additional symmetries in DLSs with respect to their diagonals, but it turned out, that there are no such symmetries for N 8.
Thus, in the course of the experiments we found two integer sequences: (0; 2; 64; 3 612 672) { the number of normalized symmetric DLSs of order 2n and (0; 2; 0; 15 780) { the number of normalized doubly symmetric DLSs of order 2n. None of these sequences is presented in OEIS at the present moment. We have not found any other types of symmetries in DLSs.