Н. Макарова

 

НЕТРАДИЦИОННЫЕ ПАНДИАГОНАЛЬНЫЕ КВАДРАТЫ

 

Часть III

 

МЕТОДЫ ПОСТРОЕНИЯ ПАНДИАГОНАЛЬНЫХ КВАДРАТОВ 8-го ПОРЯДКА

 

 

Участие в конкурсе Зиммерманна несколько отодвинуло работу с магическими квадратами. Теперь надеюсь вернуться к теме.

 

В предыдущих частях статьи “Нетрадиционные пандиагональные квадраты” были изложены алгоритмы построения нетрадиционных пандиагональных квадратов порядков 4 – 7. Перехожу к пандиагональным квадратам 8-го порядка. Но прежде чем изложить алгоритмы построения нетрадиционных пандиагональных квадратов данного порядка, расскажу о некоторых методах построения классических пандиагональных квадратов.

 

МЕТОДЫ ПОСТРОЕНИЯ КЛАССИЧЕСКИХ ПАНДИАГОНАЛЬНЫХ КВАДРАТОВ

 

Метод № 1. Этот метод взят из [1]. Автор назвал его методом обобщённых латинских квадратов. Читателям хорошо известен метод латинских квадратов. Если говорится о методе обобщённых латинских квадратов, это означает, что магический квадрат составляется из двух ортогональных обобщённых латинских квадратов. Приведу пример построения из указанной книги (стр. 119). На рис. 1 - 2 вы видите два ортогональных обобщённых латинских квадрата, а на рис. 3 построенный с помощью этих квадратов пандиагональный квадрат. Замечу, что полученный квадрат не только пандиагональный, он ещё и совершенный.

 

 

Рис. 1

 

 

Рис. 2

 

 

Рис. 3

 

Метод № 2. Теперь покажу метод латинских квадратов (не обобщённых, а классических). На рис. 4 - 5 изображены два ортогональных классических латинских квадрата.

 

 

Рис. 4

 

 

Рис. 5

 

Составляем магический пандиагональный квадрат из этих двух ортогональных латинских квадратов (рис. 6):

 

 

Рис. 6

 

Замечание. Ортогональные латинские квадраты взяты из полной группы MOLS, состоящей из 7 попарно ортогональных латинских квадратов (группа построена в Maple М. Алексеевым). В этой группе только два латинских квадрата обладают свойством пандиагональности; эти квадраты и взяты для построения магического пандиагонального квадрата.

 

Метод № 3. Этот метод изложен в статье [2]. Метод позволяет строить пандиагональные квадраты, обладающие свойством ассоциативности, то есть идеальные квадраты, из обратимых квадратов. К любому обратимому квадрату 8-го порядка достаточно применить матричное преобразование, изображённое на рис. 7.

 

 

Рис. 7

 

Возьмём для примера самый простой обратимый квадрат восьмого порядка (мои читатели знают, как составляется такой квадрат) и применим к нему данное матричное преобразование. Получим следующий идеальный квадрат (рис. 8):

 

 

Рис. 8

 

Следует отметить, что указанное матричное преобразование не единственное. Существуют другие матричные преобразования, с помощью которых из обратимых квадратов получаются идеальные квадраты другой структуры. В указанной статье рассматривается ещё матричное преобразование, которое позволяет строить из обратимых квадратов идеальные квадраты, имеющие структуру квадратов, построенных по алгоритму Франклина. 

Кстати, это тоже самостоятельный метод построения пандиагональных и идеальных квадратов – на основе алгоритма Франклина. Не буду здесь приводить этот метод. Читатели могут подробно ознакомиться с ним в статьях, посвящённых квадратам Франклина. Недавно я собрала все эти статьи в один сборник (см. [3]).

 

Метод № 4. Точно так же с помощью матричного преобразования из любого обратимого квадрата 8-го порядка можно построить совершенный магический квадрат 8-го порядка. Этот метод подробно изложен в [4].

На рис. 9 вы видите матричное преобразование, которое достаточно применить к любому обратимому квадрату, чтобы получить совершенный квадрат.

 

 

Рис. 9

 

Возьмём для примера такой обратимый квадрат 8-го порядка (рис. 10):

 

 

