2020-04-07
171
Под магическим квадратом порядка N понимается квадратная матрица размером NxN из N в квадрате последовательных элементов произвольной арифметической прогрессии натуральных чисел, которые размещены так, что суммы элементов любого столбца, строки или главной диагонали одинаковы. Результат вычисления любой из перечисленных сумм принято называть константой магического квадрата. Порядок магического квадрата определяется числом элементов любого столбца или строки. Например, магический квадрат 3-го порядка из 9-ти 1-х натуральных чисел (известный в Китае как талисман ло-шу) представляется следующей матрицей 3x3:
4 9 2
3 5 7
8 1 6
Константа квадрата ло-шу равна 15. Это единственный квадрат 3-го порядка, который можно построить из натуральных чисел от 1 до 9, если не использовать преобразования поворота и отражения. Классический образец магического квадрата 4-го порядка, известный еще в Древней Индии, представляется следующей матрицей 4x4:
1 14 15 4
12 7 6 9
8 11 10 5
13 2 3 16
Константа "индийского" квадрата равна 34. В несколько измененном виде (достигаемом перестановкой строк и столбцов):
|
|
|
16 3 2 13
5 10 11 8
9 6 7 12
4 15 14 1
он известен художникам по философской гравюре А. Дюрера "Меланхолия". Астрологи средних веков приписывали числовым сочетаниям магических квадратов таинственные и волшебные свойства. Современных математиков и программистов интересуют формальные методы составления магических квадратов.
Составление магических квадратов нечетного порядка
Наибольший практический интерес представляют универсальные методы, которые не зависят от порядка магического квадрата. Такие методов известны для магических квадратов нечетного порядка. Наиболее наглядный из них удобно рассмотреть на примере составления магического квадрата 5-го порядка из натуральных чисел от 1 до 25. Алгоритм этого метода включает следующие шаги:
1. Сначала исходный пустой квадрат достраивается до симметричной ступенчатой ромбовидной фигуры как показано на следующем рисунке, где ячейки для элементов квадрата обозначены символом #, а достроенные ячейки - символом $.
$
$ $ $
# # # # #
$ # # # # # $
$ $ # # # # # $ $
$ # # # # # $
# # # # #
$ $ $
$
2. Полученная на шаге 1 фигура заполняется по косым рядам сверху-вниз-направо целыми числами от 1 до 25 в натуральном порядке. Результат заполнения показан на следующем рисунке:
1
6 $ 2
11 # 7 # 3
16 # 12 # 8 # 4
21 $ 17 # 13 # 9 $ 5
22 # 18 # 14 # 10
23 # 19 # 15
24 $ 20
25
3. Каждое число, расположенное в фигуре шага 2 вне исходного квадрата, переносится по вертикали или горизонтали внутрь исходного квадрата на число позиций, равное порядку квадрата. В рассматриваемом примере перенос осуществляется на 5 позиций. Таблица переносов имеет следующий вид:
|
|
|
1 - вниз под 13; 2 - вниз под 14; 6 - вниз под 18;
21 - вправо за 13; 22 - вправо за 14; 16 - вправо за 8;
5 - влево перед 13; 4 - влево перед 12; 10 - влево перед 18;
25 - вверх над 13; 24 - вверх над12; 20 - вверх над 8.
Освобождающиеся ячейки, достроенные к исходному квадрату заполняются символом $.
4. После преобразований переноса на шаге 3 освободившиеся ячейки (заполненные символом $) должны быть исключены. Оставшиеся (внутренние) ячейки (заполненные натуральными числами) образуют магический квадрат, представленный следующей матрицей 5x5:
11 24 7 20 3
4 12 25 8 16
17 5 13 21 9
10 18 1 14 22
23 6 19 2 15
константа которого равна 65, что может быть проверено вычислением суммы элементов для столбцов, строк и главных диагоналей.
Рассмотренный метод составления нечетных магических квадратов не является единственным. Не менее известным и не более сложным является следующий алгоритм, предложенный С. Лубером. Правила алгоритма Лубера удобно иллюстрировать на примере магического квадрата порядка 7 из натуральных чисел от 1 до 49, матрица 7x7 которого показана на следующем рисунке:
28 19 10 01 48 39 30
29 27 18 09 07 47 38
37 35 26 17 08 06 46
45 36 34 25 16 14 05
04 44 42 33 24 15 13
12 03 43 41 32 23 21
20 11 02 49 40 31 22
В основе алгоритма Лубера лежит заполнение ячеек квадрата в направлении вверх и влево по диагонали последовательными числами выбранной арифметической прогрессии. Заполнение начинается со среднего элемента верхней строки (01). Если следующая левая диагональная ячейка уже занята числом (ячейка 01 уже занята в момент заполнения ячейки 07), нужно перейти к нижнему соседу (08) текущей заполненной ячейки (07) и продолжить движение по диагонали. Чтобы избежать возможности выхода за границы квадрата при диагональном движении его надо мысленно превратить в тор, соединив верхнюю горизонталь с нижней, а затем соединить основания полученного цилиндра. После свертки строки, столбцы и диагонали квадрата превращаются в замкнутые кривые на поверхности тора и выход за границы квадрата становится невозможным. Превращение квадрата в тор в данном случае обеспечивает возможность диагонального перехода, например, из ячейки 01 в ячейку 02 или из ячейки 45 в ячейку 46.
