Как бы вы решали задачи пойска магических квадратов заданного размера в болошоми массиве n * m.

Магический квадрат — это квадратная матрица состоящая из чисел 1..N где все суммы по столбцам, строкам и диагоналям одинаковы.

Т.е. такой квадрат


Будет в таком массиве по поции [0, 0]

4 9 2 5 6
3 5 7 6 7
8 1 6 6 7

Здравствуйте, Hard_Club, Вы писали:

H_C>Как бы вы решали задачи пойска магических квадратов заданного размера в болошоми массиве n * m.

Перебором?

цикл по строкам
  цикл по столбцам
    МагическЛиКвадрат()

... или Магич?

Здравствуйте, Hard_Club, Вы писали:

H_C>магических квадратов заданного размера
Пусть размер стороны задан и равен k (а всего в квадрате тогда получается k² элементов).


H_C>Как бы вы решали задачи пойска магических квадратов заданного размера в болошоми массиве n * m.
А квадраты и матрицы большие? Если нет, то наивным перебором (как уже предложено тут

Автор: VladFein
Дата: 05.03.15

).

Если нужно быстрее, то можно так:
Тогда первым проходом за время O(mn) находятся точки, начиная с которых идут непрерывные строки, столбцы или диагонали длины k и с суммой k(k²+1)/2 вдоль них.
Вторым проходом за то же время O(mn) эти точки группируются и определяется то же условие, но с заменой 'или' на 'и'. Полученные точки — это кандидаты в квадраты — любой магический квадрат начинается только в них.
Теперь осталось лишь проверить, что в каждом таком квадрате выполняется не только ограничение на сумму, но и на уникальность чисел. Если кандидатов мало, то можно проверить их всех непосредственно. Если много, то просто пускается по матрице sliding window размера k×k и в нём отслеживается соблюдение инварианта. Это всё займёт время O(mnk), что и определит общую сложность алгоритма.

Ну и при желании на последний шаг можно навешать различных эвристик. Например, сдвигать скользящее окно не на одну строку/столбец за раз, а сразу на много, действуя подобно тому, как алгоритм Бойера–Мура обрабатывает стоп-символы. При хорошем распределении это позволит сразу прыгать на много шагов вперёд, при плохом — особо ничего не изменит. Собственно, таких дешёвых эвристик можно ещё несколько добавить для достижения синергетического эффекта (в среднем случае).

Здравствуйте, watchmaker, Вы писали:

Пару вопросов о сложности:

W>Тогда первым проходом за время O(mn) находятся точки, начиная с которых идут непрерывные строки, столбцы или диагонали длины k и с суммой k(k²+1)/2 вдоль них.
Это не O(mnk)?

W>Вторым проходом за то же время O(mn) эти точки группируются и определяется то же условие, но с заменой 'или' на 'и'. Полученные точки — это кандидаты в квадраты — любой магический квадрат начинается только в них.
W>Теперь осталось лишь проверить, что в каждом таком квадрате выполняется не только ограничение на сумму, но и на уникальность чисел. Если кандидатов мало, то можно проверить их всех непосредственно. Если много, то просто пускается по матрице sliding window размера k×k и в нём отслеживается соблюдение инварианта. Это всё займёт время O(mnk), что и определит общую сложность алгоритма.
А это не O(mnk²)?

Здравствуйте, VladFein, Вы писали:

VF>Пару вопросов о сложности:

W>>за время O(mn)
VF>Это не O(mnk)?

W>> Это всё займёт время O(mnk)
VF>А это не O(mnk²)?

По определению при n→+∞ любая функция из класса O(n) будет также находится в классах функций O(n^2), O(n^3), O(n!) и даже в O(n^n!)

Так что ответ на оба вопроса — да

W>Если нужно быстрее, то можно так:
W>Тогда первым проходом за время O(mn) находятся точки, начиная с которых идут непрерывные строки, столбцы или диагонали длины k и с суммой k(k²+1)/2 вдоль них.
W>Вторым проходом за то же время O(mn) эти точки группируются и определяется то же условие, но с заменой 'или' на 'и'. Полученные точки — это кандидаты в квадраты — любой магический квадрат начинается только в них.
W>Теперь осталось лишь проверить, что в каждом таком квадрате выполняется не только ограничение на сумму, но и на уникальность чисел. Если кандидатов мало, то можно проверить их всех непосредственно. Если много, то просто пускается по матрице sliding window размера k×k и в нём отслеживается соблюдение инварианта. Это всё займёт время O(mnk), что и определит общую сложность алгоритма.

Как Вы так быстро догадались? Упражняетесь в аглоритмах?

А стоит ли делать некий кеш из посчитанных сум подстрок и подстолбцов равных k(k^2 + 1)/2, чтобы если мы расчитали один квадрат — квадрат чуть смещенный вниз не надо было полностью пересчитывать?

Здравствуйте, VladFein, Вы писали:

VF> МагическЛиКвадрат()
VF>... или Магич?

Магичен?

вот что получилось

for row_idx in xrange(RECTANGLE_ROWS - MAGIC_SQUARE_DIMENSION + 1):
    for col_idx in xrange(RECTANGLE_COLUMNS - MAGIC_SQUARE_DIMENSION + 1):
        row_slice = slice(row_idx, row_idx + MAGIC_SQUARE_DIMENSION)
        col_slice = slice(col_idx, col_idx + MAGIC_SQUARE_DIMENSION)
        if (MAGIC_SUM != np.sum(rectangle[row_slice, col_idx]) or
            MAGIC_SUM != np.sum(rectangle[row_idx, col_slice])):
            continue

        for row_offset in xrange(1, MAGIC_SQUARE_DIMENSION):
            if MAGIC_SUM != np.sum(rectangle[row_idx + row_offset, col_slice]):
                continue

        for col_offset in xrange(1, MAGIC_SQUARE_DIMENSION):
            if MAGIC_SUM != np.sum(rectangle[row_slice, col_idx + col_offset]):
                continue

        magic_square = rectangle[row_slice, col_slice]

        if (MAGIC_SUM != magic_square.trace() or
            MAGIC_SUM != magic_square[::-1].trace()):
            continue

        unique_number_mask = 0
        for number in magic_square.flat:
            unique_number_mask = unique_number_mask | (1 << (number - 1))
        if unique_number_mask != MAGIC_NUMBER_MASK:
            continue

        magic_squares.add(magic_square)

Здравствуйте, Hard_Club, Вы писали:

H_C> чтобы если мы расчитали один квадрат — квадрат чуть смещенный вниз не надо было полностью пересчитывать?
Так и работает скользящее окно.

Здравствуйте, Hard_Club, Вы писали:

H_C>вот что получилось

У меня есть ещё одно "наивное" предложение: после провалившихся проверок строк или колонок на MAGIC_SUM не просто продолжать по continue, а пометить точки (MAGIC_SQUARE_DIMENSION-1) во все стороны (вверх/вниз для строк или влево/вправо для колонок) как НЕ кандидаты (или во внешнем bool массиве, или флагом в старшем бите, если размерность позволяет).

P.S. Долго думал, стеснялся и сомневался — предлагать или нет? Как бы не засмеяли...