В продолжение части 1 привожу анализ заполнений квадрата со стороной 45 квадратиками размера от 1 до 9 (1x1 - 1 шт., 2x2 - 2 шт., 3x3 - 3 шт., ..., 9x9 - 9 шт.).
Начнём с простого. Несложно показать, что квадратик размера 1 не может стоять у границы и даже на расстоянии 1 от границы. Этот факт я учитывал при поиске вариантов, чтобы немного сократить перебор.
Если выстроить квадратики размера 9 вдоль двух соседних «стенок», то мы сведём задачу поиска заполнения к задаче для 
. Таким образом получается, что около 4% заполнений для 
получаются напрямую из заполнений для 
(у нас есть 4 способа выбрать 2 соседние «стенки»).
При просмотре заполнений видно, что очень часто «девятки» занимают целиком одну «стенку». Такое случается примерно в 79% заполнений. Если пойти дальше и посчитать процент случаев, когда есть хотя бы один столбец или строка, пересекающая только «девятки», получится около 96%. Видимо, так случается из-за того, что квадратиков размера 9 больше всего и они самые большие.
Рассматривая заполнения, можно также заметить, что «двойки» часто образуют прямоугольник размера 4*2, то есть касаются друг друга общей стороной. Но это происходит не всегда, а только примерно в 94% случаев. Также проверка показала, что нет случаев, когда «двойки» касаются друг друга (хотя бы углом), но при этом не совпадают по стороне.
В равенстве 
можно заметить, что сумма чисел от 1 до 9 равна стороне квадрата. Соответственно, встаёт вопрос, бывает ли, что квадратики выстраиваются таким образом, чтобы в одной строке или столбце встречались квадратики всех 9 видов. Оказывается, да, бывает. А вот чтобы одновременно в одном заполнении и столбец содержал все варианты квадратиков, и строка содержала все варианты квадратиков, - такого не бывает.
Также я задумался, сколько связных компонент может быть в заполнении. Связная компонента — это подмножество квадратиков одного размера, которые образуют одну связную область (касание только по углу не будем считать принадлежностью к одной связной компоненте). Так вот всего может быть от 14 до 30 связных компонент. Наиболее интересны варианты с маленьким и большим числом связных компонент - они выглядят как своего рода «порядок» и «винегрет» соответственно.
Также я заметил особенность, что квадратики одного размера довольно редко касаются друг друга углами (если при этом 2 других квадратика, касающиеся в этой точке отличаются размером от двух касающихся). Таких случаев менее 2%. А случаев, где более 2-х таких касаний на одном заполнении вообще не нашлось.
На этом спасибо за внимание! Надеюсь, после такого рассказа кто-нибудь сможет найти ещё более эффективный алгоритм поиска всех заполнений!
