Алгоритмы генерации магических квадратов (стр. 3 из 5)

Такие квадраты называются ещё пандиагональными.Существует 48 дьявольских магических квадратов 4×4 с точностью до поворотов и отражений. Если принять во внимание еще и их дополнительную симметрию — торические параллельные переносы, то останется только 3 существенно различных квадрата:

Однако было доказано, что из последнего третьего варианта простейшими перестановками чисел получаются первые два квадрата. То есть третий вариант — это базовый дьявольский квадрат, из которого различными преобразованиями можно построить все остальные.

Пандиагональные квадраты существуют для нечётного порядка n>3, для любого порядка двойной чётности n=4k (k=1,2,3…) и не существуют для порядка одинарной чётности n = 4k + 2 (

).

Пандиагональные квадраты четвёртого порядка обладают рядом дополнительных свойств, за которые их называют совершенными. Совершенных квадратов нечётного порядка не существует. Среди пандиагональных квадратов двойной чётности выше 4 имеются совершенные.[2]

Пандиагональных квадратов пятого порядка 3600. С учётом торических параллельных переносов имеется 144 различных пандиагональных квадратов. Один из них показан ниже.

Разломанные диагонали пандиагонального квадрата

Если пандиагональный квадрат еще и ассоциативный, то он носит название идеальный. Пример идеального магического квадрата:

Известно, что не существует идеальных магических квадратов порядка n = 4k+2 и квадрата порядка n = 4. В то же время, существуют идеальные квадраты порядка n = 8. Методом построения составных квадратов можно построить на базе данного квадрата восьмого порядка идеальные квадраты порядка n = 8k, k=5,7,9...и порядка n = 8^p, p=2,3,4... В 2008 г. разработан комбинаторный метод построения идеальных квадратов порядка n = 4k , k = 2, 3, 4,...

1.5 Выводы

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

Глава 2. Механизмы генерации магических фигур

2.1 Составление магических квадратов нечетного порядка

Наибольший практический интерес представляют универсальные методы, которые не зависят от порядка магического квадрата. Такие методы известны для магических квадратов нечетного порядка. Наиболее наглядный из них удобно рассмотреть на примере составления магического квадрата 5-го порядка из натуральных чисел от 1 до 25. Алгоритм этого метода включает следующие шаги. [9]

1. Сначала исходный пустой квадрат достраивается до симметричной ступенчатой ромбовидной фигуры как показано на следующем рисунке, где ячейки для элементов квадрата обозначены символом #, а достроенные ячейки - символом $.

2. Полученная на шаге 1 фигура заполняется по косым рядам сверху-вниз-направо целыми числами от 1 до 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.

2.2 Составление магических квадратов четного порядка

Универсальные методы составления магических квадратов произвольного четного порядка пока неизвестны. Однако, разработаны индивидуальные подходы для различных частных случаев. Ниже рассмотрен метод составления магических квадратов, порядок которых является экспонентой 2. Этот метод удобно рассмотреть на примере магического квадрата 8-го порядка из натуральных чисел от 1 до 64. Метод включает следующую последовательность шагов. [9]

1. Исходный квадрат делится на соответствующее число квадратов порядка 4. В данном случае таких квадратов будет 4. В каждом подквадрате отмечаются диагональные элементы (например, символом #). Остальные элементы построчно заполняются порядковыми целыми числами в направлении слева-направо и сверху-вниз. Числа, приходящиеся на выделенные диагональные элементы должны быть пропущены. Результат заполнения недиагональных элементов квадрата 8-го порядка показан на следующем рисунке:

#	2	3	#	#	6	7	#
9	#	#	12	13	#	#	16
17	#	#	20	21	#	#	24
#	26	27	#	#	30	31	#
#	34	35	#	#	38	39	#
41	#	#	44	45	#	#	48
49	#	#	52	53	#	#	56
#	58	59	#	#	62	63	#

2. Отмеченные на шаге 1 диагональные элементы квадрата заполняют пропущенными целыми числами в порядке возрастания в направлении справа-налево и снизу-вверх. Недиагональные элементы в каждом подквадрате должны быть отмечены (например, символом $), а числа, приходящиеся на них должны быть пропущены. Результат заполнения диагональных элементов для квадрата 8-го порядка показан на следующем рисунке:

64	$	$	61	60	$	$	57
$	55	54	$	$	51	50	$
$	47	46	$	$	43	42	$
40	$	$	37	36	$	$	33
32	$	$	29	28	$	$	25
$	23	22	$	$	19	18	$
$	15	14	$	$	11	10	$
8	$	$	5	4	$	$	1

3. Квадраты с пропусками диагональных и недиагональных элементов, полученные на шагах 1 и 2, объединяются в общий квадрат, где целочисленные элементы подавляют метки # или $. Результат объединения для квадрата 8-го порядка показан на следующем рисунке: