Обычно выбирают целые числа 1, 2, . . ., N. На рис. 6.1.1, с показан единственный магический квадрат порядка 3. Мы исследуем алгоритмы построения нечетных и дважды четных {N=4 т, т=\, 2, 3, . . .) магических квадратов. Однократно четный случай (Ж=4т-(-2, т=1, 2, 3, . . .) будет оставлен в качестве упражнения.

ff г

Ркс. 6.1.1. Построение магического квадрата порядка 3.

Нечетные магические квадраты (N=2m-\, т=0, 1, 2, ...). Следующая процедура будет порождать магический квадрат для нечетного N. Поместим число 1 в центральную позицию верхней строки. Затем перейдем вверх на квадрат и вправо на один квадрат для размещения следующего числа. Это перемещение может вывести нас за пределы массива, но простая схема на рис. 6.1.1, б показывает, куда на самом деле приводит нас такое перемещение при построении магического квадрата порядка 3. Это перемещение «вверх и вправо на один» - основная операция при построении магических квадратов нечетного порядка. Однако при каждом N-m перемещении мы сдвигаемся на позицию вниз при размещении очередного числа (рис. 6.1.1, е). Завершающие перемещения при построении магического квадрата порядка 3 показаны на рис. 6.1.1, г.

Algorithm ODDMS (магический квадрат нечетного порядка) для построения магического квадрата нечетного порядка N. Шаг 0. [Инициализация] Set /1; and / ч-(yV4-l)/2. Шаг 1. [Цикл] For COUNT ч- 1 to iV do through шаг 3 od; and STOP.

Шаг 2. [Присваивание! Set SQUARE (/, COUNT. Шаг 8. [Отыскание следующей позиции]

n(COUNT) MOD (iV)=0

then set /+1

else if /=1 then set I N else set / -t- /-1 fi; and if J=N then set / 1 else set J J+l fi fi.

Для демонстрации правильности алгоритма ODDMS удобно рассматривать все целые mod{Ny). Для всех целых от 1 до Л определим части X и F как F= (-1) mod(A)-f 1 и X=k-Y (заметим, что k=X+ +Y). На рис. 6.1.2 показаны части X и У для целых чисел от 1 до 9 в магическом квадрате 3x3.

В последующем обсуждении удобнее представлять себе квадрai NxN нарисованным на торе. Столбцы 1 и N окажутся соседними как и строки 1 и N.

Так как детальное доказательство для алгоритма ODDMS довольно утомительно, мы выделим только тот факт, что алгоритм размещает целые числа от 1 до N так, что суммы по строкам и по столбцам равны. Утверждение

относительно диагональных сумм будет остав- рис. 6.1.2. Части (X, Y) лено в качестве упражнения. целыхчисел fe=l, 2,...

Целые числа от 1 до N можно считать • • ., 9, где x=k-Y и расположенными в виде N групп по N последо- У={к-1) mod {N)+l нательных чисел. В каждой группе части X постоянны, а части Y изменяются от 1 до N. Целые числа в каждой группе размещены в виде массива NxN таким образом, что в каждой строке и в каждом столбце содержится в точности один член этой группы. Это следует из того, что алгоритм размещает все числа в каждой группе последовательно, и из того, что координаты каждого числа отличаются на единицу от координат предыдущего, т. е. если k помещается в позиции (/, J), то k+l помещается в (/-1, Следовательно, алгоритм размещает числа таким образом, что одни только части X сами образуют магический квадрат.

В каждой группе части Y являются числами от 1 до Л, размещенными Б квадратах последовательно. Рассмотрим расположение всех чисел с частью У, равной 1 (рис.6 .1.2). Если некоторая единица расположена в (Л, /i), то следующая часть У=1 находится в (/i+2, Ji-l). Это следует из того, что последний член первой группы (Y=N) помещается в (/i-f 1, Л-1), а затем алгоритм «спускается» для размещения первого числа из следующей группы. Читателю следует убедиться, что алгоритм помещает К=1 в каждую строку и каждый столбец. Аналогичные доводы можно привести за то, что Y=j, /=1, . . ., N, помещается в каждую строку и в каждый столбец. Следовательно, части У сами по себе образуют магический квадрат.

) По определению, если с (mod т]=х для целых о и т, то д: - целый остаток от деления а на т. Например, 5 (mod 31=2.

Дважды четные магические квадраты (N=4m, m=0, I, 2, ...).

Этот алгоритм несколько сложнее алгоритма ODDMS. Мы начинаем с одного квадранта со стороной 2т, где N~4m для некоторого положительного целого т. Ради удобства выберем левый верхний квадрант. Теперь пометим Ат квадратов из этого квадранта произвольным образом, но так, чтобы в каждой строке и каждом столбце оказались помеченными в точности т квадратов. Для т=2 это показано на рис. 6.1.3, а.

5 6 7 S

4 S 6

Рис. 6.1.3. Построение магического квадрата порядка 8.

Теперь отразим эти пометки относительно вертикальной оси симметрии на правый верхний квадрант, а затем относительно горизонтальной оси симметрии на нижний левый квадрант. После этого отразим эти пометки в правый нижний квадрант относительно диагонали, идущей из нижнего левого угла в правый верхний. В результате получим множество пометок, показанное на рис. 6.1.3, б.

Просмотрим все квадраты слева направо и сверху вниз. Если квадрат не имеет пометки, поместим в него первое еще невыбранное число К из последовательности 1, 2, . . ., и поместим число (N->-l)-К