Исследование свойств диагональных латинских квадратов в проектах добровольных распределенных вычислений и не только...
Одним из редких и интересных типов латинских квадратов являются пандиагональные ЛК, у которых, как известно, значения не дублируются не только в строках и столбцах, но еще и на всех 2*N ломаных диагоналях, параллельных главной и побочной диагоналям. Существует несколько видов ЛК данного типа, которые мы научились получать в разное время.
1. Циклические ДЛК — получаются путем циклического сдвига первой строки (обычно нормализованной, но не обязательно) на некоторое число позиций d — см., например, https://oeis.org/A338562.
2. Полуциклические ДЛК — получаются путем всех возможных перестановок строк циклического ДЛК, не нарушающих определение пандиагональности — см., например, https://oeis.org/A342990. Т.е. фактически в квадратах данного типа каждая i-я строка представляет собой циклическую перестановку элементов первой строки на некоторое значение d(i). На самом деле аналогичные определения можно ввести и для столбцов, причем одновременная "цикличность" строк и столбцов приводит к циклическим ДЛК, а цикличность только в одной плоскости — к полуциклическим ДЛК.
3. Цикличность можно ввести также для ломаных диагоналей и ломаных антидиагоналей, а соответствующий тип пандиагональных ДЛК называется повернутыми полуциклическими пандиагональными — см., например, http://evatutin.narod.ru/oeis_cyclic_dls.html, соответствующие числовые ряды посчитаны, но пока не добавлены в OEIS. Для циклических ДЛК данные свойства получаются "автоматически", для полуциклических — путем поворотов полуциклических на углы, кратные 45 градусам.
Однако данными типами пандиагональные ЛК не ограничиваются.
4. В работе Даббагяна и Ву приведен алгоритм построения еще одного типа пандиагональных ЛК, которые в общем случае не являются ни циклическими, ни полуциклическими, ни повернутыми полуциклическими. Они существуют не для всех порядков, путем ряда эквивалентных преобразований (повороты на углы, кратные 45 градусам, отражения/транспонирования, повороты на торе) их множество может быть расширено, что и было сделано недавно (см. https://vk.com/wall162891802_2525).
5. Ну и наконец пару лет назад в OEIS Andrew Howroyd'ом был добавлен еще один числовой ряд https://oeis.org/A343867, который, судя по названию, представляет собой полуциклические пандиагональные ЛК, т.е. ЛК, совмещающие в себе оба свойства, но... Например, для порядка N=13 известно 348 полуциклических ДЛК и, судя по данному ряду, — 1560 пандиагональных полуциклических, что вроде бы противоречит логике, т.к. по названию второе должно быть подмножеством первого. Однако, вчитавшись в комментарии к данному ряду и в статью
A. O. L. Atkin, L. Hay, and R. G. Larson, Enumeration and construction of pandiagonal Latin squares of prime order, Computers & Mathematics with Applications, Volume. 9, Iss. 2, 1983, pp. 267-292. https://doi.org/10.1016/0898-1221(83)90130-X
оказывается, что авторы трактуют полуцикличность по-другому, а именно следующим образом: существуют такие положительные значения dx, dy и dv, что для всех ячеек квадрата L выполняется соотношение
L[x][y] + dv = L[x+dx][y+dy] (все сложения, как и ранее, по модулю N).
Другими словами, по аналогии с шахматами, берем коня, который, как известно, ходит буквой Г, только в отличие от классических шахмат размер этой буквы не (1,2), а (dx,dy), обходим им квадрат в выбранном направлении, при каждом прыжке увеличивая значение в новой ячейке на dv по сравнению с предыдущей, и в итоге получаем соответствие приведенной выше формуле. Пример обхода из верхней левой ячейки ЛК, имеющей нулевое значение, для dx=1, dy=3 и dv=1 приведен ниже:
0 - - - - - - - - - - - -
- - - 1 - - - - - - - - -
- - - - - - 2 - - - - - -
- - - - - - - - - 3 - - -
- - - - - - - - - - - - 4
- - 5 - - - - - - - - - -
- - - - - 6 - - - - - - -
- - - - - - - - 7 - - - -
- - - - - - - - - - - 8 -
- 9 - - - - - - - - - - -
- - - - 10 - - - - - - - -
- - - - - - - 11 - - - - -
- - - - - - - - - - 12 - -
Очевидно, что определение отличается от приведенного выше в п. 2, и квадраты будут другие (как минимум, что уже было отмечено выше, их количество отличается), а значит во избежание терминологической путаницы будем их называть пандиагональными ЛК Аткина-Хея-Ларсона.
Однако при попытке построения их множества оказывается, что их количество совпадает с числом циклических квадратов, как и сам состав формируемых квадратов, что-то не то... Намеком на правильный путь построения квадратов данного типа является то, что в примере в OEIS приведен денормализованный ЛК и, как оказалось, не зря! Если взять произвольную "правильную" перестановку порядка N в качестве первой строки формируемого квадрата, то квадраты как раз будут получаться отличные от циклических (для "неправильной" первой строки формируемый квадрат будет некорректным), причем после выполнения нормализации они будут другими, не эквивалентными ни циклическим, ни полуциклическим. А раз так, то можно попробовать построить их множество, заодно проверив значения числового ряда A343867.
Простейшим алгоритмом будет следующий: сформировать все N! возможных первых строк, взять все возможные сочетания значения dx, dy, dv в диапазоне [1; N-1], для всех N! * (N-1)^3 комбинаций построить соответствующие им пандиагональные ЛК, нормализовать, убить дубли и получить результирующий список искомых пандиагональных ЛК Аткина-Хея-Ларсона. В лоб данный алгоритм будет работать достаточно долго, ввиду чего можно задействовать ряд хитростей, снижающих вероятность появления дублирующихся решений, а именно:
* сперва формировать значения dx, dy, dv, а затем подбирать под них "правильные" первые строки ЛК;
* брать не все возможные (N-1)^3 комбинаций значений dx, dy, dv, а только такие, что dx=1, 1<=dy<=N-1, dv=1;
* использовать не все N, а только нулевое значение в ячейке L[0][0];
* при формировании значений перестановок первой строки брать не все возможные N! перестановок (точнее, (N-1)! с учетом нулевого значения на первом месте), а только такие, цепочка позиций при движении коня из которых не приводит к получению некорректного частично заполненного ДЛК (т.е. фактически использовать отсечения некорректных решений на ранних стадиях).
Например, для порядка N=13 использование данных особенностей сокращает время вычислительного эксперимента с 1 ч 52 мин до 3,5 секунд при условии, что в исходной версии использовались отсечения при формировании перестановок, без них все работало бы на порядки дольше!
В результате выполнения приведенного выше алгоритма получаются следующие множества пандиагональных ЛК:
N=1 — 1
N=5 — 2
N=7 — 4
N=11 — 8
А теперь самое интересное
N=13 — 894 (3,5 сек в 1 поток на Core i7 4770)
N=17 — 17490 (38 минут в 1 поток)
N=19 — 88784 (6 ч 50 минут в 1 поток)
Или, что то же самое, в виде нового числового ряда, не представленного в OEIS: 1, 0, 2, 4, 0, 8, 894, 0, 17490, 88784, 0. Для порядков, кратных 2 и 3, пандиагональных ЛК не существует, поэтому в полученном числовом ряду на соответствующих местах стоят нули. Расчет для порядка N=23 в перспективе можно выполнить в проекте, на одной машине это будет достаточно долго.
Вроде бы опять не то... Однако если для данных множеств квадратов произвести повороты на углы, кратные 45 градусам, а затем удалить из полученного множества циклические ДЛК, то получатся в точности те значения, которые приведены в OEIS (как минимум для порядков N<22, остальные пока не проверялись).
PS. Интересной особенностью работы данного метода построения полуциклических пандиагональных ЛК Аткина-Хея-Ларсона является тот факт, что для некоторых порядков метод приводит к получению вполне корректных ДЛК, правда не являющихся пандиагональными. Пример подобного ДЛК для порядка N=15 (dx=1, dy=9, dv=1) приведен ниже:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
1 2 0 6 11 8 9 14 3 4 13 12 5 7 10
6 3 5 7 14 9 10 2 11 13 12 4 1 8 0
11 12 8 14 9 7 13 0 4 1 5 10 2 3 6
14 4 7 13 10 11 12 5 1 8 9 0 3 6 2
9 10 13 0 6 4 5 1 12 3 7 2 14 11 8
10 13 9 5 2 12 3 8 0 6 11 14 4 1 7
5 0 4 1 8 3 7 13 2 11 14 6 10 12 9
2 14 12 8 3 1 11 9 6 10 4 7 13 0 5
8 6 1 11 7 2 14 4 10 12 3 9 0 5 13
3 7 11 9 5 6 4 10 14 0 1 13 8 2 12
7 11 3 4 13 14 0 12 9 5 2 8 6 10 1
4 9 6 10 12 0 1 11 13 2 8 5 7 14 3
13 8 14 12 0 10 2 3 5 7 6 1 11 9 4
12 5 10 2 1 13 8 6 7 14 0 3 9 4 11
PPS. Обход квадрата, а по сути — шахматной доски, конем с заданными параметрами dx и dy смещений по горизонтали и вертикали фактически приводит к получению решений одной довольно известной задачи из целого направления задач данного класса в перечислительной комбинаторике — задачи о ладьях, ферзях, полуферзях и вот в данном случае о ферзях на тороидальной доске. Фактически из решений данной задачи потом конструируются полуциклические пандиагональные ЛК Аткина-Хея-Ларсона, что дает нам еще одну весьма интересную связь латинских квадратов и объектов из других разделов комбинаторики, на первый взгляд никакого отношения к квадратам не имеющих.
PPPS. В упомянутой выше статье приведено описание еще одного типа пандиагональных ЛК, не являющихся полуциклическими. Их построение пока оставим на сладкое... 
А можно 2 вопроса:
- А есть ли хоть какое-то продвижение в портировании счётного приложения RakeSearch под Linux и MacOS ?
- А как сейчас с развитием идеи, направления, чтобы часть больших длинных экспериментов RakeSearch запрограммировать на различные FPGA (ПЛИС) и перенести хоть часть работы на них?
В OEIS подтвержден еще один числовой ряд https://oeis.org/A366332 — минимальное число диагональных трансверсалей в полуциклических диагональных латинских квадратах порядка N=2n+1
В свободный доступ выложены списки пандиагональных полуциклических ЛК Аткина-Хея-Ларсона (см. https://oeis.org/A343867):
* порядок N=13 — http://evatutin.narod.ru/evatutin_ahl_pandiagonal_n13_1560_items_without_cyclic.zip
* порядок N=17 — http://evatutin.narod.ru/evatutin_ahl_pandiagonal_n17_34000_items_without_cyclic.zip
* порядок N=19 — http://evatutin.narod.ru/evatutin_ahl_pandiagonal_n19_175104_items_without_cyclic.zip
Напомню, что они были получены относительно недавно (см. анонс https://vk.com/wall162891802_2530) с использованием следующей схемы:
1. Формирование всех возможных комбинаций перестановок первой строки P и соотношения смещений dx, dy и dv при построении решений задачи расположения ферзей на тороидальной доске.
2. Все возможные повороты полученных пандиагональных ЛК на углы, кратные 45 градусам.
3. Нормализация, исключение дублей, исключение циклических ДЛК.
Списки находок для порядков N=13 и N=17 ранее были получены Harry White'ом (в соответствующих текстовых файлах, ссылки на которые имеются в OEIS, об этом указано), однако в OEIS авторство указано неправильное, надо будет поправить. Значения для порядков N=13, N=17 и N=19 были посчитаны ранее Andrew Howroyd'ом, однако скорее всего он сделал лишь перечисление без сохранения результатов в виде ЛК. Полученные в ходе эксперимента списки квадратов подтверждают более ранние построения упомянутых выше авторов. Также в OEIS присутствуют значения для порядков 23, 25, 29 и 31, посчитанные Jim White'ом (интересно, они с Harry случайно не родственники? :), аналогично без соответствующих подтверждающих списков. Их можно попробовать перепроверить в перспективе (хотя бы N=23 для начала), но для этого уже возможностей одной машины недостаточно и будет нужен грид...
Цитата: Yura12 от 19.11.2023, 20:03А можно 2 вопроса:
- А есть ли хоть какое-то продвижение в портировании счётного приложения RakeSearch под Linux и MacOS ?
- А как сейчас с развитием идеи, направления, чтобы часть больших длинных экспериментов RakeSearch запрограммировать на различные FPGA (ПЛИС) и перенести хоть часть работы на них?
1 — нет, причиной чему является большая загрузка по работе (у меня более 10 пар в неделю, это 3,5 рабочих дня в университете + бесконечные бестолковые поручения (мы опять переделываем наши любимые рабочие программы, опять все неправильно, пошла уже 45-я версия, нас припрягают к повышению квалификации школьных учителей, чем я считаю мы заниматься не должны, ибо в городе для этого есть профильная организация (КИРО)), и т.п.). В "плохое" советское время, о чем вспоминают возрастные профессора, такого не было: профессор не занимался бумажной работой, преподавал обычно 1-2 лекционных курса (зато на каком уровне!), а не 10-15, имел время на работу с аспирантами и занятия наукой, что в современных реалиях, к большому сожалению, делается по остаточному принципу... Во вторник стартует НСКФ, к которому сейчас идут последние штрихи подготовки: на мне лично 1 доклад, 2 доклада моих учеников (аспирант и магистрант), еще 2 ученика слились и доклады не подготовили, хотя по тем же пандиагональным ЛК я бы хотел видеть результаты ученика, а не мои доделки за ним, и ведение 1-2 наших секций совместно с Argut'ом. А дальше будет декабрь, конец семестра, курсовые, зачеты, сессия, на что тоже обычно требуется куча времени...
2 — это можно сделать, но... На это нужно как минимум время и сами ПЛИСы, которые, в отличие от CPU или GPU все же больше экзотика, они массово не распространены. Это направление я считаю весьма перспективным, ими активно занимаются как минимум в Таганроге, где мне удалось недавно побывать в командировке и чуть более подробно познакомиться с их весьма интересными наработками в данном направлении. Есть весьма интересные наработки Assa'ы по перечислению ДЛК на ПЛИС, но, насколько мне известно, работу в данном направлении он пока приостановил, последний его доклад про это был как раз на НСКФ год назад.
Давайте попробуем порешать задачу о расстановке ферзей на тороидальной шахматной доске (toroidal n queens problem)?
А давайте! Ее сложность, без учета распараллеливания расчетного кода, учета симметрий и классов изоморфизма решений примерно соответствует сложности курсовых работ по программированию на первом курсе нашей специальности, а раз вождь по-прежнему претендует на должность вождя, то он должен самостоятельно мочь залезть на пальму и сорвать кокос, а не только требовать оного от зеленых студентов, залезать на пальму самостоятельно без потусторонней помощи или административного нажима на вождя у которых получается далеко не всегда :). Соответствующий программный код сравнительно невелик, около 2 экранов, он был написан в перерывах между занятиями в университете, когда заняться было нечем, а далее он был интегрирован с остальными квадратными наработками и вот что получилось в итоге...
Во-первых, его необходимо проверить, т.е. получить решения для различных размеров досок N и сравнить с известными. Данная операция была проделана, число решений было подсчитано, в результате чего был получен числовой ряд, в точности совпадающий с https://oeis.org/A051906 или с https://oeis.org/A007705 в случае, если из первого ряда повыкидывать нулевые четные члены, что принято и часто практикуется в OEIS. Значения для порядков 1 <= N <= 15 получаются практически мгновенно, для бОльших порядков соответствующие затраты времени для однопоточной программной реализации приведены ниже
N=16 — 15 с
N=17 — 1 мин 23 с
N=18 — 8 мин 8 c
N=19 — 38 мин 54 с
(в указанные затраты времени входит не только подсчет, но еще и составление коллекции решений, что требует несколько бОльших временнЫх затрат по сравнению с первым вариантом). Примеры решений для различных размеров досок приведены ниже.
N=5 (всего 10 решений):
0 . . . . | 0 . . . . | . . . . 0
. . 0 . . | . . . 0 . | . . 0 . .
. . . . 0 | . 0 . . . | 0 . . . .
. 0 . . . | . . . . 0 | . . . 0 .
. . . 0 . | . . 0 . . | . 0 . . .
N=7:
0 . . . . . .
. . . 0 . . .
. . . . . . 0
. . 0 . . . .
. . . . . 0 .
. 0 . . . . .
. . . . 0 . .
N=11:
0 . . . . . . . . . .
. . 0 . . . . . . . .
. . . . 0 . . . . . .
. . . . . . 0 . . . .
. . . . . . . . 0 . .
. . . . . . . . . . 0
. 0 . . . . . . . . .
. . . 0 . . . . . . .
. . . . . 0 . . . . .
. . . . . . . 0 . . .
. . . . . . . . . 0 .
Пока все тривиально, все решения получаются путем обхода доски шахматным конем с некоторыми смещениями (dx,dy) между прыжками. А вот начиная с N=13 поведение меняется: кроме аналогичных решений появляются еще и другие, в которых порядок в общем случае является произвольным (Запомним этот факт! Уж не по похожей ли причине начиная с N=13 появляются нециклические пандиагональные ЛК?), примеры ниже.
N=13:
0 . . . . . . . . . . . . | 0 . . . . . . . . . . . .
. . 0 . . . . . . . . . . | . . 0 . . . . . . . . . .
. . . . 0 . . . . . . . . | . . . . 0 . . . . . . . .
. . . . . . 0 . . . . . . | . . . . . . 0 . . . . . .
. . . . . . . . 0 . . . . | . . . . . . . . . . . 0 .
. . . . . . . . . . 0 . . | . . . . . . . . . 0 . . .
. . . . . . . . . . . . 0 | . . . . . . . . . . . . 0
. 0 . . . . . . . . . . . | . . . . . 0 . . . . . . .
. . . 0 . . . . . . . . . | . . . 0 . . . . . . . . .
. . . . . 0 . . . . . . . | . 0 . . . . . . . . . . .
. . . . . . . 0 . . . . . | . . . . . . . 0 . . . . .
. . . . . . . . . 0 . . . | . . . . . . . . . . 0 . .
. . . . . . . . . . . 0 . | . . . . . . . . 0 . . . .
Нам данные решения нужны не просто так, а с целью последующего построения пандиагональных ЛК из них. Для этого ранее, по крайней мере в рамках полуциклических пандиагональных ЛК Аткина-Хея-Ларсона, использовались только такие решения, в которых ферзь стоит в верхнем левом углу доски. Попробуем решить обозначенную выше задачу о расстановке ферзей на тороидальной доске с данным ограничением и получим число решений, описываемое следующим числовым рядом:
1, 0, 0, 0, 2, 0, 4, 0, 0, 0, 8, 0, 348, 0, 0, 0, 8276, 0, 43184, 0
Члены a(1)-a(15) считаются практически мгновенно, затраты времени для однопоточной программной реализации для остальных приведены ниже:
N=16 — 1 с
N=17 — 5 с
N=18 — 27 с
N=19 — 2 мин 3 с
N=20 — 13 мин 30 c
N=21 — 1 ч 3 мин 28 с
Данный ряд в OEIS вроде бы не присутствует, однако, если исключить из его состава четные нулевые элементы, получится числовой ряд
1, 0, 2, 4, 0, 8, 348, 0, 8276, 43184
который уже присутствует в OEIS под номером A071607 и связан с отображениями циклической группы Z_{2n+1} (number of strong complete mappings of the cyclic group Z_{2n+1}). И этот ряд нам уже попадался ранее! Кроме отображений циклических групп это еще и число вертикально или горизонтально полуциклических ДЛК с фиксированной первой строкой, а теперь еще и ферзи! Найденные числовые ряды связаны следующим соотношением:
Общее_число_решений = число_решений_с_ферзем_в_верхнем_левом_углу * N
или
A071607(n) = A007705(n) / (2*n+1)
(в описании к ряду A071607 данное соотношение присутствует, а вот в рядах A051906 и A007705 почему-то нет, надо бы добавить в перспективе). На самом деле зафиксированный угол со стоящим в нем ферзем может быть любым, не обязательно верхним левым, главное, чтобы он был одинаков для всех решений. В более общем случае фиксацию можно делать в произвольном месте доски, не обязательно в углу, просто для последующих построений с пандиагональными ЛК так удобнее. Наличие множителя N объясняется тем, что любое решение можно провернуть на торе в одной из плоскостей так, чтобы единица попала в выбранный верхний левый угол, соответственно мощность семейства подобных решений равна N, а решение с фиксацией ферзя в верхнем левом углу можно рассматривать как некий аналог процедуры нормализации ЛК/ДЛК в рамках соответствующего класса изоморфизма.
Продолжение следует, вполне вероятно, что с найденными "не конными" решениями в перспективе получится сделать кое-что интересное в контексте еще одного типа пандиагональных ЛК...
от судоку к шахматам!
)))
Завтра в Институте программных систем им. А.К. Айламазяна РАН (г. Переславль-Залесский) стартует Национальный суперкомьютерный форум: https://2023.nscf.ru . Крайне жаль, что в этот раз организаторы приняли решение проводить только пленарную часть в очном формате, а все секционные заседания онлайн, но и тем не менее, наши тематические секции по гридам и смежной тематике будут работать в пятницу с самого утра и до самого вечера. С моим участием будет 3 доклада: два из них будут делать мои ученики (по результатам проектирования специализированных вычислительных устройств для умножения бинарных матриц двумя способами — систолически и итерационно с прерываниями), еще двое учеников свои наработки по пандиагональным ЛК и линейкам Голомба до публикации не довели, а жаль (пандиагональные ЛК частично освещу я), а также будет доклад по результатам работы нашего дружного квадратного кружка и проекта RakeSearch
Ватутин Э.И., Никитина Н.Н., Манзюк М.О., Курочкин И.И., Альбертьян А.М. О числе трансверсалей в диагональных латинских квадратах четных порядков // Национальный суперкомпьютерный форум (НСКФ — 2023)
делать который буду я. С презентацией к данному докладу можно ознакомиться тут:
http://evatutin.narod.ru/evatutin_dls_spectra_2023.pdf
Основная мысль доклада — показать обнаруженную недавно интересную особенность в ДЛК четных порядков, а именно то, что по предварительным итогам построения спектров сформулированы 2 не очевидные на первый взгляд гипотезы, на данный момент не имеющие теоретического объяснения:
1. В ДЛК четных порядков N=2k число трансверсалей всегда четно.
2. В ДЛК порядков N=4k+2 число трансверсалей всегда кратно 4.
(Если теоретическое обоснование все же есть или мы переоткрыли Америку, прошу дать об этом знать :).
Кроме того, в докладе планируется коротко осветить другие эксперименты, выполняемые в настоящее время в проекте RakeSearch и не только, а именно:
* текущее состояние экспериментов по спектрам быстровычислимых числовых характеристик ДЛК и ОДЛК;
* промежуточные итоги поиска ОДЛК порядка 10 в окрестностях обобщенных симметрий в парастрофических срезах;
* результаты летнего исследования свойств циклических, различных видов полуциклических, пандиагональных и диагонализированных циклических ЛК/ДЛК;
* промежуточные результаты разработки алгоритмов построения пандиагональных ЛК.
Желающие послушать могут подключаться, соответствующие ссылки будут доступны ближе к началу мероприятия.
О числе "конных" решений тороидальной задачи о ферзях
Возьмем тороидальную доску шахматную доску размером NxN (начало многообещающее, у кого такая есть в загашниках? и построим для нее все решения задачи о ферзях, получаемые движением коня с размером шага (dx,dy), 0<dx,dy<N, стартующего из верхнего левого угла, подсчитаем их количество, в результате чего получится следующий числовой ряд:
1, 0, 0, 0, 2, 0, 4, 0, 0, 0, 8, 0, 10, 0, 0, 0, 14, 0, 16, 0, ...
который нам уже хорошо знаком: он присутствует в OEIS под номером https://oeis.org/A123565 и связан с числом циклических ДЛК с фиксированной первой строкой (но не только). (Как и ранее, стартовать можно с произвольной точки с условием, что для всех формируемых решений данная точка будет одна и та же.) Примеры решений для досок размером 5x5 и 7x7 приведены ниже в соответствии с принятым в OEIS псевдографическим стилем (не моноширинным шрифтом смотрится не очень 
):
a(5)=2:
+-----------+ +-----------+
| Q . . . . | | Q . . . . |
| . . Q . . | | . . . Q . |
| . . . . Q | | . Q . . . |
| . Q . . . | | . . . . Q |
| . . . Q . | | . . Q . . |
+-----------+ +-----------+
a(7)=4:
+---------------+ +---------------+ +---------------+ +---------------+
| Q . . . . . . | | Q . . . . . . | | Q . . . . . . | | Q . . . . . . |
| . . Q . . . . | | . . . Q . . . | | . . . . Q . . | | . . . . . Q . |
| . . . . Q . . | | . . . . . . Q | | . Q . . . . . | | . . . Q . . . |
| . . . . . . Q | | . . Q . . . . | | . . . . . Q . | | . Q . . . . . |
| . Q . . . . . | | . . . . . Q . | | . . Q . . . . | | . . . . . . Q |
| . . . Q . . . | | . Q . . . . . | | . . . . . . Q | | . . . . Q . . |
| . . . . . Q . | | . . . . Q . . | | . . . Q . . . | | . . Q . . . . |
+---------------+ +---------------+ +---------------+ +---------------+
Чтобы получить все решения, получаемые ходом коня с параметрами (dx,dy) из всех возможных начальных точек, необходимо провернуть найденное выше множество решений на торе в одном из направлений на все возможные N смещений, общее число решений при этом вырастет в N раз, в результате чего получится следующий числовой ряд:
1, 0, 0, 0, 10, 0, 28, 0, 0, 0, 88, 0, 130, 0, 0, 0, 238, 0, 304, 0, ...
не присутствующий в OEIS. Удалим из него нули на четных позициях, в результате чего получится следующий числовой ряд:
1, 0, 10, 28, 0, 88, 130, 0, 238, 304, ... — "число решений задачи о ферзях на тородиальной доске с использованием хода коня с параметрами (dx,dy), стартующего из произвольной точки", также не присутствующий в OEIS. Сравнивая количество получаемых решений для досок размером 13x13 и выше, отметим, что далеко не все решения получаются ходом коня. Например, для N=13 "конных" решений при старте из верхнего левого угла получается 10, а общее их количество для данной размерности задачи (аналогично с ферзем в верхнем левом углу) — 348. Пример множества всех "конных" решений для доски 5x5 приведен ниже:
+-----------+ +-----------+ +-----------+ +-----------+ +-----------+
| Q . . . . | | Q . . . . | | . Q . . . | | . Q . . . | | . . Q . . |
| . . Q . . | | . . . Q . | | . . . Q . | | . . . . Q | | Q . . . . |
| . . . . Q | | . Q . . . | | Q . . . . | | . . Q . . | | . . . Q . |
| . Q . . . | | . . . . Q | | . . Q . . | | Q . . . . | | . Q . . . |
| . . . Q . | | . . Q . . | | . . . . Q | | . . . Q . | | . . . . Q |
+-----------+ +-----------+ +-----------+ +-----------+ +-----------+
+-----------+ +-----------+ +-----------+ +-----------+ +-----------+
| . . Q . . | | . . . Q . | | . . . Q . | | . . . . Q | | . . . . Q |
| . . . . Q | | Q . . . . | | . Q . . . | | . Q . . . | | . . Q . . |
| . Q . . . | | . . Q . . | | . . . . Q | | . . . Q . | | Q . . . . |
| . . . Q . | | . . . . Q | | . . Q . . | | Q . . . . | | . . . Q . |
| Q . . . . | | . Q . . . | | Q . . . . | | . . Q . . | | . Q . . . |
+-----------+ +-----------+ +-----------+ +-----------+ +-----------+
Когда же наконец будут пандиагональные ЛК...