ALMOST SQUARING THE SQUARE: OPTIMAL PACKINGS FOR NON-DECOMPOSABLE SQUARES

ABSTRACT We consider the problem of finding the minimum uncovered area (trim loss) when tiling non- overlapping distinct integer-sided squares in an N × N square container such that the squares are placed with their edges parallel to those of the container. We find such trim losses and associated optimal packings for all container sizes N from 1 to 101, through an independently developed adaptation of Ian Gambini’s enumerative algorithm. The results were published as a new sequence to The On-Line Encyclopedia of Integer Sequences®. These are the first known results for optimal packings in non-decomposable squares.

摘要：我们研究在N×N正方形容器内平铺互不重叠、边长均为整数且各不相同的正方形（所有正方形的边均与容器边平行）时，求解最小未覆盖面积（即修整损耗，trim loss）的问题。我们通过独立改进Ian Gambini的枚举算法，得到了容器尺寸N从1到101的全部场景下的最优修整损耗值与对应的最优平铺方案。相关研究成果已作为全新序列发表于《在线整数序列百科全书®》。这也是目前已知的首个针对不可分解正方形容器内最优平铺问题的研究成果。