На этом шаге мы рассмотрим пути решения этой задачи.
Производитель должен установить прямоугольные микросхемы на прямоугольную плату. По сути, эта задача сводится к вопросу: "Как разместить все прямоугольники разных размеров внутри другого прямоугольника таким образом, чтобы они плотно прилегали друг к другу?" Решить эту задачу можно, применив схему решения задач с ограничениями (рисунок 1).
Рис.1. Задача размещения элементов на печатной плате очень похожа на задачу поиска слова, но прямоугольники имеют разную ширину
Задача размещения элементов на печатной плате похожа на задачу поиска слов. Только вместо 1 * N прямоугольников (слов) в ней представлены М * N прямоугольников. Как и в задаче поиска слов, они не могут перекрываться. Прямоугольники нельзя размещать по диагонали, так что в этом смысле задача даже проще, чем поиск слов.
Попробуйте самостоятельно переписать решение для поиска слов, чтобы приспособить его к задаче размещения элементов на печатной плате. Можете повторно использовать большую часть кода, включая код для построения сетки.
На следующем шаге мы подведем некоторые итоги.
