Square splitting

[cobolist]

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).

 

[KornGeek]

lionelhill,
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.

 

[Olaf Doschke]

KornGeek,

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.

 

[mikrom]

You are right Olaf, but I have understood, that the cobolist wants to find a maximum possible number of a rectangles too:

I meant that I have an nxn-board (or chessboard). Then 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. Now I have to list the lengths of every A_i and determine what is the maximum of m as a function of n.

 

[lionelhill]

Absolutely, Korngeek! If we have already got a rectangle elsewhere whose area is 4, irrespective of shape, you are right that we cannot subdivide our rectangle 2*5 into anything that also contains an area of 4.

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.

 

[KornGeek]

Thanks Olaf for pointing out what I was clearly overlooking. I had read the puzzle to be "no two rectangles of the same size" rather than "no two rectangles of the same area". I now see my mistake.