Рассказы о математике с примерами на языках Python и C | страница 16
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 дней!
Однако посмотрим на магический квадрат еще раз:
Суммы всех элементов по горизонтали и вертикали равны. Из этого мы легко можем записать равенство его членов:
x11 + x12 + x13 + x14 = x21 + x22 + x23 + x24
x11 + x12 + x13 + x14 = x14 + x24 + x34 + x44
x11 + x12 + x13 + x14 = x13 + x23 + x33 + x43
x11 + x12 + x13 + x14 = x12 + x22 + x32 + x42
x11 + x12 + x13 + x14 = x11 + x21 + x33 + x44
x11 + x12 + x13 + x14 = x31 + x32 + x33 + x34
И наконец, общая сумма: т.к. квадрат заполнен числами 1..16, то если сложить все 4 строки квадрата, то получаем 4S = 1+..+16 = 136, т.е. S=34 (что соответствует приведенной в начале главы формуле).
Это значит, что мы легко можем выразить последние элементы через предыдущие:
x14 = S - x11 - x12 - x13
x24 = S - x21 - x22 - x23
x34 = S - x31 - x32 - x33
x41 = S - x11 - x21 - x31
x42 = S - x12 - x22 - x32
x43 = S - x13 - x23 - x33
x44 = S + x14 - x14 - x24 - x34