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

Однако посмотрим на магический квадрат еще раз:

Суммы всех элементов по горизонтали и вертикали равны. Из этого мы легко можем записать равенство его членов:

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

Что это дает? Очень многое. Вместо перебора 16 вариантов суммарным количеством 16!=20922789888000 мы должны перебрать лишь 9 вариантов, что дает 9!=362880 вариантов, т.е. в 57657600 раз меньше! Как нетрудно догадаться, мы фактически выразили крайние строки квадрата через соседние, т.е. уменьшили размерность поиска с 4х4 до 3х3. Это же правило будет действовать и для квадратов большей диагонали.

Обновленная программа выглядит более громоздко (в ней также добавлены проверки на ненулевые значения и проверки на уникальность элементов), зато расчет происходит в разы быстрее. Здесь также используется возможность работы со множествами в языке Python, что легко позволяет делать перебор нужных цифр в цикле:

set(range(1,16+1)) - множество чисел [1..16]

set(range(1,16+1)) - set([x11]) - множество чисел [1..16] за исключением x11.

Также добавлена простая проверка на минимальность суммы: очевидно, что сумма всех элементов не может быть меньше чем 16+1+2+3 = 22.

digits = set(range(1,16+1))

cnt = 0

for x11 in digits:

for x12 in digits - set([x11]):

for x13 in digits - set([x11, x12]):

for x14 in digits - set([x11, x12, x13]):

s = x11 + x12 + x13 + x14

if s < 22: continue

for x21 in digits - set([x11, x12, x13, x14]):

for x22 in digits - set([x11, x12, x13, x14, x21]):

for x23 in digits - set([x11, x12, x13, x14, x21, x22]):

x24 = s - x21 - x22 - x23

if x24 <= 0 or x24 in [x11, x12, x13, x14, x21, x22, x23]: continue