math - 将 9×3 矩形分成 8 个相等大小的正方形

Question

你准备好你最喜欢的布朗尼食谱，然后倒入新的 9×3 英寸烤盘中。布朗尼蛋糕烘烤。牙签出来是干净的。现在进行切割。

正方形是巧克力蛋糕最美味的形状。你要为八个人服务。你怎么能把你刚出炉的东西切成八块呢？

Answer 1

所以这本质上是装箱问题的一种变体（众所周知，它是NP-hard！）。

一种解决方案是使用2个3x3方格、12x2个方格和5个1x1方格，如下：

该解决方案显然是非唯一的，因为各个方格的位置可以左右排列。

由于NP-hardness，我想很难想出一种有效的算法来将一般NxM矩形k精确地划分为正方形。事实上，必须有整个系列的参数值无法解决（例如，如果你从一个6x1矩形开始，就不可能分成少于 6 个正方形的任何东西......）。