Компьютерная математика Weekly

Запишем таблицу умножения чисел от 1 до N. Много ли чисел в ней встречаются?

Ну первая идея, что примерно N²/2… но некоторые числа встречаются несколько раз не только потому что 6×7=7×6, но и нетривиальным образом (24=8×3=6×4, вот это всё)… насколько это существенно?

Для таблицы умножения 10×10 ответ 42, вроде не очень далеко от 50. Но это потому что 10 маленькое число — на самом деле, встречается лишь o(N²) чисел!

На пальцах можно так объяснить. Сколько обычно простых делителей у числа, не превосходящего N? Каждое p является делителем с вероятностью 1/p, поэтому матожидание числа делителей есть ∑1/p, а эта сумма растет (как здесь обсуждалось) как log log N. А для чисел из таблицы умножения типичное количество простых делителей равно 2 log log N, среди чисел от 1 до N² таких чисел очень мало (почти у всех намного меньше простых делителей, log log N²).

Но это только начало истории, дальше — см. t.me/MathfromKrach/213

«Those familiar with the landscape of mathematics will instantaneously recognize this problem as something Erdős would ask. It was indeed Erdős who asked this in 1955. In the following, we discuss some elementary bounds for this problem, a remarkable achievement of Ford who solved the problem up to a constant factor, and finally rather surprising conjectural answer to this question, which is a work in progress by Ben Green and Mehtaab Sawhney.»

на картинке для небольших чисел (до 47) показано, насколько велик их НОД по сравнению с их произведением (по клеткам разнесена формула =GCD($A2,B$1)/SQRT($A2*B$1))

можно подумать, что видно на этой картинке и почему

какие последовательности обладают свойством
a[1]+a[2]+…+a[2n-1]=a[n]² (для всех n)?

кто складывал идущие подряд нечетные числа, понимает, что a[n]=2n-1 подходит… а что еще можно придумать?

на Всеросе сегодня предлагали (задача 10.2) доказать, что при каких-то доп. условиях других решений нет… а я прочитав условие подумал, что это похоже на то, что обсуждалось напр. в t.me/compmathweekly/120 & t.me/compmathweekly/121 — и можно в таком же духе продеформировать…

ну и действительно, a[n] = sin(2n-1)x / sin x подходит

(написал сначала, что это все решения… но пожалуй чутка погорячился, чтобы так было, надо какое-то аналогичное «четное» условие добавить видимо)

здесь пару раз уже обсуждались количества разбиений (t.me/compmathweekly/40 например)

одна стандартная (при этом хорошая) задача — разобраться, почему количество разбиений на различные слагаемые всегда равно количеству разбиений на нечетные слагаемые

например: (7 6+1 5+2 4+3 4+2+1) vs (7 5+1+1 3+3+1 3+1+1+1+1 1+1+1+1+1+1+1)

можно потребовать, чтобы слагаемые были не только различными, но и все четными… ну это по понятной причине мы ничего нового не увидим; с другой стороны, если считать разбиения на различные нечетные слагаемые, то получается какая-то совсем новая последовательность

а чтобы получалась не новая последовательность, а тождество, можно сделать такой странные трюк

будем называть… э… 7-исправленными разбиениями — разбиения в сумму различных слагаемых, где кратные 7 числа бывают двух видов. так вот, если взять 7-исправленные разбиения нечетных чисел на нечетные — то будет та же последовательность oeis.org/A093950 что и просто для 7-исправленных разбиений

