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

и ясно, что площадь прямоугольника, который можно разрезать, должна делиться на 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) и наслаждаться ответом

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

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