The paper discusses the reduction of problems based on Latin squares to the exact cover problem aiming at its subsequent solution using the dancing links algorithm. The former problems include generation of Latin squares and diagonal Latin squares of a general form/with a given normalization, generation of orthogonal Latin and diagonal Latin squares directly/through the set of transversals, obtaining a set of transversals for a given square, forming a subset of disjoint transversals. For each subproblem, we describe in detail the process of forming the corresponding binary coverage matrices. We show that the use of the proposed approach in comparison with the classical one, i.e. the formation of sets of transversals and their coverages using exhaustive enumeration, allows one to increase the e ective processing pace of diagonal Latin squares by 2.5{5.6 times. The developed software implementations of the algorithms are used in computational experiments as part of the Gerasim@Home volunteer distributed computing project on the BOINC platform
One of the known types of combinatorial objects are the Latin Squares (LS) [
Currently, all ODLS of orders 1{8 and their properties are known up to an isomorphism in
the corresponding main classes1. For higher orders, it is currently not possible to obtain all
ODLS due to their large number on the one hand and, as a consequence, huge computational
costs on the other hand. Currently, in the projects of volunteer computing RakeSearch [
The DLX algorithm for solving the exact cover problem is based on constructing the corresponding binary coverage matrix of size R rows by C columns, followed by nding such subsets of rows whose units exactly (without intersections) cover all columns. To solve problems based on LS/DLS, it is necessary to form various coverage matrices, which is non-trivial and is discussed in detail below.
When forming an LS , the rows of the binary matrix correspond to all possible combinations of triples (i; j; ), where i is the row number of the formed square, j is the column number, is the value placed in the cell aij , the total number of rows is N 3. The columns of the binary matrix correspond to three semantic groups of N 2 elements each: (i) The i-th row ri of the square contains the value of (N 2 columns of the binary matrix), (ii) The j-th column cj contains the value of (N 2 columns of the binary matrix), (iii) The cell of a square with coordinates [i; j] is used (N 2 columns of a binary matrix).
The binary matrix that corresponds to forming an LS of order 3 is shown in Fig. 1.
When forming a DLS , two more groups of columns are added to the matrix considered above: (i) The main diagonal of the square contains the value (N columns), (ii) The secondary diagonal of the square contains the value (N columns).
The binary matrix that corresponds to forming an LS of order 3 is shown in Fig. 2.
When forming LS/DLS normalized by their rst row , by de nition, the elements of the rst row are speci ed: a00 = 0; a01 = 1; : : : ; a0;N 1 = N 1, and one cannot set any other values in their places, which corresponds to the special rst row and gaps (empty rows without units) in the binary matrix. An example of such a binary matrix is shown in Fig. 3, where blank lines are highlighted in gray. In order to reduce the problem dimension, empty rows can be removed from the matrix.
To search for a set of diagonal transversals in the LS/DLS , the rows of the binary matrix correspond to the elements aij of the square, included in the transversal. The columns of the matrix correspond to the following semantic groups of elements: 1 http://evatutin.narod.ru/evatutin odls 1 to 8.zip (i) Transversal element aij covers the i-th row of the square (N columns), (ii) Transversal element aij covers the j-th column of the square (N columns), (iii) Transversal element aij = (N columns),
covers the value of in the set of values used in the transversal (iv) Element aij is located on the main diagonal (1 column), (v) Element aij is located on the secondary diagonal (1 column).
When forming transversals of a general form (non-diagonal), the last two semantic groups and the corresponding two columns of the matrix should be excluded from consideration. Note that when forming a coverage, the values of groups 1, 2, 4, and 5 are general and independent of the processed DLS, while the values of group 3 are determined by the speci c values of the elements of the processed DLS, for which a set of transversals is formed. An example of a binary 00 1 21 matrix for the formation of a set of diagonal transversals for an LS @1 2 0A is shown in 2 0 1
To search for an ODLS mate B for a given DLS A directly (without using transversals), the binary matrix has N 3 rows corresponding, as in the search for LS/ DLS, to all possible combinations of triples (i; j; ). The columns of the matrix correspond to two semantic groups: (i) The formation of the correct DLS B (3N 2 + 2N columns), (ii) The uniqueness of pairs of values ( 1; 2), 1 = aij , 2 = bij (N 2 columns by the number of pairs).
(3N 2 + 2N ) for the formation of DLS of order N = 3.
To form an OLS from the rst semantic group of the matrix, it is necessary to exclude 2N columns corresponding to restrictions on the uniqueness of values on the diagonals.
To form the reduced OLS/ODLS pairs , it is necessary, as already discussed above, to form a special rst row of the binary matrix corresponding to the pairs of elements (0; 0); (1; 1); : : : ; (N 1; N 1) in the rst rows of squares of the formed pair, and to remove from the binary matrix the empty lines corresponding to the assignment (a0i := 1) ^ (b0i := 2) of values of the xed elements. An example of a binary matrix corresponding to the formation of the ODLS mate to a given DLS is shown in Fig. 5.
When forming an ODLS from a set of transversals , each row of the binary matrix corresponds to one of the transversals, the columns of the matrix correspond to the elements aij of the formed orthogonal square that are part of the transversal. An example of a square, its set of transversals and the corresponding binary matrix are shown in Fig. 6.
When forming ODLS pairs directly (without transversals), the corresponding binary matrix will have N 4 rows corresponding to all possible combinations of values (i; j; 1; 2), and
DL{Sz A (3N 2 + 2N ) + (3N 2 + 2N ) + | } | }
DL{Sz B
N 2 pairs (ai|j;{bzij})=( 1; 2) = 7N 2 + 4N columns that correspond to the correctness conditions for the pair of squares A and B in conjunction with the uniqueness of the pairs ( 1; 2).
It is easy to notice that the binary matrices given above, corresponding to various problems based on LS/DLS/OLS/ODLS, are signi cantly sparse, which makes it e cient to use the DLX dancing links algorithm in the search for coverages.
(3N +2) to form the set of diagonal transversals of the
(4N 2 + 2N ) for forming the ODLS for the given LS dimension of the problem being solved (from the LS/DLS order N ), and the corresponding algorithms for their formation are quite simple and have an asymptotic polynomial time complexity not exceeding O(N 3).
Construction of the set Construction of the set of transversals of LS/DLS of diagonal transversals of LS/DLS
In the early software implementation the search for transversals and covers from them was
implemented using the exhaustive search method. In this case, the strategy of early cutting
o unpromising solutions (branches and bound method [
Thus, the problems considered above allow e ective polynomial reduction to the exact cover
problem and its solution using DLX. The developed software implementations of the algorithms
for constructing cover matrices, DLX, and reconstructing solutions from the found covers are
currently actively used in the Gerasim@Home volunteer computing project within the BOINC
platform [
The work was supported by the Russian Foundation of Basic Research, project 18-07-00628. Authors thank citerra [Russia Team] from the internet portal BOINC.ru for his help in the development and implementation of some algorithms and corresponding productive discussions.