Алгоритмы неформально. Инструкция для начинающих питонистов - [17]

entry_i = math.floor(n/2) + 1

entry_j = math.floor(n/2)

square = fillsquare(square,entry_i,entry_j,0)

Если теперь вывести квадрат, то можно увидеть, что он полностью сформирован:

>>> printsquare(square)

         [0]   [1]   [2]   [3]   [4]   [5]   [6]

   [0]    22    47    16    41    10    35     4

   [1]     5    23    48    17    42    11    29

   [2]    30     6    24     0    18    36    12

   [3]    13    31     7    25    43    19    37

   [4]    38    14    32     1    26    44    20

   [5]    21    39     8    33     2    27    45

   [6]    46    15    40     9    34     3    28

Осталось внести одно последнее изменение. Из-за правил оператора % наш квадрат содержит последовательные числа от 0 до 48, а алгоритм Курусимы должен заполнять квадрат целыми числами от 1 до 49. Остается добавить одну строку, которая заменяет в квадрате 0 на 49:

square=[[n**2 if x == 0 else x for x in row] for row in square]

Построение квадрата завершено. Можно убедиться в том, что это действительно магический квадрат, с помощью созданной ранее функции verifysquare():

verifysquare(square)

Функция должна вернуть True — признак того, что проверка прошла успешно.

Мы только что построили магический квадрат 7 × 7 по алгоритму Курусимы. ­Протестируем наш код и проверим, сможет ли он построить больший магический квадрат. Если мы заменим n числом 11 или другим нечетным значением, то можем выполнить тот же код и получить магический квадрат произвольного размера:

n = 11

square=[[float('nan') for i in range(0,n)] for j in range(0,n)]

center_i = math.floor(n/2)

center_j = math.floor(n/2)

square[center_i][center_j] = int((n**2 + 1)/2)

square[center_i + 1][center_j] = 1

square[center_i - 1][center_j] = n**2

square[center_i][center_j + 1] = n**2 + 1 - n

square[center_i][center_j - 1] = n

entry_i = center_i

entry_j = center_j

square = fillsquare(square,entry_i,entry_j,(n**2)/2 - 4)

entry_i = math.floor(n/2) + 1

entry_j = math.floor(n/2)

square = fillsquare(square,entry_i,entry_j,0)

square = [[n**2 if x == 0 else x for x in row] for row in square]

Квадрат 11 × 11 выглядит так:

>>> printsquare(square)

         [0]   [1]   [2]   [3]   [4]   [5]   [6]   [7]   [8]   [9]  [10]

   [0]    56   117    46   107    36    97    26    87    16    77     6

   [1]     7    57   118    47   108    37    98    27    88    17    67

   [2]    68     8    58   119    48   109    38    99    28    78    18

   [3]    19    69     9    59   120    49   110    39    89    29    79

   [4]    80    20    70    10    60   121    50   100    40    90    30

   [5]    31    81    21    71    11    61   111    51   101    41    91

   [6]    92    32    82    22    72     1    62   112    52   102    42

   [7]    43    93    33    83    12    73     2    63   113    53   103

   [8]   104    44    94    23    84    13    74     3    64   114    54

   [9]    55   105    34    95    24    85    14    75     4    65   115

  [10]   116    45   106    35    96    25    86    15    76     5    66

Убедитесь (вручную или с помощью функции verifysquare()), что это действительно магический квадрат. Все это можно проделать для любого нечетного n — и восхититься результатом.

Магические квадраты не имеют большого практического значения, но их закономерности могут быть занимательными. Если вы заинтересовались темой, то предлагаю обдумать следующие вопросы.

• Остается ли в больших магических квадратах, созданных нами, закономерность «чет/нечет» на внешней границе квадрата Ло Шу? Как вы думаете, существует ли эта закономерность во всех возможных магических квадратах? Чем она объясняется (если существует)?

• Не обнаружили ли вы другие закономерности в магических квадратах, созданных нами, которые еще не упоминались?

• Удастся ли вам найти другой набор правил для построения квадратов Курусимы? Например, существуют ли правила для перемещения вверх-вниз по квадрату Курусимы (вместо диагональных перемещений)?

• Существуют ли другие разновидности магических квадратов, которые удовлетворяют определению магического квадрата, но не следуют правилам Курусимы?

• Существует ли более эффективная программная реализация алгоритма Курусимы?

Магические квадраты веками привлекали внимание великих японских математиков, а также занимали значительное место в культурах всего мира. Нам повезло, что великие математики прошлого подарили нам алгоритмы для генерирования и анализа волшебных квадратов, которые легко реализуются на современных мощных компьютерах. В то же время остается только восхищаться терпением и проницательностью великих математиков прошлого, необходимыми для исследования магических квадратов, когда у этих людей не было ничего, кроме пера, бумаги и интеллекта (и появляющихся время от времени волшебных черепах).

Резюме

В данной главе рассматривались некоторые старинные алгоритмы, возраст которых насчитывает от нескольких столетий до нескольких тысячелетий. Читатели, заинтересовавшиеся такими алгоритмами, найдут немало интересных тем для изучения. Возможно, сегодня эти алгоритмы не представляют особой практической ценности, но их определенно стоит изучить — во-первых, они представляют исторический интерес, а во-вторых, помогают расширить наши горизонты и вдохновляют на разработку собственных инновационных алгоритмов.