<p>Since you are not interested in the best performance rather easy coding,
it would be a good idea to colour the region of covered area. The algorithm
would look like the following:</p>

<blockquote>
  <p>Colour(x,y,w,d): Fill the rectangle starting from (x,y) to (x+w,y+d).  </p>
  
  <p>UnColour(x,y,w,d): Empty the rectangle starting from (x,y) to (x+w,y+d).  </p>
  
  <p>Check(x,y,w,d): Verify if rectangle starting from (x,y) to (x+w,y+d) is empty? </p>
  
  <p>maxC = maximum count</p>
</blockquote>

<p>PSEUDO-CODE: Invoke SOLVE(w,d,W,D,0)</p>

<p>Solve(w,d,W,D,C)</p>

<blockquote>
  <p>if(C>maxC) maxC=C</p>
  
  <p>for (y=1,y&lt;=D,y++)</p>
  
  <blockquote>
    <p>for (x=1,x&lt;=W,x++)</p>
    
    <blockquote>
      <p>if(Check(x,y,w,d))</p>
      
      <blockquote>
        <p>Colour(x,y,w,d)</p>
        
        <p>Solve(w,d,W,D,C+1)</p>
        
        <p>UnColour(x,y,w,d)</p>
      </blockquote>
      
      <p>if(Check(x,y,d,w))</p>
      
      <blockquote>
        <p>Colour(x,y,d,w)</p>
        
        <p>Solve(w,d,W,D,C+1)</p>
        
        <p>UnColour(x,y,d,w)</p>
      </blockquote>
    </blockquote>
  </blockquote>
</blockquote>

CC BY-SA 3.0
2017-09-16T07:17:33.523Z
why do you start at y=x=1? instead of 0?
E. Williams
CC BY-SA 3.0
2017-09-17T08:16:51.000Z
That is just a convention. Depending upon your needs you can either
store it in [1,W]x[1,D] or [0,W-1]x[0,D-1]. Either one can be used. Former
is sometimes  better for understanding, later one is used for efficient coding. Essentially what the code does is try to put a block where ever possible and recurse.
sbzk
CC BY-SA 3.0
2017-09-17T08:17:21.330Z
It can be greatly improved by some techniques/heuristics as follows.
(1) If Check(x,y,w,d) is successful, do not try Check(x+x',y+y',w,d) for any x',y'>=0. This is because one can prove any solution from later, can also be achieved using the former.
(2) Stopping the Check operation as soon as any unsuccessful cell is found.
(3) Using advanced data structures for performing Check, Colour, Uncheck in O(nlog n) time instead of O(n^2) where n = max(w,d). One such data structure is called a Segment Tree.
sbzk
CC BY-SA 3.0
2017-09-17T19:08:30.667Z
Thanks, nice explanation. But could you explain me better the first heuristic? ( (1) If Check(x,y,w,d) is successful, do not try Check(x+x',y+y',w,d) for any x',y'>=0.)
E. Williams
CC BY-SA 3.0
2017-09-18T10:00:55.080Z
Assume, we have filled the space only from [1,x]x[1,y]. Hence Check(x,y,w,d) is successful and also each  Check(x+x',y+y',w,d) for any x',y'>0 are successful. But we essentially would like to pack the rectangles as close as possible. So there is no point leaving a entire row (for x) or column (for y) and placing the rectangle after a gap. What ever solution works for such a placement, will also work for placement at (x,y) as you would only be leaving more space for placement to the right and bottom.
sbzk
CC BY-SA 3.0
2017-09-15T08:16:01.867Z
2017-09-15T08:16:01.867Z
sbzk
<p>A conceptually far simpler algorithm is to try all the options. Cut the rectangle into $g=gcd(w,\ell)$ squares. There are finitely many ways to portion these squares into non-overlapping blocks that form allowable rectangles. Ennumate them and try all the options.</p>

<p>This is pretty bad, but unless you're going to do something more clever than "try all the options on the tree" it's going to be the same  worst case run-time up to factors ignored by big-O. And possibly even the same in all case, I'm not quite sure.</p>

