# How big do squares need to be to fit a box, tesselating, with minimal remainder?

A geometry question that I feel utterly defeated by. I'm trying to design a responsive user interface that efficiently fits a variable number of square elements on a screen, by adjusting the size of the squares. With a known square size, the number of squares along and up will be implicit. I'm also very interested to know the answer.

I describe the problem as thus:

A known number of squares, n, must be fit as efficiently as possible (least remaining area) into a rectangle of known dimensions x & y. The dimension (equal width and height) of the squares, s, must be adjusted to achieve this. The squares must be axis-aligned. Find s.

All I've been able to establish is that where n/(w/h) is an integer, n + 1 is a worst case scenario of remainder. I can't seem to get any more facts to come out in the wash, but am interested in the working of the answer.

Update:

I've worked out (I hope), the maximum number of squares that may be fit, as follows:

max squares =
( floor( longest side / shortest side ) * divisor^2 ) +
( floor( r / ( shortest side / divisor ) ) * divisor )


Based on fitting squares with a size of the shortest side of the rectangle, dividing them down by the divisor (iteratively until enough squares are achieved), each time seeing how much of the remainder can be occupied by the divided down dimension.

Now I just need to turn this into a single formula so it doesn't have to be computed iteratively, if possible.

• If I follow it right, $s=1$ will have no remaining area, but is there a balance between square size and remaining area? – Empy2 May 19 '16 at 15:52
• All squares must be the same size. The problem is to find a size where all squares fit the rectangle, with the least possible remainder of space. In some cases there might be no remainder at all; e.g. a rectangle of width 4 units and height 2 units, of which 8 squares must be fit, in which case s = 1 unit. If the width were increased to 4.1 units the solution would be the same, but there would now be a remainder of 0.2 units^2. – Toby Wilson May 20 '16 at 7:59

I'm decently sure this can be accomplished by simply adding the largest possible square i.e. has the minimum of width or height as side length. put square on side of rectangle and you end with a rectangle demension $x$ and $y-x$ without loss of generality. then simply repeat until either there's no remainder or your out of number of squares.