например: (15 11+3+1 9+5+1 7+7'+1 7+5+3 7'+5+3) vs (7 7' 6+1 5+2 4+3 4+2+1)

такую теорему опубликовал Кэли в 1876 году. и забавным образом это связано с эллиптическими интегралами из недавнего поста t.me/compmathweekly/128

но в этой теме так и не разобрался, а вместо этого напишу, что вместо 7-исправленных разбиений можно брать 23-исправленные, и тоже будет такого же рода утверждение… а если какие-то другие числа вместо 7 или 23 брать, то ничего не получается (по крайней мере на первый взгляд)

но может кто-то найдет экспериментально каких-то еще родственников этого тождества Кэли

для экспериментов минимально адаптировал count_partitions_upto из упомянутого в начале поста, так что особого кода не будет

Леня @qtasep Петров со товарищи (D.Anderson, G.Panova) «present computational results related to principal specializations of the Schubert polynomials (…). We find the first counterexample, at n=17, to the conjecture of Merzon-Smirnov that the maximal value of S_w(1^n) is obtained at a layered permutation.»

https://lpetrov.cc/2026/03/schubert-computation-sampling/

вполне себе компьютерная математика — при этом не то что бы просто достаточно перебрать в лоб:

This conjecture was exhaustively verified by one of us (DA) for n≤13 in February 2025. (…) In May 2025, Adam Wagner (along with DA and Alejandro Morales) deployed Google DeepMind’s FunSearch to seek counterexamples to Conjecture. For n≤16 the heuristics found by the model did not uncover any counterexamples, providing weak evidence in favor of the conjecture in this range. (For larger n, time constraints limited the power of this method.)

Витя Клепцын обратил внимание на дудл Гугла к «дню числа пи» с этих выходных

там периметры вписанных и описанных многоугольников со всё большим числом сторон вычисляются при помощи динамики a’ = 2ab/(a+b), b’=√(a’b)

если не бояться тригонометрии, то эти формулы несложно проверить, но вижу такое первый раз

более естественно смотрится похожая динамика a’ = 2ab/(a+b), b’=√(ab)… или, если перейти к обратным величинам, a’=(a+b)/2, b’=√(ab)

если такое итерировать, то обе переменные очень быстро сходятся к одному и тому же числу, «арифметико-геометрическому среднему» Гаусса

вот как раз про это думал написать чуть раньше в связи с тем, что (1/4)! тесно связано с AGM(1,√2)… а также в связи с тем, что AGM позволяет параметризовать точки кубической кривой правильно (так, чтобы сложение на кубике соответствовало сложению параметров)

в Мат. просвещении ключевое утверждение про связь AGM с эллиптическими функциями дали в виде задачи: доказать, что интеграл по прямой от dt/√((t²+a²)(t²+b²)) не меняется при замене (a,b) на ((a+b)/2,√(ab))… можно попробовать решить или прочитать решение в mathnet.ru/rus/mp979 или elsewhere

продолжу нерегулярные записки про компьютерные эксперименты вокруг разговоров со школьниками

обсуждали вчера функцию y=n²x(1-x)ⁿ на отрезке [0;1]

вот как она выглядит для (умерено) большого n

контрольные вопросы: в какой точке максимум? чему он равен? что с ним происходит при больших n?

ясно, что для любого конкретного x с ростом n значение в точке x стремится к нулю — но при этом уже из ответов на вопросы выше видно, что интеграл к нулю не стремится

всё самое интересное происходит всё ближе и ближе к нулю… чтобы это рассмотреть, можно сделать гиперболический поворот (x,y)→(xc,y/c) (площади он не меняет!) — вот можно поиграть с этим: https://www.geogebra.org/m/ytevq2sa

если не хватает интуиции, на сколько именно “поворачивать” (перемасштабировать), то вдохновляться можно ответами на контрольные вопросы

руки ни до чего не доходят, но напишу про кое-что из прочитанного, что понравилось

возьмем какую-нибудь эрмитову матрицу и будем смотреть на (Av,v) для векторов на единичной сфере

ясно, что это значение всегда лежит между минимальным и максимальным собственными значениями… а как конкретно оно распределено (если v выбираем случайно по сфере)?

вот на картинке эксперимент (не мой) для матрицы 3×3 — чудесным образом распределение кусочно-линейное

и дальше тоже занятно

источник: mathstodon.xyz/@dpiponi/115512381036445964 (а он ссылается на arxiv.org/abs/2511.04602 — но наверное это и где-то еще написано)

как оценить p(n), количество разбиений числа n в сумму слагаемых (без учета порядка)?

буквально для p(n) явную формулу придумать не получается, но всё сильно упрощается, если наложить дополнительное ограничение «максимальное слагаемое не больше k»

легко сообразить, например, что p₁(n)=1, p₂(n)≈n/2, а чуть напрягшись можно получить и p₃(n)≈n²/12+…

вообще pₖ(n) — это количество целых точек в (k-1)-мерном симплексе x₁+2x₂+…+kxₖ=n — а значит, при больших n это примерно объем этого симплекса, т.е. типа n^{k-1}/{(k-1)!k!} (можно думать, что один факториал берется из формулы объема многомерного симплекса и еще один из произведения сторон, т.е. коэффициентов в уравнении)

левая картинка иллюстрирует, что если n растет, а k фиксировано, то довольно быстро pₖ(n) перестает быть адекватным приближением для p(n) — которое растет, как мы уже видели, быстрее любого полинома (см. тж. https://t.me/compmathweekly/40 и комментарии там)

всё же можно прикинуть, что раз сторона квадрата площади n равна √n, запрещать слагаемым быть сильно больше √n не должно особо сильно влиять на ответ — и с этим неплохо согласуется правый график

если воспользоваться оценкой типа Стирлинга √n! ~~ (√n/e)^√n, то в прикидке p(n)~~p_{√n}(n) вещи типа n^n сокращаются и остается эвристика p(n)~~exp(2с√n)

и это совсем недалеко от правильной асимптотики p(n)~exp(2с√n)/{4√3n}, где c²=1+1/2²+1/3²+…=π²/6

в продолжение развлечений с доской Гальтона запишу конспективно элементы дальнейших обсуждений:

что мы увидим, если всё-таки ничего не аггрегировать, а смотреть на вероятность конкретного события? например, пусть мы кинули монетку N раз (и эн-большое действительно большое)
• для какого k событие «орел выпал ровно k раз» наиболее вероятно?
• что происходит с этой (максимальной) вероятностью с ростом N?
• хорошо, она стремится к нулю — а насколько быстро?

по ходу дела смотрели на картинки, которые рисовал питон — но вообще тут можно обойтись и экселем (для совсем ленивых: =BINOM.DIST(A2,2*A2,0.5,FALSE))

как обычно, если на графике видно только «как-то всё это быстро растет / убывает», полезно переходить к логарифмическому масштабу ( a la https://t.me/compmathweekly/20 )

если не удовлетвориться первым приближением «убывает как 1/√N», а поразбираться и с константой, то возникают обсуждавшиеся факториалы дробных чисел

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

пока приближается Матпраздник и мало сил на новые сюжеты — напомню несколько постов из прошлого с красивым картинками:

* квазипериодическое замощение плоскости треугольниками двух видов t.me/compmathweekly/33

* случайные разбиения на доминошки и появляющийся при этом полярный круг t.me/compmathweekly/57

* фрактал Ньютона в экселе t.me/compmathweekly/107

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


выше возникала рекуррента
a[n+1]⋅a[n-1] = a[n]²−1
можно еще для однородности перейти к
b[n+1]⋅b[n-1] = b[n]²−b[1]²
(если хочется решение исходной р-ты, то a[k]=b[k]/b[1] подойдет)

какие у нее решения, кроме 1, 2, 3, 4, 5…?

тут есть прекрасный явный ответ:
b[n] = c⋅sin(nx)
(тригонометрическая разминка: доказать, что это решение)

(тут ясно, что если устремить x к нулю, то получится как раз линейное решение выше, но вот глядя на последовательность 1, 2, 3, 4… не так уж видно, что это тень вырождение синуса)


с другой стороны, если начать не с [1, 2], а с [1, 3], то возникает последовательность 1, 3, 8, 21, 55, 144… — чисел Фибоначчи с четными номерами

мини-загадка: как одно соотносится с другим?

алгебра дуальных чисел (записей типа 2+7ε, где умножение задается соотношением ε²=0) возникала уже здесь как средство для автоматического дифференцирования ( https://t.me/compmathweekly/108 )

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

в новом Кванте (№11-12 за 2025 год) увидел статью В.Овсиенко¹, где похожий механизм позволяет разным классическим последовательностям отбрасывать интересные тени

например. возьмем классическую последовательность чисел Каталана 1, 1, 2, 5, 14… (они считают скобочные структуры, бинарные деревья и проч.). она задается рекуррентой c[n+1] = sum(c[i]*c[n-i] for i in range(n+1)) — вот сохраним ту же рекурренту, но начальное условие продеформируем в [1, 1+ε]. вещественная часть от этого не поменяется, а вот коэффициенты при ε дадут «тень», представляющую собой…

ну не буду пока признаваться — но можно до эксперимента прикинуть: производящая функция будет почти такая же, только аргумент на что-то такое ε-образное сдвинется… и появится, как обсуждалось в прошлый раз, производная…

***

было приятно, что для компьютерного эксперимента не потребовалось примерно ничего:

from my_dual import eps

cat = [1, 1+eps]
for n in range(1,10):
    cat.append( sum(cat[i]*cat[n-i] for i in range(n+1)) )
print(*cat)

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

***

другой пример. какую тень отбрасывает последовательность 1, 2, 3, 4, 5..? если взять рекурренту a[n+1]=a[n]+1, то ничего интересного видно не будет — но это, учит В.О., потому что рекуррента выбрана неправильно. а правильно — a[n+1]*a[n-1] = a[n]*a[n]−1 — тогда начальное условие [1,2+ε] дает нетривиальную тень…

выбор рекурренты тут может показаться несколько странным, но можно думать про это как про «детскую версию» последовательности Сомоса — рекуррент в духе a[n+2]*a[n-2] = a[n+1]*a[n-1]+a[n]*a[n], описывающих в т.ч. последовательность nP точек на эллиптической кривой

про последовательности Сомоса уже не понимаю, но можно послушать рассказы А.Устинова на ЛШСМ — mathnet.ru/present39762 (и далее по ссылкам)

¹ (upd) https://www.kvant.digital/issues/2025/11-12/ovsienko-posledovatelnosti-teni_ot_fibonachchi_k_markovu_i_obratno-d5ddf696/

на уроке вчера возникла потребность в доске Гальтона… показал из Википедии, но возникло желание поменять разные параметры — пришлось быстренько добавить компьютерный эксперимент

напомню, о чем речь: когда мы переворачиваем конструкцию слева, море шариков (например, 1000) начинает падать через сколько-то уровней (15, 100…) штырьков, на каждом из которых шарик случайно отклоняется либо налево, либо направо; и в конце шарики в соответствии с x-координатой попадают в один из нескольких (скажем, 9) столбиков и мы видим какую-то гистограмму

это нетрудно сымитировать в духе

import numpy as np

balls = 1000
pins = [15,100,400,1000,10_000]
groups = 9

ans = np.zeros((len(pins),groups),dtype=np.uint32)
for i, n in enumerate(pins):
    for _ in range(balls):
        bits = np.random.randint(2, size=n)
        dest = int(groups*np.sum(bits)/n) 
        ans[i,dest] += 1
print(ans)

хорошо сделанная (это непросто!) доска Гальтона позволяет увидеть нормальное распределение, это демонстрация ЦПТ… но мы обсуждали более простые вещи

[1 19 43 234  404 152 127 18 2]
[0  0  1 118  734 147   0  0 0]
[0  0  0   7  981  12   0  0 0]
[0  0  0   0  998   2   0  0 0]
[0  0  0   0 1000   0   0  0 0]

— видно, что если для первых строк еще есть какое-то распределение, то когда кидаем монетку много раз, при любом фиксированном округлении доля орлов просто-таки всегда (в экспериментальном смысле) равна 1/2

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

с другой стороны, вот это «мы можем получить любую последовательность, все последовательности равновероятны… но для длинных последовательностей хоть тыщщу раз ставь эксперимент, макроскопический параметр все время виден один и тот же» (более сложный пример, возникавший здесь: полярный круг) всё-таки вызвывает удивление, ощущение какого-то противоречия

ну и тут кроме тех или иных эмоций можно было бы обсуждать собственно доказательство… но этого не делали

// фото: Matemateca (IME/USP)/Rodrigo Tetsuo Argenton

4.
кратко объясню, как определение факториала выше связано с Г-интегралом

∫ t^s exp(-t) dt (от 0 до ∞)

пользуясь тем, что exp(-t) = lim(1-t/N)^N можно (опущу технические детали типа перестановки пределов) переписать этот интеграл как

lim ∫ t^s (1-t/N)^N dt (от 0 до N)

а переходя к переменной x=t/N мы получаем

lim N^s ∫ x^s (1-x)^N N dx (от 0 до 1) =¹
lim N^s / (N+s|N)
т.е. s! в смысле предыдущего определения

¹ то, что такой B-интеграл равен обратному биномиальному коэффициенту, легко доказать N-кратным интегрированием по частям

(заодно теперь видно, что в (1/2)! не обойтись без π: B-интеграл ∫ x^(1/2) (1-x)^(1/2) dx буквально считает площадь под полуокружностью… кстати, «именно это» π, из (1/2)! можно видеть в формуле Стирлинга)

***

интегралы легко приближенно считать даже в экселе — можно написать формулу типа

=LET(x,SEQUENCE($B2)*$A2,
SUM(POWER(x,C$1)*EXP(-x)*$A2))

(считая, что в клетке A2 записана длина шага, в клетке B2 количество шагов, в клетке C1 — число s)

ну конечно вычислительно это малоудачно: для погрешности ~1/N нужны шаги ~1/N в количестве, соответственно, ~N — и больше 5 цифр после запятой уже малодоступны экселю (если не переходить к методам численного интегрирования поумнее)

1.
если у нас есть A предметов, то 2 из них можно выбрать A(A-1)/2 способами, 3 — A(A-1)(A-2)/6 способами и т.д.; буду здесь обозначать (A|K) := A(A-1)…(A-K+1) / K!

эту формулу часто помнят в виде отношения факториалов, но если мы хотим выбрать 2 предмета из 1000, то начинать подсчет количества вариантов с вычисления 1000! — не самая лучшая идея

есть и другой аспект. разговор о выборе K предметов имеет смысл только если число A целое… а вот в наше определение для (A|K) формально можно подставить любое A

в этом есть смысл — например,
(1+x)^A = 1 + Ax + (A|2)x² + (A|3)x³ + ...
и это равенство верно и для нецелых A

многие помнят, что sqrt(1+x) это примерно 1+x/2 — а формула выше учит, что делать, если точности такого первого приближения недостаточно


2.
если от ограничений на A мы избавились, то K в формулах выше всё ж должно быть натуральным, иначе непонятно, что такое K!

но теперь можно изменить точку зрения и воспользоваться предыдущим для определения факториала произвольного числа

смотрите. если A большое число (а K пока натуральное), то (A|K) ~ A^K / K!, т.е. K! ~ A^K/(A|K); наконец, если A = K+N, то пользуясь симметрией биномиальных коэффициентов, (K+N|K)=(K+N|N), мы получаем K! ~ N^K/(K+N|N)

ура: правая часть определена и при нецелых K, и можно теперь считать определением факториала K! = lim N^K/(K+N|N) — а текст выше объясняет, что для целых K такой факториал совпадает с привычным

такое определение придумал, насколько понимаю, Эйлер


3.
пора всё-таки добавить компьютер… на картинке вычисления (1/2)!, (1/3)!, (1/4)! в экселе

sanity check: (K+2|2)=(K+2)(K+1)/2 — вроде это согласуется с тем, что подсчитано в строке 4

технически для бин. к-та написана формула типа
=PRODUCT(1+A$1/SEQUENCE(A3))

приятно, что полмиллиона сомножителей тут для экселя совсем не проблема… потому что видно, что такие формулы сходятся к ответу довольно медленно

как посчитать (1/4)! быстрее — мб в следующий раз обсудим



если никогда с этим не сталкивались и кажется, что всё это какая-то ерунда, предлагаю возвести ответ для (1/2)! из таблицы в квадрат и сообразить, что это за число (если ничего не приходит в голову — умножьте на 4)

раз речь зашла о разрезаниях — два еще слова про разрезания на т-тертаминошки

легко порезать на такие фигурки квадрат 4×4 — а значит, и все прямоугольники 4m×4n

с другой стороны, подсчет площадей дает только намного более слабое ограничение: если прямоугольник M×N можно разрезать, то MN делится на 4

оценки с двух сторон не сходятся… а что из этого ближе к правде?

задача для кружка: разобраться с доской 10×10

ответ на общий вопрос очень простой: ничего кроме досок 4m×4n разрезать нельзя (но сами разрезания могут быть довольно сложными, обратите внимание что даже картинка выше не составлена из двух квадратов)

никакими стандартными приемами типа раскрасок это доказать не получается (если знаете, что такое группа Конвея замощения — это тоже не помогает)

утверждение доказано в работе D.W.Walkup, Covering a rectangle with T-tetrominoes, Amer. Math. Monthly 72 (1965) 986–988 — рассуждение не длинное, элементарное (типа возьмем и докажем по индукции), но ничего (имхо) не понятно

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

но всё равно какого-то понятного объяснения про невозможность разрезаний на т-тетроминошки не хватает — какое-то прямо заколдованное место

на мат. кружке еще бывает, что не сказано, на какие именно фигуры резать, просто предлагают, скажем, разрезать квадрат 4×4 без угловой клетки на 3 равные фигуры

как такую задачу поставить SAT-солверу, научился по сути у Феди Куянова


кроме переменных со смыслом «такая-то клетка поля принадлежит такой-то фигуре» заведем, грубо говоря, по переменной для каждого потенциально возможного движения

и напишем условия
1) что каждая клетка поля принадлежит ровно одной фигуре;
2) что если данное движение выбрано (соотв. ему переменная True), то оно переводит первую фигуру во вторую;
2') что хоть одно движение выбрано

(если режем не на две, а на K частей, то для каждого движения будет не одна а (K-1) переменная со смыслом «это движение переводит фигуру №0 в фигуру №l»)

как конкретно закодировать, что движение s переводит одну фигуру в другую? грубо говоря, для каждой клетки c надо добавить условие [-s,-c_0,s(c)_l] («если уж выбрано движение s, а клетка c выбрана в фигуру №0, то клетка s(c) должна быть выбрана в фигуру №l) и условие [-s,-c_l,s^{-1}(c)_0] (чтобы было не просто вложение, а биекция)

остается еще техническая возня — потому что, скажем, символ s выше используется в трех разных (с т.з. питона) смыслах (перебираю я наборы чисел — на сколько, грубо говоря, сдвигать-поворачиать; по каждому набору строится отображение, просто так написать в коде s(c) нельзя; а сат-солверу в списке условий нужно отдавать ни то и ни другое, а отдельно заведенный номер переменной…), или, скажем, я замел под ковер то, что s(c) может вылезти за границы фигуры и тогда никакой переменной s(c)_l вообще нет (контрольный вопрос: какое условие надо тогда написать : ) — но всё ж логика не такая сложная… и даже код вышел не длинный


на кружке объясняю, что при решении задач на разрезание на равные части полезно бывает думать, какое конкретно движение их совмещает — и нравится, что та же математика помогает при общении на эти темы с компьютером

на мат. кружках для начинающих нередко режут какие-нибудь фигуры на уголки из трех клеток

и ясно, что площадь прямоугольника, который можно разрезать, должна делиться на 3… но 3×(2n+1) разрезать нельзя, 3×(2n) разрезать легко — возникает гипотеза, что даже на 6 должно количество клеток делиться

и все же прямоугольник 5×9 на уголки разрезать можно



давно хотел научиться пользоваться SAT-солверами для задач на разрезание и тому подобных дискретных задач, а это пусть будет модельный пример

для базового введения посмотрите лучше вот например https://youtu.be/4K1MyG4ljI8 (спасибо — и не только за это видео! — Саше Куликову), но всё же кратко поясню

SAT-солвер умеет только одно: подбирать значения булевых перменных, чтобы выполнялся набор условий, где каждое условие — выбор из вариантов «такая-то переменная равна такой-то константе»¹

в pycosat условия записываются в духе [1 -3 -4] («x1 or (not x3) or (not x4)»)

в нашей задаче мы заведем по одной переменной для каждого потенциального положения уголка внутри прямоугольника:

placements = []
covers = {}
for shape in TILES:
    for i, j in allcells():
        cells = [(i+dx, j+dy) for dx, dy in shape]
        if all(inside(*cell) for cell in cells):
            pid = len(placements) + 1
            placements.append(cells)
            for cell in cells:
                covers.setdefault(cell, []).append(pid)

все такие положения теперь лежат в массиве placements, а в словаре covers для каждой клетки указано, какие есть потенциальные способы ее покрыть

теперь пишем условия: 1) что каждая клетка покрыта; 2) что она не покрыта дважды (т.е. что из каждой пары способов покрытия хоть один не выбран):

clauses = []
for cell in allcells():
    ps = covers.get(cell, [])
    clauses.append(ps)
    for a, b in combinations(ps, 2):
        clauses.append([-a, -b])

и… всё! — можно говорить solve(clauses) и наслаждаться ответом

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

¹ прошу прощения у логиков и сочувствующих за терминологию, но от формулировки «нормальная форма, в которой булева формула имеет вид конъюнкции дизъюнкций литералов» я теряю нить