CC BY-SA 3.0
2017-09-15T06:19:07.153Z
I cannot understand you, could you please extend your explanation? I would appreciate it. For example for a 4x3 rectangle should you cut it into 1 squares?
E. Williams
CC BY-SA 3.0
2017-09-15T11:31:50.540Z
@E.Williams Correct. You're cutting it into a grid such that both side lengths of the smaller rectangle are multiples of the grid side length
Stella Biderman
CC BY-SA 3.0
2017-09-15T12:58:55.317Z
Thanks have you got a more extensive explanation about this idea?
E. Williams
CC BY-SA 3.0
2017-09-15T13:00:32.343Z
@E.Williams I'm not sure where my explanation is going awry. So you have a grid and you overlay it on the object square, right? The possible ways to divide the grid squares into rectangles is easier to enumerate than your tree. So you can just enumerate all coverings that way.
Stella Biderman
CC BY-SA 3.0
2017-09-14T23:58:06.940Z
2017-09-15T00:12:28.593Z
2017-09-15T00:12:28.593Z
Stella Biderman
<p>I want to create an algorithm to fill a fixed-size big rectangle (W,H) with the maximum number of fixed-size smaller rectangles (w,h) (I can rotate the small rectangles 90º).
<a href="https://i.sstatic.net/lNTfw.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/lNTfw.jpg" alt="tree"></a></p>

<p>I have thought about doing it with a k-ary tree. So each node is a possible placement of a small rectangle. There are 4 combinations to add a rectangle (vertical/horizontal and how does it divide the regions).
<a href="https://i.sstatic.net/tjUFl.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/tjUFl.png" alt="enter image description here"></a></p>

<p>Where the root node is the empty big rectangle and its children are the first level of possible combinations when adding one rectangle, the second level defines the possible combinations when a second rectangle is added, so on...</p>

<p>I have defined some objects:</p>

<pre><code>BigRectangle:
integer v1, v2, v3, v4 //the 4 vertices that define a BigRectangle.
List&lt;Region&gt; regions //contains a list of Regions contained in BigRectangle.

Region:
integer v1, v2, v3, v4 //the 4 vertices that define a region.
list&lt;SmallRectangle&gt; smallRectangles //contains a list of SmallRectangle contained in Region.

SmallRectangle:
integer v1, v2, v3, v4 //the 4 vertices that define a SmallRectangle.
integer orientation //(0|1) 0-vertical, 1-horizontal.
</code></pre>

