I am looking for an algorithm that can return the number of size of n squares that fit into a a rectangle of a given width and height, maximizing the use of space (thus, leaving the least amount of leftover space for squares that do not fit). Neither the rectangle nor the squares can be rotated.

For example, let's say I have a rectangle that is 5 inches by 7 inches, and I need it to fit 35 squares. The algorithm needs to tell me that the 35 squares fit if they are 1 inch wide/tall (as they could be laid out inside the rectangle in a 5 x 7 grid). Another example is if I need to divide a rectangle 35 inches by 1 inch into 35 squares. It should still tell me that the squares will fit if they are 1-inch wide/tall (as they could be laid out in the rectangle in a 35 x 1 grid).

The tricky part is that sometimes there may be leftover space, as the squares cannot be divided into partial squares. Let's say for either of the two examples above I need to lay out 34 squares and not 35 (in which case the answers would still be 1 inch), or maybe 33, or 7 squares. Or, perhaps the rectangle width and height aren't whole numbers. With the number of squares being a variable I need an algorithm that can tell me the size of the squares for a given rectangle width and height.

Thanks for your help!

  • $\begingroup$ Starting point: If you take all the squares and move them to a corner, the leftover space is much easier to calculate.(I am assuming all the squares are of equal size) $\endgroup$
    – chubakueno
    Commented Aug 12, 2013 at 22:00
  • 1
    $\begingroup$ Also, as you note in your tags, I see a formula kind of unlikely: this problems are usually solved by algorithms. The trigonometry tag is not relevant, I think. $\endgroup$
    – chubakueno
    Commented Aug 12, 2013 at 22:06
  • 2
    $\begingroup$ See squares in squares and squares in dominoes from Erich's Packing Center for some specific cases. Finding these automatically seems like a pretty hard problem. $\endgroup$
    – MvG
    Commented Aug 12, 2013 at 22:18
  • 1
    $\begingroup$ @MvG thanks for the links. I just realized that I need to clarify that squares cannot be rotated. $\endgroup$
    – Anton
    Commented Aug 12, 2013 at 22:25
  • $\begingroup$ Code on Stack Overflow: Resizing n of squares to be as big as possible while still fitting into box of X by Y dimensions $\endgroup$
    – jscs
    Commented Oct 2, 2015 at 2:13

3 Answers 3


Let's analyze a single case:

If we want to cover a $6x5$ rectangle with $7$ squares, we first note that each square at most has an area of $30/7$. We also know that for our filling to be optimal, we need to fill at least an axis.

So now we know that we will fill either the $6$ or the $5$ completely. We will first try with the 5. Since the maximal side of our squares is $\sqrt{30/7}$, we now need the smallest integer more than $5/\sqrt{30/7}$, that is equal to $\lceil5/\sqrt{30/7}\rceil=3$

So we would divide the $5$ in $3$ parts $p_x$, so each side will have $5/3$ . If so, I would cover $(5/3)^2*7=19\frac49$ of the thirty squares. If they don't fit vertically, we try with more parts $p_x$, until the squares fit in the other axis. $$\lfloor6/(5/p_x)\rfloor*\lfloor5/(5/p_x)\rfloor=\lfloor6/(5/p_x)\rfloor*p_x\ge7 \,\,\,\,\,\,\,\,\,\, (5/p_x=\text{the actual size of our squares)}$$ Also, since $p_x$ is integer $\lfloor p_x \rfloor =p_x$

If we do the same with the $6$, we get $\lceil6/\sqrt{30/7}\rceil$ again covering $19\frac49$ of the surface. We then do the same as with the $5$ and save it as $p_y$

Let's now recall the formulas we had.

We had an $x∗y$ rectangle and filled it with $N$ squares. We started with $p_x=⌈x/\sqrt{xy/N}⌉$=$⌈\sqrt{Nx/y}⌉$ or $p_y=⌈y/\sqrt{xy/N}⌉=⌈\sqrt{Ny/x}⌉$ and then we made them fit by shrinking them until they fit in the other axis. But we know we want the area maximised, so $Side=max(x/p_x,y/p_y)$.

A better method:

Once we have the start value $p_x=⌈x/\sqrt{xy/N}⌉=⌈\sqrt{Nx/y}⌉$,if it does not fit in the $y$ axis, we need to make it fit in the $y$ axis. For that, we use that $$a=x/p_x$$ where $a$ is the value of the actual side of our squares. Then we know that for our side to fit we need to reduce it: $$S_x=y/(\lceil y/a \rceil)$$ We do the same with $S_y$ and calculate $max(S_x,S_y)$ The advantage of this is that it needs a constant number of operations, the most expensive one being the square root.

Plain, unoptimized C Code

Some multiplications may be reused but for code readability and practical uses this is enough. Input: values of $x$,$y$, and $n$. Handcoded.

Output: The optimal side of our squares

