Всем доброго времени суток.
В этой статье я опишу метод получения нормальных магических квадратов порядка nm, где n и m - положительные натуральные числа, при условии, что нам известен нормальный магический квадрат порядка n
Однажды, еще в школе, я заинтересовался магическими квадратами, как весьма хардкорной заменой судоку. По-сути, все свободное время в школе я проводил за составлением магических квадратов. Здесь и в дальнейшем, под магическим квадратом я подразумеваю нормальный магический квадрат.
Как это начиналось
Я никогда не изучал магические квадраты, составленные ранее, изображения которых были в открытом доступе, и не следовал известным "рецептам".
Алгоритм, которого я придерживался был прост, хотя и весьма сложен в исполнении, учитывая, что все это происходило на обычной тетрадной бумаге в клетку:
Рисуем квадрат и вписываем в него числа от 1 до n2, где n - сторона квадрата, по порядку, построчно, слева направо, сверху вниз.
Подписываем исходные суммы в строках, столбцах и диагоналях.
Выписываем два столбца, расположенных симметрично относительно центра квадрата.
Меняем местами числа в столбцах до тех пор, пока суммы чисел не окажутся равны (следуя интуиции и расчетам). Здесь стоит отметить, что этот алгоритм подходит только для ассоциативных магических квадратов, но об этом я тогда не знал, из-за чего серьезно застрял на квадрате 6х6.
Рядом с исходным квадратом рисуем пустой квадрат, в котором стрелками соединяем клетки, числа в которых "переехали".
Применяем схему перемещения чисел к строкам, находящимся на таком же удалении от центра и проверяем суммы в строках.
Хотел бы я сформулировать и этот пункт, но, боюсь, здесь начинается подгонка: скрупулезно подсчитывая суммы, менять местами числа, находящиеся на одинаковом удалении от центра, считая по количеству строк/столбцов.
Итак, после выполнения этих шагов, тетрадный лист порой оказывался полностью исписанным: множество "черновых" квадратов, нерабочих моделей перемещения чисел (схем со стрелками), и в конце, если повезет, готовый магический квадрат и рабочая схема перемещения чисел. Здесь стоит упомянуть, что если в ассоциативном магическом квадрате поменять местами два столбца, находящихся на удалении L от центра, а затем поменять местами две строки, также находящиеся на удалении L, то квадрат останется магическим и ассоциативным, но схема перемещения чисел изменится.
С маленькими квадратами все было донельзя просто (n=3 и n=4), и меня заинтриговали схемы, получающиеся в итоге. Это были симметричные рисунки, в которых мне виделось нечто загадочное. Загадкой для меня было скорее не то, отчего они так выглядят, а то, какие рисунки получатся от квадратов с большими сторонами, отчего я сразу перешел к квадратам 5х5, 6х6, 7х7 и 9х9.
Времени, бумаги и чернил уходило немерено, но я справился со всеми ими, кроме 6х6. Порывшись в интернете, я обнаружил, что к моему большому сожалению, ассоциативных квадратов 6х6 не существует. Заодно узнал, что такое ассоциативный магический квадрат :)
Закончив с квадратом 9х9, я понял, что бумаги уходит реально много: на один тетрадный лист помещалось только три-четыре таких квадрата, а учитывая мою любовь к зарисовыванию стрелочками "путей чисел", места оставалось еще меньше.
Кстати, зарисовыванием я занимался не просто так: такая схема была для меня способом, с помощью которого, в дальнейшем, можно быстро повторить этот же квадрат. Также я обнаружил, что некоторые числовые последовательности, будучи записанными в квадрат по этой схеме, также составляли ассоциативный магический квадрат, что меня порядком удивило. Это относится, например, к четным и нечетным положительным числам, а также к любым целым числам, идущим по возрастанию или убыванию.
Сразу скажу, что этот способ не работает с квадратами натуральных чисел, или степенями одного числа. Было бы неплохо, ведь за нахождение некоторых квадратов даже назначена награда.
Наши дни
Забросив рисование квадратов на первом курсе, отучившись, отслужив в армии и устроившись на работу, в один из долгих зимних вечеров, от нечего делать, я решил систематизировать свои знания о магических квадратах. К моему большому огорчению, все мои записи о магических квадратах пропали, и я едва не опустил руки. Нарисовав самый простой квадрат 3х3, я нарисовал рядом его схему перемещения, или "шаблон". Как истинно ленивый программист, я подумал: что, если применить этот шаблон к базовому квадрату 9х9, разделив его на 9 секторов, по три строки и столбца, а затем применить этот же шаблон к каждому сектору. Что, если получится магический квадрат?
По-быстрому нарисовав базовый квадрат, я быстро исполнил задуманное и с замиранием сердца взялся за калькулятор. Не было предела моему удивлению, когда я понял, что действительно получил ассоциативный магический квадрат!
Следующей моей идеей было проверить шаблон на квадрате 27х27, но одна мысль о том, что мне придется от руки прописывать 729 чисел от 1 до 729, вернула меня с небес на землю. Страшно было даже не то, что придется все прописывать, а то, что, если я ошибусь, придется все переделывать заново, а без нарисованного базового квадрата (в котором числа идут по-порядку) вероятность ошибки возрастала в разы... Но я не сдался. Зачем писать все вручную, если можно написать программу, которая все сделает за тебя?
NumPy + PyGame = Profit!
Итак, собственно, код. Для написания программы использовался Python версии 3.9 и opensource-библиотеки Numpy и PyGame.
import numpy as np
import pygame as pgБазовый квадрат для магического - это элементарная матрица, где mx,y == x + y * n + 1, где n - длина стороны квадрата. Напишем функцию-генератор:
def create_matrix(n: int):
return np.arange(1, n ** 2 + 1).reshape(n, n)Далее я записал шаблоны магических квадратов 3x3 и 4x4, в виде списка последовательностей перестановок:
m_3 = [[[1, 0], [0, 0], [1, 2], [2, 2]], [[2, 0], [2, 1], [0, 2], [0, 1]]]
m_4 = [[[0, 0], [2, 2]], [[1, 0], [0, 1]],
[[2, 0], [3, 1]], [[3, 0], [1, 2]],
[[0, 2], [1, 3]], [[1, 1], [3, 3]],
[[2, 1], [0, 3]], [[3, 2], [2, 3]]]Затем, после вдумчивого разбора предлагаемого NumPy функционала, были созданы функции для разбивания матрицы на сектора, и обратной сборки:
# _m - input matrix, _x - base row length
def m_split(_m, _x):
return [np.vsplit(x, _x) for x in np.hsplit(_m, _x)]
# _m - input "previous splitted" matrix, _x - base row length
def m_join(_m, _x):
return np.vstack([np.hstack(np.vstack(_m)[x::_x]) for x in range(_x)])После чего реализованы функции, выполняющие последовательную перестановку и цепь перестановок, в соответствии с шаблоном:
# _m - input "previous splitted" matrix, idxs - indices of matrix cells.
def m_rot(_m, idxs):
# [-----X----][-----Y----]
a0 = _m[idxs[0][0]][idxs[0][1]]
for i in range(len(idxs) - 1):
_m[idxs[i][0]][idxs[i][1]] = _m[idxs[i + 1][0]][idxs[i + 1][1]]
_m[idxs[-1][0]][idxs[-1][1]] = a0
return _m
#_m - input "previous splitted" matrix, _steps - pattern of digits swaps (m_3, m_r, ...)...
def magic_steps(_m, _steps):
m0 = _m
for step in _steps:
m0 = m_rot(m0, step)
return m0И, наконец, функция генерации магического квадрата со стороной npow:
# _mss - magic steps (m_3, m_4, or ...)
def pow_square(_root, _pow, _mss):
m_dmag = lambda x, d: m_join(magic_steps(m_split(x, d), _mss), d)
_p = _root ** _pow
m0 = m_dmag(create_matrix(_p), _root)
for i in range(1, _pow):
m0 = m_join([[m_dmag(x, _root) for x in y] for y in m_split(m0, _root ** i)], _root ** i)
return m0Чтобы потешить ностальгию, и нарисовать глобальный шаблон для полученного на выходе квадрата, я использовал библиотеку PyGame, как в разы более шуструю альтернативу модулю turtle, который я по недоразумению попытался использовать вначале:
# returns list of [list of coordinates for all moved digits in move-chain]
def get_cycles(_m):
ret = []
dim = len(_m)
used = []
j_to_xy = lambda _j, _d: [(_j - 1) % _d, int((_j - 1) / _d)]
xy_to_j = lambda _xy, _d: _xy[0] + _xy[1] * _d + 1
for j in range(1, dim * dim + 1):
_p = []
x, y = j_to_xy(j, dim)
if _m[y][x] in used:
continue
if _m[y][x] == j:
used += [_m[y][x]]
continue
_p += [[x, y]]
while True:
a = _m[y][x]
x, y = j_to_xy(a, dim)
_p += [[x, y]]
used += [a]
if xy_to_j([x, y], dim) == j:
ret += [_p]
break
return ret
# returns list of digits, that's just stay on their base coordinates.
def get_statics(_m):
dim = len(_m)
j_to_xy = lambda _j, _d: [(_j - 1) % _d, int((_j - 1) / _d)]
ret = []
for j in range(1, dim * dim + 1):
x, y = j_to_xy(j, dim)
if _m[y][x] == j:
ret += [[x, y]]
return ret
# drawing function.
def to_star(_m):
# compute optimal window width\height (d_sz) and step length multiplier (sz)...
dim = len(_m)
max_sz = 1000
_sz = int(max_sz / dim)
sz = 20 if _sz > 20 else 1 if _sz == 0 else _sz
d_sz = (sz * dim + 20, sz * dim + 20)
# initialize PyGame window and drawing field:
pygame.init()
_sc = pygame.display.set_mode(d_sz)
_sc.fill((255, 255, 255))
pg.display.flip()
# begin drawing
for _c in get_cycles(_m):
sc = _sc.convert_alpha()
sc.fill([0, 0, 0, 0])
# scale coordinates with computed step length multiplier (sz)
# last point excluded, as it is equals to the first.
points = [(x * sz + 10, y * sz + 10) for x, y in _c[:-1]]
# draw line or polygon between the coordinates of the moved numbers
# lines have 55% opacity.
r = pg.draw.lines(sc, (0, 0, 0, 15), True, points) \
if len(points) > 2 \
else pg.draw.line(sc, (0, 0, 0, 55), points[0], points[1])
_sc.blit(sc, (0, 0))
pg.display.update(r)
for _s in [(x * sz + 10, y * sz + 10) for x, y in get_statics(_m)]:
# draw small yellow circle on the coordinates of the numbers
# that have retained their positions
r = pg.draw.circle(_sc, (200, 200, 0, 70), _s, 5)
pg.display.update(r)
# end drawing, wait for exit.
c = pg.time.Clock()
while True:
c.tick(60)
for events in pg.event.get():
if events.type == pg.QUIT:
pg.quit()
pygame.display.update()И в конце - функция main, которая, собственно и соберет все это в кучу и запустит:
if __name__ == '__main__':
pow = 3
root = 4
m1 = pow_square(root, pow, m_4)
try:
to_star(m1)
except pygame.error:
print('Drawing finished.')
print(m1)
# Compute sums of all digits in rows, columns and diagonals.
m2 = np.rot90(m1)
print([sum(x) for x in m1])
print([sum(x) for x in m2])
print(sum([m1[x, x] for x in range(root ** pow)]))
print(sum([m2[x, x] for x in range(root ** pow)]))Быстрая проверка показала, что метод действительно работает. И при этом - не только на 3х3, но и на 4х4, 5х5, и, скорее всего, на всех других натуральных магических квадратах. Мой метод получения ассоциативных магических квадратов порядка 3n, 4n и 5n безукоризненно работает, и без проблем сработает с любым другим натуральным магическим квадратом (причем, не обязательно ассоциативным - все зависит только от заложенного шаблона)!
Несколько примеров работы программы
Оригинал магического квадрата порядка 81 (.csv)
Исходный код программы на GitHub
Примечание: программа работает довольно медленно с квадратами порядка > 1000. Не рекомендуется запускать на слабых ПК при больших размерностях. Подвисает во время отрисовки.
P.S. Скорее всего, код представленный в статье, имеет огромное количество точек оптимизации, и, вероятно, следовало обрабатывать матрицу многопоточно, но так как этот код практически не имеет иной области применения, кроме демонстрации метода генерации магических квадратов, он оставлен, как есть. Заранее извиняюсь за некоторое отсутствие эстетики в коде...
