## Square splitting

## Square splitting

(OP)

I have been given a square board with side length n. I have to split it as many rectangles as possible with different areas. What is a suitable algorithm to do the job? (n is not very large, say n about 50).

## RE: Square splitting

One thing I will say: The number of rectangles would be infinite unless you specified a limit upon the conditions. If we let X and Y be the dimensions of a rectangle made out of this square, X and Y (for example) would have to be made integers before a limited result could be obtained.

I guess it's clear that I'm not quite understanding the problem as you have specified it. Of course, one of the key rules of computer science is that a well-stated problem is a problem half-solved. So you might want to clarify yourself.

Measurement is not management.

## RE: Square splitting

HTH,

p5wizard

## RE: Square splitting

## RE: Square splitting

Sorry. Sctually I have to list width and height of every A_i and their position on a board. So for example 6x6 board can be split into four pieces like this:

SSSS))

SSSS))

hhhh))

$$$$$$

$$$$$$

$$$$$$

## RE: Square splitting

As I understand it, you have to split up an integer-sized square into the maximum number of integer-sized rectangles, where no two rectangles have the same size.

Do the rectangles have to be, well,

rectangles? Are squares allowed?-- Chris Hunt

Webmaster & TragedianExtra Connections Ltd

## RE: Square splitting

True. And no two rectangles overlaps.

"Do the rectangles have to be, well, rectangles? Are squares allowed?"

Squares are allowed as they are rectangles.

## RE: Square splitting

cobolist,

Unfortunately, you have made yourself irrelevant to many browsers, by your careless inattention to relevant details in your original post.

What other requirements are you going to change? Few are going to waste their time dabbling in your uncertainties.

Skip,

^{Don't let the Diatribe...talk you to death!}_{Just traded in my old subtlety...for a NUANCE!}## RE: Square splitting

I have a question to your example:

SSSS))

SSSS))

hhhh))

$$$$$$

$$$$$$

$$$$$$

Do you mean hhhh on chessboard has Lebesque Measure of dimension 2?

I think in the plain geometry a point would be a object with Lebesgue Measure of 0, a line Lebesgue Measure of 1 and a part of plain would have Lebesgue Measure of 2.

Transfered to the chess board, which is however differently to the plain a discrete set, instead of a point we can take a field, instead of a line we can take a row or column etc...

So IMHO your hhhh, which is a part of row has a measure (in Sence of Lebesgue) of 1 and not 2 as you explain.

Now apart of the Lebesgue Measure: Is this problem generally solvable or not?

Let us take a trivial example: square board of 2x2. Then there isn't a solution.

If I try e.g.

AB

xB

I have 2 rectangles A and BB, |A| < |BB| but x is invalid because |x| =|A|

INHO: this task doesn't have a solution.

Now let us take a task of 3x3:

The possible solutions are:

AAB

CCB

CCB

or

ABB

CCC

CCC

I.e. the maximum of rectangles is 3.

## RE: Square splitting

Consider the square as being divided up into 1*1 integer cells, each bounded by walls. The walls can be "on" or "off". The idea is to find situations where all the shapes left between the walls are rectangular (including square), and all are of different area. Therefore go through every combination of walls being on or off, and test for this condition.

For a square of side n, there are 2(n-n)n walls, so the algorithm would appear to scale as n-squared, which is already not nice (though almost to be expected from a problem dealing with area). However, it's worse than this, as the number of cases increases with n-squared, but so does the complexity of testing each case, so it may well scale as badly as n to the fourth.

Of course you can do a few simple optimisations, such as failing the test as soon as two rectangles have the same size, or a shape fails to be a rectangle. Whole ranges of wall combinations can be rejected, because if the walls at the top left corner already form a non-rectangle, changing a wall outside this shape will never correct the situation. Further, once you've found a "good" combination, you may be able to reject many bad combinations early, because if the remaining area to test is too small to contain enough rectangles to reach the "good" value, it must already be bad.

## RE: Square splitting

The maximum number of rectangles of different area we can put into any shape is clearly 1+2+3+4...+x (since this uses all possible areas). A square has area n-squared. So presumably somewhere there are squares where:

n^2 = 1+2+3...+x.

Firstly: can we find which values of n will do this?

Secondly: can we prove whether or not there is any practical way to arrange the rectangles so they'll fit?

Actually the second part is very easy for most specific squares.

## RE: Square splitting

If I try e.g.

AB

xB"

There is a solution:

AA

AA

I'm sorry using the word Lebesgue measure. As a mathematician I just think areas as Lebesgue measures. So nxn board has measure n^2.

## RE: Square splitting

instead I thought about a task to find 2 or more disjunctive rectangles A_1,...,A_m so that |A_1|<|A_2|<...<|A_m|

## RE: Square splitting

The maximum number of rectangles of different area we can put into any shape is clearly 1+2+3+4...+x (since this uses all possible areas). A square has area n-squared. So presumably somewhere there are squares where:

n^2 = 1+2+3...+x.

Firstly: can we find which values of n will do this?"

n=1 is the only solutions. You can get the Pell equation n^2-8x^2=1 and solve it via standard technique.

## RE: Square splitting

Don't un understand. Wherefore is the above equation?

I used this approach:

Tried to construct rectangle of size 1, then rectangle of size 2,...

So if I have constructed rectangle of size k, I tried to construct rectangle of size k+1, if it was not possible then rectangle of size k+2,...etc

Results:

For n=1, we have only trivial solution i.e one rectangle of surface 1, because

1^2 = 1

