Рассказы о математике | страница 16

И наконец, известный квадрат 4х4, изображенный на гравюре немецкого художника Дюрера “Меланхолия”. Этот квадрат изображен не просто так, 2 числа 1514 указывают на дату создания гравюры.

Как можно видеть, уже математики прошлого умели строить магические квадраты разной размерности. Интересно рассмотреть их свойства.

Сумма чисел магического квадрата размера NxN зависит только от N, и определяется формулой:

Это несложно доказать, т.к. сумма всех чисел квадрата равна сумме ряда 1..N^>2. Действительно, для квадрата Дюрера M(4) = 34, что можно посчитать на картине. Для квадратов разной размерности суммы равны соответственно: M(3) = 15, M(4) = 34, M(5) = 65, M(6) = 111, M(7) = 175, M(8) = 260, M(9) = 369, M(10) = 505.

Напишем программу для построения магических квадратов размерности N. Первый подход будет “в лоб”, напрямую. Создадим массив, содержащий все числа от 1 до N^>2 и получим все возможные перестановки этого массива. Их число довольно-таки велико, и составляет 1*2*..*N = N! вариантов. Также для каждого массива необходимо проверить, является ли он “магическим”, т.е. выполняется ли требование равенства сумм.

Для получения всех перестановок воспользуемся алгоритмом, описанным здесь - https://prog-cpp.ru/permutation/.

Код программы приведен ниже:

def swap(arr, i, j):

arr[i],arr[j] = arr[j],arr[i]

def next_set(arr, n):

j = n - 2

while j != -1 and arr[j] >= arr[j + 1]: j -= 1

if j == -1:

return False

k = n - 1

while arr[j] >= arr[k]: k -= 1

swap(arr, j, k)

l = j + 1

r = n - 1

while l < r:

swap(arr, l, r)

l += 1

r -= 1

return True

def is_magic(arr, n):

for i in range(0, n):

sum1 = 0

sum2 = 0

sum3 = 0

sum4 = 0

for j in range(0, n):

sum1 += arr[i*n + j]

sum2 += arr[j*n + i]

sum3 += arr[j*n + j]

sum4 += arr[(n-j-1)*n + j]

if sum1 != sum2 or sum1 != sum3 or sum1 != sum4 or sum2 != sum3 or sum2 != sum4 or sum3 != sum4:

return False

return True

def show_squares(n):

N = n*n

arr = [i+1 for i in range(N)]

cnt = 0

while next_set(arr, N):

if is_magic(arr, n):

print(arr)

cnt += 1

return cnt

# Требуемая размерность

cnt = show_squares(3)

print("Число вариантов:", cnt)

Программа выдала 8 вариантов для N=3, время вычисления составило 2 секунды:

[2, 7, 6, 9, 5, 1, 4, 3, 8]      [6, 1, 8, 7, 5, 3, 2, 9, 4]

[2, 9, 4, 7, 5, 3, 6, 1, 8]      [6, 7, 2, 1, 5, 9, 8, 3, 4]

[4, 3, 8, 9, 5, 1, 2, 7, 6]      [8, 1, 6, 3, 5, 7, 4, 9, 2]