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.