Рис. 10

 

Применим к этому обратимому квадрату матричное преобразование, показанное на рис. 9, получим следующий совершенный квадрат (рис. 11):

 

 

Рис. 11

 

Метод № 5. Этот метод из статьи Россера ([5]).

Метод основан на построении примитивного квадрата и применении к нему преобразования, которое в статье задаётся следующей формулой:

 

(1)                                          A(i,j) = B(2i – j, -3i + 2j), где

 

A(i,j) – элементы примитивного квадрата, B(2i – j, -3i + 2j) – элементы пандиагонального квадрата. Индексы вычисляются по модулю 8.

На рис. 12 вы видите примитивный квадрат, построенный в статье.

 

 

Рис. 12

 

Интересно отметить, что этот примитивный квадрат получается из самого простого обратимого квадрата применением преобразования 3-х квадратов.

Применим теперь к этому примитивному квадрату преобразование (1), получим следующий пандиагональный квадрат (рис. 12а):

 

 

Рис. 12а

 

В квадрате выделены так называемые решётки, каждая решётка окрашена одинаковым цветом. Числа, расположенные в решётках, образуют пандиагональные квадраты 4-го порядка с одинаковой магической константой. Это свойство используется при построении нетрадиционных пандиагональных квадратов 8-го порядка, а также 12-го и 16-го (см. [6]).

 

Метод № 6. Этот метод тоже из статьи Россера. Метод можно применять для построения классических пандиагональных квадратов любого порядка n = 4m, m = 2, 3, 4, …

Изложу кратко суть метода. Строятся m² пандиагональных квадратов 4-го порядка по следующей схеме (рис. 13):

 

 

Рис. 13

 

где (A, C), (B, D) в случае n = 8 выбираются произвольным образом из следующих 8 пар чисел (в общем случае пар будет 2m²):

 

(0,60), (4,56), (8,52), (12,48), (16,44), (20,40), (24,36), (28,32)

 

Из построенных пандиагональных квадратов 4-го порядка составляется пандиагональный квадрат 8-го порядка по решёткам Россера (см. изображение решёток на рис. 12а).

 

Приведу пример. Возьмём для пандиагонального квадрата № 1 4-го порядка такие пары: (A,C)=(4,56), (B,D)=(12,48); для квадрата № 2 – (A,C)=(8,52), (B,D)=(16,44); для квадрата № 3 – (A,C)=(20,40), (B,D)=(28,32); для квадрата № 4 – (A,C)=(24,36), (B,D)=(0,60).

Строим пандиагональные квадраты 4-го порядка по схеме, изображённой на рис. 13.

 

Квадрат № 1

 

 

Квадрат № 2

 

 

Квадрат № 3

 

 

Квадрат № 4

 

 

Из полученных пандиагональных квадратов 4-го порядка составляем пандиагональный квадрат 8-го порядка (рис. 14):

 

 

Рис. 14

 

Метод № 7. Это самый простой метод. Он основан на преобразовании 3-х квадратов, применяемом к ассоциативному квадрату. Ассоциативный классический квадрат 8-го порядка можно построить, например, методом квадратных рамок (рис. 15).

 

 

Рис. 15

 

Примечание: описание метода квадратных рамок можно посмотреть в [7] или [8].

 

Теперь применим к ассоциативному квадрату с рис. 15 преобразование 3-х квадратов (это преобразование неоднократно определялось в моих статьях), получим следующий пандиагональный квадрат (рис. 16):

 

 

Рис. 16

 

Интересно, что этот пандиагональный квадрат обладает свойством комплементарности, однако совершенным не является.

 

На этом закончу рассказ о методах построения классических пандиагональных квадратов 8-го порядка. Конечно, здесь перечислены далеко не все методы. В моих ранних статьях вы найдёте ещё некоторые методы, например, метод качелей.

 

МЕТОДЫ ПОСТРОЕНИЯ НЕТРАДИЦИОННЫХ ПАНДИАГОНАЛЬНЫХ КВАДРАТОВ

 

Метод № 1. Этот метод основан на построении примитивного квадрата. Примитивный квадрат для построения пандиагонального квадрата 8-го порядка должен удовлетворять следующим условиям (рис. 17):

 

 

