基于无重叠矩形的N×N方格网格填充位置求解

问题描述 #

给定由整数高度h和宽度w定义的矩形列表R，需找出所有满足以下条件的网格铺排方案：

• 将列表中每个矩形（可选择原方向或90度旋转后的方向）无重叠放置在N×N方格网格内（N≤64）
• 列表中的每个矩形必须且仅放置一次；若列表存在重复矩形，对应矩形需按其重复次数mᵢ（正自然数）放置mᵢ次

示例说明 #

示例场景 #

设R={{1,2},{1,1}}，目标网格为2×2空网格：

0 0
0 0

可行铺排方案 #

以下为所有可行填充方式，其中a代表第一个矩形（1×2），b代表第二个矩形（1×1）：

b a    0 b     a 0    a a    
0 a    a a     a b    0 b    

0 a    b 0     a b    a a    
b a    a a     a 0    b 0    

后续规划 #

当前计划先遍历完整的解空间，以此作为后续贪心搜索、神经网络等算法的基础；最终目标是基于一种考虑矩形边距的度量标准，找出最优铺排方案。

内容的提问来源于stack exchange，提问作者bantix