For n=2, we have only trivial solution i.e one rectangle of surface 4, because

2^2 = 4

For n=3:

3^2 = 1 + 2 + 6 (3 rectangles - of sizes 1, 2 and 6)

For n=4:

4^2 = 1 + 2 + 3 + 4 + 6 (5 rectangles)

For n=5:

5^2 = 1 + 2 + 3 + 4 + 5 + 10 (6 rectangles)

For n=6:

6^2 = 1 + 2 + 3 + 4 + 6 + 8 + 12 (7 rectangles)

For n=7:

7^2 = 1 + 2 + 3 + 4 + 5 + 6 + 10 + 18 (8 rectangles)

For n=8:

8^2 = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 12 + 24 (9 rectangles)

So, this leads me inductive to this presumption:

For n >= 4 the maximal number of rectangles is n+1.

You can proove if it's true or false using mathematical induction.

## RE: Square splitting

http://r

## RE: Square splitting

Not sure that's true. For example, it works for n=6, x=8

n^2 = 36

36 = 1+2+3+4+5+6+7+8

However, I'm utterly sure that you cannot divide a 6-by-6 square into 8 different sized rectangles (you can, of course, divide it into 8 shapes of different integer area if you don't mind non-rectangular shapes).

Also I'm not sure of the equation. The area of the sum of shapes area 1+2+3...x is given by

((x+1)/2)*x

=(x^2 + x)/2

The area of the square is n^2

So the equation is

n^2 = (x^2 + x)/2

=> 2(n^2) = x^2 + x

You'll notice that both sides of the equation = 72 for the example n=6, x=8

## RE: Square splitting

x_{i+1}=3x_i+4n_i+1

n_{i+1}=2x_i+3n_i+1

is the recursion which gives the solutions.

## RE: Square splitting

If I'm understanding you correctly, it seems that you are focusing exclusively on rectangles of size 1 by y (where y is an integer from 1 to x). Keep in mind that rectangles of size 1x4 and 2x2 both have the same area, but their differing dimensions permit both to be in the solution.

## RE: Square splitting

Thanks for the comment. To clear up possible misunderstanding, no, I'm just considering that no two rectangles are allowed to have the same area, so the absolute maximum number of rectangles into which we can divide any shape is 1+2+3... where these values are the areas, all possible areas being represented. I don't mind whether area 4 is represented by a 1*4 or a 2*2 block.

I'm also inclined to think no such square exists. When I suggested the first question, I think I meant "how do we find the pairs of values n and x satisfying n^2=1+2+..n".

The second part of the question is how do we prove whether there is actually a genuine square out there that can be divided this way.

The obvious thought that springs to mind is that no square n can be divided this way if there is a prime number between x and n, since prime numbers can only be rectangles 1 unit wide, and if this rectangle is bigger than n, it doesn't fit in the square. I'm pretty sure prime numbers appear a lot more frequently than squares! But the progression of prime numbers is way outside my knowledge.

## RE: Square splitting

I get that you don't care whether the rectangle with area 4 is represented by a 1x4 block or a 2x2 block, but I'm suggesting that both would need to be considered.

So, the progression would be more like

1(1x1), 2(1x2), 3(1x3), 4(1x4), 4(2x2), 5(1x5), 6(1x6), 6(2x3), 7(1x7), 8(1x8), 8(2x4), 9(1x9), 9(3x3), 10(1x10), 10(2x5), 11(1x11), 12(1x12), 12(2x6), 12(3x4)...

or

1, 2, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 9, 10, 10, 11, 12, 12, 12, ...

Otherwise, you could end up with an area 10 block of 2x5 that could be subdivided into a 2x2 and a 2x3 just because you previously used a 1x4 and a 1x6.

## RE: Square splitting

but the definition of the puzzle prohibits rectangles to have the same area, not only to have the same shape.

Some citations of cobolist:

1. citing

cobolist:"as many rectangles as possible with different areas"

2. citing

Chris Hunt: "...you have to split up an integer-sized square into the maximum number of integer-sized rectangles, where no two rectangles have the same size."

cobolist: "True. And no two rectangles overlaps."

You may only conduct that in fact both 1x4 and 2x2 are allowed in a solution by the more mathemtical description cobolist gave:

3. citing

I have to find rectangles A_1,...,A_m with integer sides such that A_i intersection A_j = emptyset for every i < j, |A_1|<|A_2|<...<|A_m| (|A_i| means the size of A_i, 2-dimensional Lebesgue measure) if they are ordered by size, and A_1 union A_2 ... union A_m equals nxn-board. I have to list width and height of every A_i and their position on a board.

This definition of the task DOES in fact even allow to split the chessboard in n<2 single square rectangles. So I assume the real and full task is still not described, but somehow we understand it makes no sense that two same rectangles are allowed, we still don't know if the area of those rectangles is allowed to repeat, if it's a different shape.

Cobolist, can't you simply paste in the full quote of your homework? Or leave this forum alone and doing your homework alone?

Bye, Olaf.

## RE: Square splitting

## RE: Square splitting

From the point of view of developing algorithms, this is quite an important feature of the problem. It means we can keep data on rectangles in a straightforward, easily maintained array, rather than messing around with linked lists. We know there can be only one entry for each area. We also know how big the array needs to be. Further, we can stop our searching early when we're examining a particular layout. If, for instance, we choose to fill our space from small rectangle towards large, as soon as the remaining area of square to be filled is less than the current rectangle size, we know we can't fill it, and can abandon the current layout of rectangles.

## RE: Square splitting