Рис. 17

 

(2)              a + e = b + f = c + g = d + h, a + l = i + m = j + n = k + p

 

Эти свойства аналогичны свойствам, которым должен удовлетворять примитивный квадрат для построения пандиагонального квадрата 4-го порядка.

Очевидно, что примитивный квадрат, изображённый на рис. 12, удовлетворяет этим условиям.

Далее к построенному примитивному квадрату применяется преобразование (1).

Приведу пример пандиагонального квадрата из произвольных натуральных чисел, построенного данным методом. На рис. 18 показан примитивный квадрат из произвольных натуральных чисел.

 

 

Рис. 18

 

В примитивном квадрате есть одинаковые числа, но это не столь важно. Главное, что этот примитивный квадрат удовлетворяет условиям (2). Подбором чисел в первой строке и первом столбце примитивного квадрата нетрудно добиться, чтобы все числа в квадрате были различны. Я просто записала в первой строке и первом столбце произвольно выбранные простые числа.

Применив к примитивному квадрату преобразование (1), получим следующий пандиагональный квадрат (рис. 19):

 

 

Рис. 19

 

Построить пандиагональный квадрат из простых чисел или из смитов данным методом мне не удалось.

 

Замечание. Позже  составила примитивный квадрат, состоящий из различных натуральных чисел (рис. 18а).

 

 

Рис. 18а

 

В этом квадрате больше половины простых чисел. Применяем к этому квадрату преобразование (1) и получаем следующий пандиагональный квадрат (рис. 19а):

 

 

Рис. 19а

 

Метод № 2. Этот метод основан на решётках Россера. Для построения пандиагонального квадрата 8-го порядка достаточно найти четыре пандиагональных квадрата 4-го порядка с одинаковой магической константой. Далее эти квадраты записываются в решётки (см. рис. 12а).

Первый квадрат данным методом мне удалось построить из простых чисел с магической константой 3360. Не показываю пандиагональные квадраты 4-го порядка отдельно, сразу показываю пандиагональный квадрат 8-го порядка, в котором хорошо видны квадраты 4-го порядка в решётках (рис. 20):

 

 

Рис. 20

 

Затем удалось построить пандиагональный квадрат из простых чисел с меньшей магической константой – 2640 (рис. 21).

 

 

Рис. 21

 

Если применить к пандиагональным квадратам с рис. 20 - 21 преобразование обратное преобразованию 3-х квадратов, получатся ассоциативные квадраты. На рис. 22 изображён ассоциативный квадрат, полученный из квадрата с рис. 21.

 

 

Рис. 22

 

Этим свойством обладает любой пандиагональный квадрат 8-го порядка, построенный данным методом.

Из смитов тоже удалось построить пандиагональный квадрат этим методом. На рис. 23 вы видите этот квадрат (подробно о построении этого квадрата см. [6]).

 

 

 

Рис. 23

 

Магическая константа квадрата равна 2720048. С меньшей магической константой пандиагональный квадрат 8-го порядка из смитов построить не удалось.

Точно так же превращаем этот пандиагональный квадрат в ассоциативный с помощью преобразования обратного преобразованию 3-х квадратов (рис. 24):

 

 

Рис. 24

 

Метод № 3. Этот метод разработан мной. В основу метода положено понятие псевдокомплементарных пар, применённое С. Беляевым в его алгоритме для пандиагональных квадратов 6-го порядка. Для разработки схемы (конфигурации) пандиагонального квадрата я взяла классический идеальный квадрат, который вы видите на рис. 25 (этот квадрат построен методом № 3 для классических квадратов, см. рис. 8).

 

 

Рис. 25

 

 

Схема, построенная на основе данного квадрата, выглядит так (рис. 26):

 

 

Рис. 26

 

Имеем 4 группы псевдокомплементарных пар с отклонениями p₁, p₂, p₃, p₄ и 4 группы с обратными отклонениями –p₁, -p₂, -p₃, -p₄. При этом отклонения должны быть связаны так: p₁ = -p₂, p₃ = -p₄. То есть фактически надо всего 4 группы псевдокомплементарных пар – с отклонениями p₁, -p₁, p₃, -p₃. В каждой группе должно быть не менее 8 пар.

