Рассказы о математике | страница 16
Сумма чисел магического квадрата размера 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]
[4, 9, 2, 3, 5, 7, 8, 1, 6] [8, 3, 4, 1, 5, 9, 6, 7, 2]
Действительно, как известно, существует только 1 магический квадрат 3х3:
Остальные являются лишь его поворотами или отражениями (очевидно что при повороте квадрата его свойства не изменятся).
Теперь попробуем вывести квадраты 4х4. Запускаем программу… и ничего не видим. Как было сказано выше, число вариантов перебора для 16 цифр равняется 16! или 20922789888000 вариантов. На моем компьютере полный перебор такого количества занял бы 1089 дней!
