Алексей Никоноров - Повышение производительности солвера на примере решения одной задачи назначения
Как SAT-солверы решают задачи про разрезания
и почему прямоугольник 5×9 всё-таки режется на уголки На математических кружках для начинающих часто дают задачи, в которых нужно разрезать клетчатую фигуру на одинаковые маленькие кусочки. Классический пример — L-образный «уголок» из трёх клеток. Формулировка выглядит безобидно: можно ли разрезать данный прямоугольник на такие уголки без наложений и пропусков? Первое рассуждение почти всегда арифметическое. Каждый уголок состоит из трёх клеток, значит, общее число клеток обязано делиться на 3...