Для приведённого на рис. 25 классического идеального квадрата в соответствии с данной конфигурацией имеем такие отклонения от комплементарности: p₁ = 10, p₂ = -10, p₃ = -6, p₄ = 6.

Обозначим элементы групп псевдокомплементарных пар с отклонениями p₁, -p₁, p₃, -p₃: a_i, b_i, c_i, d_i (i = 1,2, …, 8) соответственно. Тогда схема квадрата, заполненная элементами групп, будет иметь следующий вид (рис. 27):

 

 

Рис. 27

 

при этом имеются следующие зависимости:

a_i + a_i’ – K = p₁

b_i + b_i’ – K = -p₁

c_i + c_i’ – K = p₃

d_i + d_i’ – K = -p₃, i = 1, 2, …, 8,

где K = S/4 – константа комплементарности (S – магическая константа квадрата).

 

Общая формула пандиагонального квадрата 8-го порядка имеет 36 независимых переменных. Представленная схема позволила уменьшить количество независимых переменных до 24. Я сомневалась, можно ли реализовать этот алгоритм, реально ли выполнить так много вложенных циклов. Опасения оказались напрасными. Программа работает замечательно, квадраты находятся очень быстро.

 

Пандиагональные квадраты, построенные методом № 2 (см. рис. 20 – 21), тоже вписываются в представленную конфигурацию, только для этих квадратов все отклонения равны 0, так как они составлены из комплементарных пар чисел.

 

С помощью данного метода мне удалось построить несколько пандиагональных квадратов 8-го порядка из простых чисел, при этом нашёлся квадрат с меньшей магической константой, чем квадрат, построенный методом № 2.

Сначала я решила протестировать программу на классических пандиагональных квадратах. Задала комплект отклонений: p₁ = -10, p₃ = 6. Здесь всё просто, в каждой из 4 групп имеем ровно 8 пар чисел. Запустила программу, первый квадрат выдался в долю секунды, этот квадрат показан на рис. 28.

 

 

Рис. 28

 

Убрала в программе выход на конец после первого построенного квадрата, и квадраты посыпались. Прервала программу.  Таким образом, мы имеем ещё один метод построения классических пандиагональных квадратов 8-го порядка.

 

Прежде чем строить нетрадиционные пандиагональные квадраты, сделала в программе небольшую оптимизацию. Она состоит в следующем. Посмотрев на исходный классический идеальный квадрат, на основе которого составлена конфигурация пандиагонального квадрата, увидела, что числа в этом квадрате располагаются очень даже упорядоченно; например, в первой строке имеем: первое число - первое в паре псевдокомплементарных чисел, второе число тоже первое, затем 4 числа - вторые в псевдокомплементарных парах, наконец, два последних числа опять первые. В следующих строках структура повторяется со сдвигом. Тогда я сделала в программе так, чтобы переменные циклов пробегали не все значения в группах псевдокомплементарных пар, а либо только первые значения, либо только вторые, в соответствии со структурой квадрата. Это дало колоссальное ускорение выполнения программы! Потому что все переменные

циклов стали пробегать в два раза меньше значений.

 

В качестве первой магической константы взяла 2632. Константа комплементарности K = 2632/4 = 658. Отклонения взяла такие: p₁ = 8 (31 пара псевдокомплементарных чисел), -p₁ = -8 (20 пар), p₃ = 14 (33 пары), -p₃ = -14 (16 пар). Подчеркну ещё раз, что отклонения надо выбирать так, чтобы в каждой группе псевдокомплементарных пар чисел было не меньше 8 пар. Чем больше пар в группах, тем лучше, быстрее находится квадрат.

Первый квадрат программа нашла за 45 минут. Смотрите квадрат на рис. 29.

 

 

Рис. 29

 

Дальше начала постепенно уменьшать магические константы. Показываю квадраты в порядке их построения.

 

Квадрат № 2. Магическая константа равна 2568. Отклонения: p₁ = 12, p₃ = 54. Группы псевдокомплементарных пар содержат 29, 41, 30 и 29 пар. Очень хорошие подобрались псевдокомплементарные пары. Первый пандиагональный квадрат выдался через 1 секунду (рис. 30).

 

 

