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

def rule1(x,n,upright):

    return((x + ((-1)**upright) * n)%n**2)

В математическом выражении Python интерпретирует True как 1, а False как 0. Если аргумент upright равен False, то наша функция вернет то же значение, что и прежде, так как (–1)0 = 1. Если аргумент upright равен True, то функция будет вычитать n вместо того, чтобы прибавлять, и это позволит нам идти в другом направлении. Проверим, сможет ли функция определить значение справа и выше от 1 в квадрате Ло Шу:

print(rule1(1,3,True))

Функция должна вывести 7, правильное значение из квадрата Ло Шу.

Аналогичная функция создается и для правила 2. Функция для правила 2 получает аргументы x и n, как и функция для правила 1. Но функция для правила 2 по умолчанию изменяет ячейка ниже и правее x. А значит, мы будем прибавлять аргумент upleft, который будет равен True, если вы захотите изменить направление правила. Итоговое правило выглядит так:

def rule2(x,n,upleft):

    return((x + ((-1)**upleft))%n**2)

Функцию можно протестировать на квадрате Ло Шу, хотя в нем всего две пары ячеек, которые не сталкиваются с исключением из правила 2. Для этого исключения можно написать следующую функцию:

def rule3(x,n,upleft):

    return((x + ((-1)**upleft * (-n + 1)))%n**2)

Правило должно соблюдаться только при пересечении антидиагонали магического квадрата. Позднее вы увидите, как определить, пересекается ли антидиагональ.

Итак, теперь мы знаем, как заполнить пять центральных квадратов, и у нас есть правила для заполнения остальных ячеек по известным центральным ячейкам. Можно переходить к заполнению квадрата.

Заполнение остальных ячеек квадрата

Один из способов заполнить остальные ячейки — обойти его случайным образом, используя известные ячейки для заполнения неизвестных. Сначала определим индексы центральной ячейки:

center_i = math.floor(n/2)

center_j = math.floor(n/2)

Затем можно случайным образом выбрать направление для «обхода»:

import random

entry_i = center_i

entry_j = center_j

where_we_can_go = ['up_left','up_right','down_left','down_right']

where_to_go = random.choice(where_we_can_go)

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

После того как направление для перемещения будет выбрано, выполняется правило, соответствующее направлению перемещения. Если выбрано перемещение вниз и налево (down_left) или вверх и направо (up_right), то мы следуем правилу 1, выбирая соответствующие аргументы и индексы:

if(where_to_go == 'up_right'):

    new_entry_i = entry_i - 1

    new_entry_j = entry_j + 1

    square[new_entry_i][new_entry_j] = rule1(square[entry_i][entry_j],n,True)

if(where_to_go == 'down_left'):

    new_entry_i = entry_i + 1

    new_entry_j = entry_j - 1

    square[new_entry_i][new_entry_j] = rule1(square[entry_i][entry_j],n,False)

Аналогичным образом при выборе направления вверх и налево (up_left) или вниз и направо (down_right) используется правило 2:

if(where_to_go == 'up_left'):

    new_entry_i = entry_i - 1

    new_entry_j = entry_j - 1

    square[new_entry_i][new_entry_j] = rule2(square[entry_i][entry_j],n,True)

if(where_to_go == 'down_right'):

    new_entry_i = entry_i + 1

    new_entry_j = entry_j + 1

    square[new_entry_i][new_entry_j] = rule2(square[entry_i][entry_j],n,False)

Код предназначен для перемещения вверх и налево или вниз и направо, но должен выполняться только в том случае, если при этом не пересекается антидиагональ. Необходимо позаботиться о том, чтобы правило 3 выполнялось только при пересечении антидиагонали. Проверить, находится ли значение рядом с антидиагональю, достаточно просто: индексы значений непосредственно над антидиагональю в сумме дают n-2, а индексы значений непосредственно под антидиагональю в сумме дают n. Для этих особых случаев нужно реализовать правило 3:

if(where_to_go == 'up_left' and (entry_i + entry_j) == (n)):

    new_entry_i = entry_i - 1

    new_entry_j = entry_j - 1

    square[new_entry_i][new_entry_j] = rule3(square[entry_i][entry_j],n,True)

if(where_to_go == 'down_right' and (entry_i + entry_j) == (n-2)):

    new_entry_i = entry_i + 1

    new_entry_j = entry_j + 1

    square[new_entry_i][new_entry_j] = rule3(square[entry_i][entry_j],n,False)

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

where_we_can_go = []

if(entry_i < (n - 1) and entry_j < (n - 1)):

    where_we_can_go.append('down_right')

if(entry_i < (n - 1) and entry_j > 0):

    where_we_can_go.append('down_left')

if(entry_i > 0 and entry_j < (n - 1)):

    where_we_can_go.append('up_right')

if(entry_i > 0 and entry_j > 0):

    where_we_can_go.append('up_left')

Теперь у нас есть все элементы, которые необходимы для написания кода Python, реализующего алгоритм Курусимы.