Использование Х-образных диагональных заполнений и ESODLS CMS схем для перечисления главных классов диагональных латинских квадратов

摘要

В статье введено понятие Х-образных диагональных заполнений в диагональных латинских квадратах (ДЛК), проведено их перечисление, построение классов изоморфизма и показана связь с задачами на базе карточных деков. На их основе предложен способ генерации сильно нормализованных канонических форм ДЛК с использованием ограниченного множества ESODLS CMS схем, позволяющий сократить необходимые вычислительные затраты на 3—4 порядка по сравнению с программной реализацией на базе полного перебора ДЛК. С использованием разработанных программных реализаций и проекта добровольных распределенных вычислений Gerasim@Home на платформе ВОШС осуществлен подсчет числа главных классов ДЛК порядка 9, число которых ранее было неизвестно и составило 3292326155394.