#include <math.h>
#include <stdio.h>
#define MAX(x,y)    (x)>(y)?(x):(y) 
int main(){
    double x=5, y=6, n=7;//values here
    double px=ceil(sqrt(n*x/y));
    double sx,sy;
    if(floor(px*y/x)*px<n)  //does not fit, y/(x/px)=px*y/x
            sx= x/px;
    double py=ceil(sqrt(n*y/x));
    if(floor(py*x/y)*py<n)  //does not fit
    return 0;
  • $\begingroup$ Thank you for the detailed answer. I'm going to give it a go tonight/tomorrow morning. Right now I'm having a little trouble wrapping my head around what to do after calculating P(x), when it comes to reducing. $\endgroup$
    – Anton
    Commented Aug 13, 2013 at 0:20
  • $\begingroup$ @Anton I posted now a method to reduce it without any iterations, so it is $O(\text{the time your sqrt function takes})$ $\endgroup$
    – chubakueno
    Commented Aug 13, 2013 at 0:32
  • 3
    $\begingroup$ @Anton The notation $O(n)$ is the notation of asymptotic complexity. One of it's basic properties is that you just care about the highest order term and you drop all the constants, for example $O(5x^2+x+1)$=$O(x^2)$. It is a useful way of noting the time complexity of your algorithm. In this case, the slowest operation is the square root. Since there are varying implementations, I wrote $O(\text{the time your sqrt function takes})$ because I don't know your code implementation. Assuming you will code this, this makes sense. If you are doing this by hand, this is unimportant :). $\endgroup$
    – chubakueno
    Commented Aug 13, 2013 at 1:36
  • 1
    $\begingroup$ @Anton here is some code ideone.com/fwcmoc, outputs the side of the square. $\endgroup$
    – chubakueno
    Commented Aug 13, 2013 at 4:00
  • 1
    $\begingroup$ @chubakueno can you please check the generic formulas after "We started with", there seems to be some inconsistencies with $p_x$ and $p_y$ in the text. Also can you please explain how you went from $x/\sqrt{a}$ to just $\sqrt{b}$? $\endgroup$
    – TWiStErRob
    Commented Sep 8, 2014 at 21:10

chubakueno's solution doesn't always work. Take for example $x=10$, $y=2$ and $n=8$. His algorithm returns 1 whereas the biggest square size is obtained by fitting one single line of eight squares, and is therefore $10/8=1.25$.

Below is an algorithm that works, written in Javascript. It also has the advantage of computing the minimum number of rows and columns, on top of the square size. Inputs are x, y and n.

// Compute number of rows and columns, and cell size
var ratio = x / y;
var ncols_float = Math.sqrt(n * ratio);
var nrows_float = n / ncols_float;

// Find best option filling the whole height
var nrows1 = Math.ceil(nrows_float);
var ncols1 = Math.ceil(n / nrows1);
while (nrows1 * ratio < ncols1) {
    ncols1 = Math.ceil(n / nrows1);
var cell_size1 = y / nrows1;

// Find best option filling the whole width
var ncols2 = Math.ceil(ncols_float);
var nrows2 = Math.ceil(n / ncols2);
while (ncols2 < nrows2 * ratio) {
    nrows2 = Math.ceil(n / ncols2);
var cell_size2 = x / ncols2;

// Find the best values
var nrows, ncols, cell_size;
if (cell_size1 < cell_size2) {
    nrows = nrows2;
    ncols = ncols2;
    cell_size = cell_size2;
} else {
    nrows = nrows1;
    ncols = ncols1;
    cell_size = cell_size1;
  • $\begingroup$ how could I apply your solution to a similar problem but for a collection of rectangles with fixed aspect ratios of w/h = 3/2 and w/h = 2/3? If you'd like I can create a new question for it. Thanks! $\endgroup$ Commented Aug 17, 2020 at 13:06
  • 2
    $\begingroup$ @inyourcorner Sorry for the delay. You could divide ratio by your rectangle's aspect ratio rect_ratio in the beginning, apply the algorithm, and then your cell size will be x = rect_ratio * cell_size, y = cell_size, if I'm not mistaken. $\endgroup$
    – Neptilo
    Commented Aug 31, 2020 at 22:04
  • $\begingroup$ This makes sense - thanks for confirming, and for the help $\endgroup$ Commented Sep 10, 2020 at 16:44
  • $\begingroup$ perfect - just what I needed $\endgroup$
    – ashleedawg
    Commented Aug 14, 2021 at 8:52

Credit for the algorithm is entirely from chubakueno's answer. I'm just posting a C# version of it here in case anyone else needs it.

/// Calculates the optimal side of squares to be fit into a rectangle
/// Inputs: x, y: width and height of the available area.
///         n: number of squares to fit
/// Returns: the optimal side of the fitted squares
double FitSquares(double x, double y, int n)
    double sx, sy;

    var px = Math.Ceiling(System.Math.Sqrt(n * x / y));
    if (Math.Floor(px * y / x) * px < n) {
        sx = y / Math.Ceiling(px * y / x);
    } else {
        sx = x / px;

    var py = Math.Ceiling(System.Math.Sqrt(n * y / x));
    if (Math.Floor(py * x / y) * py < n) {
        sy = x / Math.Ceiling(x * py / y);
    } else {
        sy = y / py;

    return Math.Max(sx, sy);
  • $\begingroup$ this does not take into consideration the w & h of the smaller squares? $\endgroup$
    – Smith
    Commented Feb 1, 2018 at 8:15
  • $\begingroup$ No, it assumes we always want to fit squares of fixed sizes. $\endgroup$
    – Petrucio
    Commented Feb 1, 2018 at 20:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .