Python:将几何形状放入棋盘矩阵？

Question

在过去的几天里，我一直在想一个AI问题的解决方案。问题听起来是这样的：

我想确定在给定大小的正方形电路板上的几个给定几何形状(不超过给定电路板大小)的排列方式，使得该电路板将被均匀覆盖，并且这些形状不会重叠。

我想要应用深度优先搜索/贪婪的最佳优先搜索，但为了遍历它，很难找到表单和实际棋盘的适当表示。我是python的新手，所以这让它变得有点困难。有什么建议吗？

可视化示例：

​

​

​

​

Answer 1

您所描述的是矩形/正方形拟合的变体。问题的不同版本存在，为了图形的最佳位置，必须最小化未使用的单元格，而其他版本，如您正在描述的版本，需要均匀覆盖整个电路板。这就是所谓的“完美正方形/矩形布局”问题。

解决这些问题的典型方法包括使用表示矩形变量的有限整数域和一组约束，以确保几何位置是有效的(即不跨越电路板边界，不相互重叠，..)。