Comments 14
Спасибо. Очень интересно. Видел на нг эти квадратики.
Но найти все варианты заполнения это реально Круто!
Спасибо, интересная задача, крутое исследование! Вы, наверно, можете в oeis.org завести соответствующую последовательность (будет что-то типа 1,0,0,0,0,0,0,2332,216285)
Я тоже хочу попробовать ускорить ее на CPU, как будет больше времени)) Тут возможны низкоуровневые оптимизации для представления текущего заполнения, интересно, насколько они будут полезны.
Еще можно попробовать такую оптимизацию: при добавлении нового квадрата, если он получается выше предыдущего, проверять, что существуют свободные квадраты, которые можно поставить на предыдущий квадрат (если пред-предыдущий квадрат выше) - но не факт, что это сильно сократит количество вариантов для перебора.
Я написал простую реализацию на c++ (однопоточную и без учета симметрий), она решила n=8 за 25 минут.
то добавляем к задаче ещё 1 квадратик (всевозможные его варианты) и тем самым подразбиваем задачу примерно на 9 подзадач
Если я правильно понял, то вы перешли от dfs (depth-first search), не очень подходящего для GPU, к bfs (breadth-first search)?
216'285 вариантов заполнения ..., или в 8 раз больше, если включить в ответ все повороты и симметрии
А всех вариантов действительно будет в 8 раз больше? Это верно, только каждый вариант разбиения несимметричен ни в какой симметрии, так как иначе ему будет соответствовать меньше, чем 8 вариантов. Я проверил для n=8 и действительно получил 18656 = 2332*8 вариантов. Интересно, можно ли доказать, что не существует симметричных разбиений?
Спасибо за интерес к статье!
Вы, наверно, можете в oeis.org завести соответствующую последовательность (будет что-то типа 1,0,0,0,0,0,0,2332,216285)
Да, я как раз подал на рассмотрение в oeis.org такую последовательность.
Я написал простую реализацию на c++ (однопоточную и без учета симметрий), она решила n=8 за 25 минут.
Это очень впечатляет!
Если я правильно понял, то вы перешли от dfs (depth-first search), не очень подходящего для GPU, к bfs (breadth-first search)?
По сути, да. Делаю 1 шаг поиска в ширину, а потом каждую подзадачу пробую решить поиском в глубину.
А всех вариантов действительно будет в 8 раз больше? Это верно, только каждый вариант разбиения несимметричен ни в какой симметрии, так как иначе ему будет соответствовать меньше, чем 8 вариантов. Я проверил для n=8 и действительно получил 18656 = 2332*8 вариантов. Интересно, можно ли доказать, что не существует симметричных разбиений?
Поясню этот момент. Это утверждение мне казалось очевидным, но в реальности оно чуть более сложное.
Во-первых, поворот на 90 и 180 градусов не может привести к тому же заполнению, т.к. у нас более одного квадратика в нечётном количестве, т.е. нечётное количество квадратиков одного размера стоит вне центра, и поэтому хотя бы один квадратик не найдёт соответствия, т.к. все циклы "кто в кого переходит при повороте" чётной длины.
Во-вторых, при n=8 (и других n, когда сторона квадрата чётная) симметрии быть не может, т.к. квадратики нечётного размера не могут стоять в центре, а их нечётное количество.
В-третьих, при n=9 (и других n, когда сторона квадрата нечётная) симметрия потенциально может быть двух видов: относительно горизонтали/вертикали и относительно диагонали. В первом случае на центральной линии, а во втором на диагонали должны стоять только квадратики размера 1, 3, 5, 7, 9. Проблема возникает с квадратиком размера 1. Если симметрия относительно горизонтали/вертикали, то он будет стоять между двумя квадратиками большего размера, что приведёт к "пазу" толщины 1, или же он будет у границы. В случае диагонали, несложно понять, что квадратик размера 1 также не может стоять в таком положении, т.к. это приведёт к "пазу" толщины 1.
Я немного поэкспериментировал с задачей, но комментарии хабра слишком коротки, чтобы подробно описать результат, поэтому вот очень примерное описание решения задачи для n=8 (n=9 я пока даже не трогал):
Неоптимимизированное решение: стандартный DFS (depth first search with backtracking), состояние представленно как три 16-байтных массива (текущие высоты, длины, и количество оставшихся квадратов). После заполнения текущего нулевого уровня, все заполненные строки схловываются, как в тетрисе, так что заполняется всегда нулевой уровень, что упрощает код.
Время работы: 24 мин, количество шагов DFS: 64G, код
Симметрия: рассматриваются только такие состояния, в которых самый первый квадрат не меньше второго и не меньше последнего в первом ряду, остальные состояния достраиваются с помощью симметрии.
Время: 14 мин, шагов DFS: 35G, код
Эвристика: после добавления квадрата, рассматриваются два предыдущих: если средний квадрат в этой тройке ниже, чем крайние, то проверяется, что у нас еще остались достаточно маленьуие квадраты, чтобы в будущем заполнить этот промежуток.
Время: 12 мин, шагов DFS: 23G, код
Низкоуровневые оптимизации перехода состояний иcпользуют 128-битные __uint128_t и регистры SSE, а также ускоренное нахождение размеров квадратов, которые можно использовать на текущем шаге, через битовые маски
Время: 9.5 мин, шагов DFS: 23G, код
Еще пробовал, но не получилось:
5. Еще более низкоуровневые оптимизации: все операции в 128-бит или SSE, уменьшение размера состояния до 32 байт, уменьшение дорогостоящих операций обновления состояния: ускорение получается меньше 10%, а код очень сильно усложняется.
6. Я пробовал делать DFS в половину глубины, а потом сшивать попарно. К сожалению, идея не работает: обратный DFS не может сгененировать некоторые варианты (например, когда в первой половине есть "яма" длиной 2 и высотой 4)
При этом у вас, как я понимаю, работает на одном ядре. Поэтому 9,5 мин - это очень крутой результат!
Не совсем понял про "яму" длиной 2 и высотой 4. Если это про метод, проиллюстрированный на Рис. 4, то это решается рассмотрением вариантов квадратиков, у которых основание лежит на нужной половине, а центр уже за границами половины, и исключением их из финальной фигуры.
я пытался строить все варианты с половиной кубиков (18 для n=8, 22 или 23 для n=9).
В вашем случае границы, как на рис.4, сложность в том, что на любой позиции над средней линией можно поставить квадратик размера 1 (допустим, он бы еще не был использован), и тоже получится правильная граница. То есть, "жадное" заполнение сверху вниз и слева направо не работает, надо перебирать больше вариантов, по крайней мере, близко к границе. Или я чего-то не учитываю?
Спасибо. Очень интересно! По времени уже близко к тому, как мой код работает на GPU.
Есть 2 хорошие новости:
Во-первых, результат для n=9 подтвердился. Я взял код №2 от @lightln2, распараллелил его с помощью обвязки на Питоне и запустил на 10 ядрах. Результат сошёлся с моим.
Во-вторых, последовательность приняли в OEIS: https://oeis.org/A381976
Как я решал задачу 2025 года. Часть 1