Algorithms for Construction and Enumeration of Closed Knight’s Paths

Prof. DSc. Stoyan Kapralov1), Assoc. Prof. Dr.Valentin Bakoev2),
Kaloyan Kapralov3)
1)University of Gabrovo (Bulgaria)
2)“St. Cyril and St. Methodius” University of Veliko Tarnovo (Bulgaria)
3)Sofia (Bulgaria)

https://doi.org/10.53656/math2023-2-1-alg

Abstract. Two algorithms for constructing all closed knight’s paths of lengths up to 16 are presented. An approach for classification (up to equivalence) of all such paths is considered. Two closed knight’s paths are called equivalent if one can be obtained from the other by applying one or more of the equivalences: translation, rotation, symmetry, or when the corresponding polygons (whose vertices are the cells visited by the knight), are geometrically congruent. By applying the construction algorithms and classification approach, we enumerate both nonequivalent and non-self-intersecting knight’s paths and show the obtained results. Some pedagogical aspects related to the problems under consideration and the teaching of subjects such as “Programming”, “Algorithms and Data Structures”, “Graph Algorithms” and “Competitive Programming” are also discussed.
Keywords: knight graph; closed knight’s path; nonequivalent path; non-self-intersecting path; equivalence; enumeration

Свързани статии:

The Values Of The Teachers For The Implementation Of Inclusive Education In Bulgaria Inspection Of The Schools In Varna-Preslav Diocese / Varna Province In 70-S Of The Nineteenth Century A MONOGRAPH ON THE CRIMEAN WAR (1853 – 1856)AND THE BULGARIAN LANDS, PRESENTED THROUGH AN ORIGINAL FRENCH SOURCE FROM THE AGE 75 Years of the World Organization OMEP: Preschool Education in Bulgaria in the Perspective of International Pedagogical Experience