RESEARCH OF THE DABBAGHIAN-WU ALGORITHM FOR CONSTRUCTING NON-CYCLIC PANDIAGONAL LATIN SQUARES
Abstract
In this paper we consider a mathematical model and the Dabbaghian-Wu algorithm based on it, designed
to construct non-cyclic pandiagonal Latin squares. It is shown that due to the high computational complexity
and the fact of existence of other varieties of pandiagonal squares, the application of classical algorithms, such
as brute force and cyclic shifts, is insufficient to construct a complete list of pandiagonal Latin squares. This confirms the purpose of the work – the research and experimental approbation of mathematical models and
algorithms for the task of construction in an acceptable time. We perform research of the algorithm presented by
Dabbaghian and Wu, which is intended for constructing pandiagonal Latin squares of prime order p, defined by
the expression p=6n+1. It is a modification of the cyclic construction algorithm and allows to obtain a
pandiagonal non-cyclic square from the original cyclic square. The conversion is done by cyclic shifts in specific
cells in each row of the original square. A software implementation of the Dabbaghian-Wu algorithm was developed.
The results of the experiments confirmed the correctness of the construction methodology proposed by
Dabbaghian and Wu. Thus, for order 13, 72 unique squares were found. In addition, an attempt was made to
construct for an order that is not an odd prime number, for example 25. In this case, it was possible to obtain 4
correct pandiagonal Latin squares. By additional conversions of the resulting sets, increase the number of
squares, so for order 13 the collection is expanded to 1570, and for 25 to 210. The research made it possible to
research the Dabbaghian-Wu algorithm in depth and draw a conclusion about its features, the advantages include
its relatively low computational complexity, and the disadvantages are the full correctness of the constructions
only for odd prime orders. The resulting sets of squares will be used in the future to obtain their numerical
characteristics using distributed computing.
References
2006, 1016 p.
2. Keedwell A.D., Dénes J. Latin Squares and their Applications. Elsevier, 2015, 438 p.
3. Vatutin E.I. O perechislenii tsiklicheskikh latinskikh kvadratov i raschete znacheniya funktsii Eylera s
ikh ispol'zovaniem [On enumerating cyclic Latin squares and calculating the value of the Euler function
using them], Vysokoproizvoditel'nye vychislitel'nye sistemy i tekhnologii [High-performance computing
systems and technologies], 2020, Vol. 4, No. 2, pp. 40-48.
4. Vatutin E.I., Kochemazov S.E., Zaikin O.S. Applying volunteer and parallel computing for enumerating
diagonal Latin squares of order 9, Proc. of The Eleventh International Conference on Parallel
Computational Technologies, Vol. 753 of Communications in Computer and Information Science.
Springer, 2017, pp. 114-129.
5. Kochemazov S., Zaikin O., Vatutin E., Belyshev A. Enumerating diagonal latin squares of order up to 9,
Journal of Integer Sequences, 2020, Vol. 23, No. 1, pp. 2012.
6. Vatutin E.I., Belyshev A.D., Nikitina N.N., Manzyuk M.O. Ispol'zovanie X-obraznykh diagonal'nykh
zapolneniy i ESODLS CMS skhem dlya perechisleniya glavnykh klassov diagonal'nykh latinskikh
kvadratov [Use of X-based diagonal fillings and ESODLS CMS schemes for enumeration of main
classes of diagonal Latin squares], Telekommunikatsii [Telecommunications], 2023, No. 1, pp. 2-16.
7. Vatutin E.I. O podschete glavnykh klassov tsiklicheskikh diagonal'nykh i pandiagonal'nykh latinskikh
kvadratov [On the calculation of the main classes of cyclic diagonal and pandiagonal Latin squares],
Optiko-elektronnye pribory i ustroystva v sistemakh raspoznavaniya obrazov i obrabotki izobrazheniy
[Optical-electronic instruments and devices in pattern recognition and image processing systems],
2021, pp. 77-79.
8. Bell J., Stevens B. Constructing orthogonal pandiagonal Latin squares and panmagic squares from
modular n-queens solutions, Journal of Combinatorial Designs, 2007, No. 15 (3), pp. 221-234.
9. Hedayat A. A complete solution to the existence and nonexistence of Knut Vik designs and orthogonal
Knut Vik designs, Journal of Combinatorial Theory, Series A, 1977, No. 22 (3), pp. 331-337.
10. Atkin A.O.L., Hay L., Larson R.G. Enumeration and construction of pandiagonal Latin squares of
prime order, Computers & Mathematics with Applications, 1983, No. 9 (2), pp. 267-292.
11. Vik K. Bedømmelse av feilene på forsøksfelter med og uten målestokk. – 1924.
12. Stoffel A. Totally diagonal Latin squares, Stud Cerc Mat., 1976, Vol. 28, pp. 113-119.
13. Chang G.J., Hwang F.K. Diagonal and Pandiagonal Tournament Latin Squares, European Journal of
Combinatorics, 1985, Vol. 6, No. 2, pp. 149-155.
14. Dabbagian V., Wu T. Constructing non-cyclic pandiagonal Latin squares of prime orders, Journal of
Discrete Algorithms, 2015, No. 30, pp. 70-77.
15. Vatutin E.I. Spetsial'nye vidy diagonal'nykh latinskikh kvadratov [Special types of diagonal Latin
squares], Oblachnye i raspredelennye vychislitel'nye sistemy v elektronnom upravlenii ORVSEU -
2022 v ramkakh Natsional'nogo superkomp'yuternogo foruma (NSKF – 2022) [Cloud and distributed
computing systems in the electronic management of ORVSEU - 2022 within the framework of the National
Supercomputing Forum (NSCF - 2022)], 2022, pp. 9-18.
16. Vatutin E., Nikitina N., Belyshev A., Manzyuk M. On polynomial reduction of problems based on diagonal
Latin squares to the exact cover problem, CEUR Workshop, 2020, pp. 289-297.
17. Vatutin E., Belyshev A., Manzuk M., Nikitina N. Evaluation of Efficiency of Using Simple Transformations
When Searching for Orthogonal Diagonal Latin Squares of Order 10, Communications in
Computer and Information Science, 2020, Vol. 1304, pp. 127-146.
18. Al'bert'yan A.M., Kurochkin I.I., Vatutin E.I. Ispol'zovanie geterogennykh vychislitel'nykh
kompleksov v grid-sistemakh iz personal'nykh komp'yuterov [The use of heterogeneous computing
complexes in grid systems of personal computers], XIV Vserossiyskaya mul'tikonferentsiya po
problemam upravleniya MKPU-2021 [XIV All-Russian Multiconference on Control Problems
MKPU-2021], 2021, pp. 90-93.
19. Nikitina N.N., Vatutin E.I., Manzyuk M.O. [i dr.]. Pokazateli i tekhnologicheskaya osnova proektov
raspredelennykh vychisleniy Rakesearch i Sidock@home [Metrics and technological basis of distributed
computing projects Rakesearch and Sidock@home], Oblachnye i raspredelennye vychislitel'nye
sistemy v elektronnom upravlenii ORVSEU - 2022 v ramkakh Natsional'nogo superkomp'yuternogo
foruma (NSKF - 2022) [Cloud and distributed computing systems in the electronic management of
ORVSEU - 2022 within the framework of the National Supercomputing Forum (NSCF - 2022)], 2022,
pp. 38-46.
20. Manzyuk M., Nikitina N., Vatutin E. Start-up and the Results of the Volunteer Computing Project
RakeSearch, Communications in Computer and Information Science, 2019, Vol. 1129, pp. 725-734.
