How to solve an equation with truncated unknowns?

Question

In order to provide some context, here's the problem that took me to the question:

I'm attempting to fill a rectangle of known dimensions (w: width, h: height) with squares whose side is s. I also know the total amount of squares that need to be on the screen, let's call it t. Another restriction that this arrange must meet is that the squares will be aligned in a grid (i.e. there could be "empty" cells on the grid, but the squares must be aligned).

So, the first approach to tackle this, would be to imagine a different problem. Let's say that I know the size of the squares and I want to know how many do they fit inside the rectangle. So, horizontally it would be trunc(w/s) and vertically trunc(h/s) resulting in the next equation:

t = trunc(w/s) * trunc(h/s)

So, with this equation in hand, I would love to solve s, since it's my original unknown, and I would have it. However, I have no idea how to do algebra with this truncations.

EDIT 1: Actually, I made a mistake. Maybe the equation isn't solvable for certain values, but if it's OK to leave "blank" cells, then we can safely operate with the following inequation instead of the original equation:

t $\ge$ trunc(w/s) * trunc(h/s)

Answer 1

Assuming $w$, $h$ and $t$ are given positive integers, where $t \le w \cdot h$, and that $s$ must be a positive integer, the following algorithm finds $s$:

$s = Min(w, h, \lfloor \sqrt {\frac{w \cdot h}{t}} \rfloor)$

$t' = \lfloor \frac{w}{s} \rfloor \cdot \lfloor \frac{h}{s} \rfloor$

$While \; t' \lt t \; do$

$ s = s - 1$

$t' = \lfloor \frac{w}{s} \rfloor \cdot \lfloor \frac{h}{s} \rfloor$

$End \; While$

The algorithm starts by assigning an approximate value to $s$ which is always larger or equal to the final value. It then calculates the largest grid size that can be made with this value. If the grid size is too small, it decreases $s$ until the grid size is greater than or equal to the needed size $t$.

In the trials I did, the maximum number of times it cycled through the loop was $3$.

Let me know what you think.

Answer 2

I assume that you are looking for squares filling as much as possible, so that $s$ must be an exact divisor of $w$ or $h$.

Let $w=n_xs$. Then we can fit $n_y=\lfloor\frac hs\rfloor$ squares vertically, for a total of $\frac ws\lfloor\frac hs\rfloor$. Similarly, fitting on the height, we have $\lfloor\frac ws\rfloor \frac hs$ squares. So we are looking for the largest $s$ that fulfills

$$\frac ws\left\lfloor\frac hs\right\rfloor,\left\lfloor\frac ws\right\rfloor \frac hs\le t.$$

From this,

$$s\approx\sqrt{\dfrac{wh}t}$$

any you can compute the corresponding $n_x,n_y$ and you can try nearby values.