<p>I am trying to write the algorithm but it is being a mess. I cannot figure out how to write an algorithm to simulate this tree :(</p>

<p>(I am not interested on achieving the best performance)</p>

<pre><code>1. Create and insert an empty BigRectangle as the root.

2. ...
...
</code></pre>

CC BY-SA 3.0
2017-09-14T21:06:28.993Z
Also on [cs.se]: https://cs.stackexchange.com/questions/81195/packing-identical-rectangles-in-a-bigger-rectangle.
Yuval Filmus
CC BY-SA 3.0
2017-09-15T06:34:09.827Z
The decision version of this problem is known as the pallet packing problem and is not even known to be in NP. See http://cs.smith.edu/~jorourke/TOPP/P55.html#Problem.55
Mikhail Rudoy
CC BY-SA 3.0
2017-09-15T08:00:33.760Z
But I do not find there any real implementation for a solution
E. Williams
<ds.algorithms><optimization><tree><computational-geometry><packing>
How to continue this algorithm?
E. Williams
# How to continue this algorithm?

(Asked by: username_0 on 2017-09-14)

I want to create an algorithm to fill a fixed-size big rectangle (W,H) with the maximum number of fixed-size smaller rectangles (w,h) (I can rotate the small rectangles 90º).

I have thought about doing it with a k-ary tree. So each node is a possible placement of a small rectangle. There are 4 combinations to add a rectangle (vertical/horizontal and how does it divide the regions).

Where the root node is the empty big rectangle and its children are the first level of possible combinations when adding one rectangle, the second level defines the possible combinations when a second rectangle is added, so on...
I have defined some objects:
BigRectangle:
integer v1, v2, v3, v4 //the 4 vertices that define a BigRectangle.
List regions //contains a list of Regions contained in BigRectangle.

Region:
integer v1, v2, v3, v4 //the 4 vertices that define a region.
list smallRectangles //contains a list of SmallRectangle contained in Region.

SmallRectangle:
integer v1, v2, v3, v4 //the 4 vertices that define a SmallRectangle.
integer orientation //(0|1) 0-vertical, 1-horizontal.

I am trying to write the algorithm but it is being a mess. I cannot figure out how to write an algorithm to simulate this tree :(
(I am not interested on achieving the best performance)
1. Create and insert an empty BigRectangle as the root.

2. ...
...

**Tags:** ds.algorithms, optimization, tree, computational-geometry, packing
> **Comments:**
> **username_1**: Also on [cs.se]: https://cs.stackexchange.com/questions/81195/packing-identical-rectangles-in-a-bigger-rectangle.  
> **username_2**: The decision version of this problem is known as the pallet packing problem and is not even known to be in NP. See http://cs.smith.edu/~jorourke/TOPP/P55.html#Problem.55  
> **username_0**: But I do not find there any real implementation for a solution  

---

## 2 answers

### Answer by username_3 on 2017-09-15. Score: 0 | Accepted answer

Since you are not interested in the best performance rather easy coding,
it would be a good idea to colour the region of covered area. The algorithm
would look like the following:

> Colour(x,y,w,d): Fill the rectangle starting from (x,y) to (x+w,y+d).
>
> UnColour(x,y,w,d): Empty the rectangle starting from (x,y) to (x+w,y+d).
>
> Check(x,y,w,d): Verify if rectangle starting from (x,y) to (x+w,y+d) is empty?
>
> maxC = maximum count

PSEUDO-CODE: Invoke SOLVE(w,d,W,D,0)

Solve(w,d,W,D,C)

> if(C>maxC) maxC=C
>
> for (y=1,y<=D,y++)
>
> > for (x=1,x<=W,x++)
> >
> > > if(Check(x,y,w,d))
> > >
> > > > Colour(x,y,w,d)
> > > >
> > > > Solve(w,d,W,D,C+1)
> > > >
> > > > UnColour(x,y,w,d)
> > >
> > > if(Check(x,y,d,w))
> > >
> > > > Colour(x,y,d,w)
> > > >
> > > > Solve(w,d,W,D,C+1)
> > > >
> > > > UnColour(x,y,d,w)

> **Comments:**
> **username_0**: why do you start at y=x=1? instead of 0?  
> **username_3**: That is just a convention. Depending upon your needs you can either store it in [1,W]x[1,D] or [0,W-1]x[0,D-1]. Either one can be used. Former is sometimes  better for understanding, later one is used for efficient coding. Essentially what the code does is try to put a block where ever possible and recurse.  
> **username_3**: It can be greatly improved by some techniques/heuristics as follows. (1) If Check(x,y,w,d) is successful, do not try Check(x+x',y+y',w,d) for any x',y'>=0. This is because one can prove any solution from later, can also be achieved using the former. (2) Stopping the Check operation as soon as any unsuccessful cell is found. (3) Using advanced data structures for performing Check, Colour, Uncheck in O(nlog n) time instead of O(n^2) where n = max(w,d). One such data structure is called a Segment Tree.  
> **username_0**: Thanks, nice explanation. But could you explain me better the first heuristic? ( (1) If Check(x,y,w,d) is successful, do not try Check(x+x',y+y',w,d) for any x',y'>=0.)  
> **username_3**: Assume, we have filled the space only from [1,x]x[1,y]. Hence Check(x,y,w,d) is successful and also each  Check(x+x',y+y',w,d) for any x',y'>0 are successful. But we essentially would like to pack the rectangles as close as possible. So there is no point leaving a entire row (for x) or column (for y) and placing the rectangle after a gap. What ever solution works for such a placement, will also work for placement at (x,y) as you would only be leaving more space for placement to the right and bottom.  

---

### Answer by username_4 on 2017-09-14. Score: 1

A conceptually far simpler algorithm is to try all the options. Cut the rectangle into $g=gcd(w,\ell)$ squares. There are finitely many ways to portion these squares into non-overlapping blocks that form allowable rectangles. Ennumate them and try all the options.

This is pretty bad, but unless you're going to do something more clever than "try all the options on the tree" it's going to be the same worst case run-time up to factors ignored by big-O. And possibly even the same in all case, I'm not quite sure.

> **Comments:**
> **username_0**: I cannot understand you, could you please extend your explanation? I would appreciate it. For example for a 4x3 rectangle should you cut it into 1 squares?  
> **username_4**: @E.Williams Correct. You're cutting it into a grid such that both side lengths of the smaller rectangle are multiples of the grid side length  
> **username_0**: Thanks have you got a more extensive explanation about this idea?  
> **username_4**: @E.Williams I'm not sure where my explanation is going awry. So you have a grid and you overlay it on the object square, right? The possible ways to divide the grid squares into rectangles is easier to enumerate than your tree. So you can just enumerate all coverings that way.  

---

