我一直在努力为以下问题找到一个方便的解决方案：
假设我们有一个给定尺寸的墙和4种尺寸为4x 2，2x2，2x 1，1x1的瓷砖。墙的周长内有一些不能平铺的矩形区域（即孔）还有一种特殊类型的瓷砖，其可变尺寸为a x b，a查找符合以下约束的墙平铺：
相同尺寸的瓷砖不能一块一块地放在另一块的下面，并且要对齐（即，下面一行的瓷砖必须移动，这样相邻的相同尺寸的瓷砖之间就不会有看起来像十字的间隙）
使用最少数量的瓷砖
超出矩形边界的瓷砖将被修剪到边缘；由此产生的不完整瓷砖将被破碎成更小的瓷砖；这可能涉及使用一种特殊的瓷砖，该瓷砖应始终位于矩形边缘或孔的边缘，无论情况如何
以下是我迄今为止所做的尝试：
我已经研究了使用domino平铺来解决这个问题的算法，但是大多数人似乎并不关心平铺过程不会产生看起来像是平铺相交处的十字的间隙。另外，对我来说，这个问题似乎有点不同，因为有更多类型的瓷砖，而且矩形似乎不必完全填充（小的空间可能保持在使用特殊瓷砖填充的边缘附近）
我尝试了使用带有状态节点修剪的分支和绑定技术生成所有可能的平铺，以便只探索那些没有破坏约束的平铺添加的状态，但这绝对是不可伸缩的。
我也研究过打包算法，但据我所知，这可能会导致某些瓷砖的地方，有一些小的未经整理的空间，可以留在墙的前提。
可能是我忽略了一些东西，或者在探索上述技术时没有足够的洞察力。
这么说来，你们有什么建议或建议来解决这个问题吗？
This is an example of a tiling which respects constraints 1 and 3, but is not optimal
最佳答案
你需要最佳的瓷砖，还是你愿意满足于“相当好”？找到最佳解决方案可能非常困难直觉上，我建议采用以下启发式方法：
1. Pretend there are no holes in the wall, tile with large tiles.
2. Remove all tiles which intersect with holes.
3. current_size = largest
4. For each empty space: tile as much as possible with current_size
5. current_size = the size just below current_size
6. return to 4
关于algorithm - 固定大小的瓷砖拼贴矩形，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/7921583/