Рис. 30

 

Квадрат № 3 (рис. 31). Магическая константа равна 2520.

 

 

Рис. 31

 

Квадрат № 4 (рис. 32). Магическая константа равна 2280.

 

 

 

Рис. 32

Квадрат № 5 (рис. 33). Магическая константа равна 2196.

 

 

Рис. 33

Квадрат № 6 (рис. 34). Магическая константа равна 2000.

 

Рис. 34

 

Квадрат № 7 (рис. 35). Магическая константа равна 1800.

 

Рис. 35

 

Квадрат № 8 (рис. 36). Магическая константа равна 1584.

 

 

Рис. 36

 

Этот квадрат найден не с первой попытки, попытка - это выбор комплекта отклонений. В первой попытке выбрала такие отклонения: p₁ = 18, p₃ = 96. Хотя количества псевдокомплементарных пар с такими отклонениями были довольны большие (21 и 22), квадрат долго не находился. Тогда я взяла другой комплект отклонений: p₁ = 60, p₃ = 96. С такими отклонениями квадрат нашёлся за 3 минуты.

С меньшей магической константой мне не удалось построить пандиагональный квадрат из простых чисел. Напомню, наименьший магический квадрат 8-го порядка из простых чисел имеет магическую

константу 1154.

 

Ещё один интересный квадрат удалось построить данным методом. В этом квадрате все отклонения равны 0, то есть он составлен из комплементарных пар чисел. Магическая константа квадрата равна 2040. Константа комплементарности K = 510. Квадрат построился за 2 минуты. Интересно, что имеем ровно 32 комплементарных пары с такой константой комплементарности.

Смотрите этот квадрат на рис. 37.

 

 

Рис. 37

 

Поскольку этот квадрат составлен из комплементарных пар чисел, его можно превратить в ассоциативный квадрат с помощью преобразования, обратного преобразованию 3-х квадратов. Таким образом, я получила ассоциативный квадрат 8-го порядка из простых чисел с магической константой 2040 (раньше был построен такой квадрат с магической константой 2640). Это наименьшая магическая константа для ассоциативных квадратов 8-го порядка из простых чисел. Ассоциативный квадрат показан на рис. 38.

 

 

Рис. 38

 

Не пробовала пока строить этим методом пандиагональные квадраты из смитов.

Метод № 4. Это метод построения нетрадиционных идеальных квадратов 8-го порядка.

 

Из произвольных натуральных чисел построить идеальный квадрат 8-го порядка очень просто. Достаточно взять 8 арифметических прогрессий длины 8 с одинаковой разностью, таких, что их первые члены образуют арифметическую прогрессию; записать эти прогрессии в виде примитивного квадрата (см. пример на рис. 39), и затем заполнить матрицу 8х8 на основе какого-нибудь классического идеального квадрата (возьмём, например, квадрат с рис. 25), то есть числа в классическом квадрате – это порядковые номера чисел в примитивном квадрате.

 

 

Рис. 39

 

На рис. 40 изображён готовый идеальный квадрат, построенный из чисел данных арифметических прогрессий:

 

 

Рис. 40

 

Однако из простых чисел (и из смитов) таким способом построить идеальный квадрат не удаётся, так как неизвестно 8 нужных арифметических прогрессий. Из простых чисел такие прогрессии, конечно, существуют, но найти их не так просто. Поэтому для идеальных квадратов из простых чисел я разработала специальный метод.

В качестве базового квадрата для разработки метода взяла классический идеальный квадрат, изображённый на рис. 41. То есть придерживалась точно такой структуры квадрата при составлении программы (при выборе первого или второго числа из комплементарной пары).

 

 

Рис. 41

 

В общей формуле идеального квадрата 8-го порядка 18 независимых переменных (при заданной магической константе), мне удалось уменьшить количество независимых переменных до 15, используя различные зависимости, в том числе и по решёткам Россера.

Понятно, что идеальный квадрат 8-го порядка можно построить только из такого массива, в котором есть не менее 32 комплементарных пар чисел.

Общая схема идеального квадрата очень простая (рис. 42):