Algorithm to fill rectangle with small squares?

Given a rectangle with width and height, fill it with n squares (n is integer, also given), such that the sq开发者_运维百科uares cover as much of the rectangle's area as possible. The size of a single square should be returned.

Ideas?

The squares do not necessarily have to be oriented the same as the larger rectangle. These sorts of problems are known as packing problems, and finding optimal solutions is notoriously hard.

For an excellent treatment in the case when the larger shape into which the n squares are packed is a square, see Erich Friedman's paper Packing Unit Squares in Squares: A Survey and New Results

For example, Gödel was the first to publish on this subject. He found that a2+a+3+(a-1)√2 squares can be packed in a square of side a+1+1/√2 by placing a diagonal strip of squares at a 45 degree angle. For example,

And just for fun, I highly recommend you check out Erich's Packing Center.

Assuming that all the squares are aligned and they are the same size, you can find this by binary searching on the side length of the square:

import math

def best_square(w, h, n):
    hi, lo = float(max(w, h)), 0.0
    while abs(hi - lo) > 0.000001:
        mid = (lo+hi)/2.0
        midval = math.floor(w / mid) * math.floor(h / mid)
        if midval >= n:
            lo = mid
        elif midval < n: 
            hi = mid
    return min(w/math.floor(w/lo), h/math.floor(h/lo))

I know that question was a long time ago, but here is what i though :

you have n square you have a rectangle you want to know the size of the square to fill the rectangle

for example :

rectangle of 1280*720 filled with 100 squares. 
The surface is 1280*720=921600
1 square should have the surface of 921600/100 = 9216
so the square size is sqrt(9216)=96

In the end it would just be a function that return the result of this :

sqrt((width*height)/n)

Here is my solution The idea is to go on a recursive loop Suppose u start with square_counter =0

While length and breath: // find the biggest possible square

Count1 = length/breath // take the floor

Square_counted += count1

New balance length = length - count1* breath

Now square with Max size possible wrt breath

Count2 = breath/length

Square_count += count2

Breath = breath - count* length