ИССЛЕДОВАНИЕ АЛГОРИТМА ДАББАГЯНА-ВУ ДЛЯ ПОСТРОЕНИЯ НЕЦИКЛИЧЕСКИХ ПАНДИАГОНАЛЬНЫХ ЛАТИНСКИХ КВАДРАТОВ
Аннотация
Рассматривается математическая модель и базирующийся на ней алгоритм Даббагяна-Ву,
предназначенный для построения нециклических пандиагональных латинских квадратов. Показано,
что из-за высокой вычислительной сложности и факта существования других разновидностей
пандиагональных квадратов, применение классических алгоритмов, таких как полный перебор и
циклических сдвигов, недостаточно для построения полного перечня пандиагональных латинских
квадратов. Этим подтверждается цель работы – исследование и экспериментальная апробация
математических моделей и алгоритмов, предназначенных для задачи построения за приемлемое
время. Здесь производится исследование алгоритма, представленного Даббагяном В. и Ву. Т, ко-
торый предназначен для построения пандиагональных латинских квадратов простых порядков p,
определяемых выражением p=6n+1. Можно сказать, что он является модификацией алгоритма
циклического построения. То есть, позволяет получить из исходного циклического квадрата пан-
диагональный нециклический. Преобразование выполняется путем циклических сдвигов в опреде-
ленных ячейках в каждой строке исходного квадрата. Была разработана программная реализация
алгоритма Даббагяна-Ву. Результат экспериментов подтвердил корректность предложенной
Даббагяном В. и Ву. Т. методики построения. Таким образом, для порядка 13 удалось найти 72
уникальных квадрата. К тому же, проведена попытка построения для порядка, не являющегося
нечетным простым числом, например 25. В данном случае удалось получить 4 корректных пан-
диагональных латинских квадрата. Путем дополнительных преобразований полученных наборов
увеличить количество квадратов, так, для порядка 13 коллекция расширена до 1570, а для 25 – до
210. Исследование позволило углубленно ознакомиться с алгоритмом Даббагяна-Ву и сделать вы-
вод о его особенностях – к достоинствам относится его относительно низкая вычислительная
сложность, а к недостаткам – полноценная корректность построений только для нечетных про-
стых порядков. Полученные наборы квадратов в дальнейшем будут задействованы для получения
их числовых характеристик при помощи распределенных вычислений.
Литература
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.
