Под магическим квадратом порядка 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.
Программирование магических квадратов
Для программирования магических квадратов удобно использовать парадигму инкапсуляции объектно-ориентированного программирования, сосредоточив "магические" структуры данных и методы их обработки в отдельном классе Magic. В класс Magic рекомендуется включить следующие приватные (privat) компоненты - данные:

unsigned degree - порядок квадрата;

unsigned basic, differ - начальный элемент и разность арифметической прогрессии натуральных чисел, заполняющих магический квадрат;

unsigned **tab - указатель на двумерный массив беззнаковых целых чисел, который должен содержать матрицу магического квадрата.

Для обработки приватных данных в классе Magic целесообразно предусмотреть следующие общедоступные (public) компонентные методы:

void magodd( ) - формирует магический квадрат нечетного порядка;

void mageven2( ) - составляет магический квадрат четного порядка, у которого порядок является экспонентой 2;

int chksum( ) - вычисляет контрольные суммы элементов столбцов, строк и главных диагоналей квадрата, возвращая величину константы квадрата или 0, если квадрат не является магическим;

void print( ) - отображает матрицу и константу магического квадрата в потоке стандартного вывода;

void magbuild( ) - вызывает метод составления, соответствующий порядку магического квадрата.

Для инициализации компонент-данных в классе Magic следует предусмотреть конструктор. Конструктор класса Magic должен иметь возможность принимать 3 аргумента, определяющих порядок, начальный элемент и разность арифметической прогрессии элементов магического квадрата. При декларации конструктора рекомендуется указать значения аргументов по умолчанию:
Пример 1
class Magic { 
...................... 

public: 

Magic(unsigned=3, unsigned=1, unsigned=1); 

..................... 

}; 

Это позволит для создания объектов класса Magic использовать вызов конструктора в сокращенном формате; с одним , двумя или без аргументов. Например, следующий вызов конструктора:

Magic loshoo;

является корректным для составления магического квадрата ло-шу, где приватные компоненты-данные degree, basic, differ по умолчанию инициализируются величинами 3, 1, 1, соответственно. Кроме инициализации целочисленных компонент-данных конструктору класса Magic желательно поручить динамическое распределение памяти, необходимое для хранения 2-мерного массива элементов магического квадрата tab. Для динамического распределения памяти под 2-мерный массив рекомендуется использовать следующую 2-х этапную схему:

1. распределить память под 1-мерный массив указателей на беззнаковые целые размером degree по адресу tab используя оператор new:

tab=new unsigned *(degree);

2. под каждый указатель полученного массива указателей распределить одномерный массив беззнаковых целых из degree элементов, используя оператор new в цикле:

for (int i=0; i<degree;i++)

tab[i]=new unsigned(degree);

Рассмотренный способ формирования 2-мерного массива позволит обращаться к любому j-му элементу i-й строки в компонентных методах класса Magic традиционным образом tab[i][j]. Вызов компонентных методов составления магического квадрата может быть реализован в теле конструктора класса Magic, а обращение к компонентному методу отображения результатов целесообразно организовать в основной функции программы magic.

После завершения требуемой обработки и отображения результатов объекты класса Magic должны быть уничтожены с помощью деструктора ~Magic( ). Деструктор класса Magic должен освободить память, динамически распределенную конструктором по адресу tab для хранения 2-мерного массива элементов магического квадрата. Рекомендуется освобождать память по схеме обратной ее распределению, используя оператор delete:

1. освободить память, распределенную под degree одномерных массивов беззнаковых целых (из degree элементов каждый) по адресам от tab[0] до tab[degree-1]:

for (int i=0; i<degree; i++)

delete [degree](tab[i]);

2. освободить память, распределенную под 1-мерный массив указателей на беззнаковые целые, состоящий из degree указателей по адресу tab:

delete [degree]tab;
Обычно деструктор вызывается неявно при завершении работы с объектом класса, например, после выхода из блока, где объект был определен. При необходимости явного вызова деструктора в обращении к нему должно быть специфицировано имя класса, которому он принадлежит:

Magic mag(4);

mag.Magic::~Magic( );

В соответствии с принципами структурного программирования следует разместить декларацию класса Magic в отдельном заголовочном h-файле. Исходный код компонентных методов класса Magic и основной функции main( ) программы magic, которая оперирует ими, рекомендуется разместить в 2-х отдельных файлах. Для успеха трансляции в каждый из них нужно включить заголовочный файл класса Magic, используя директиву include.