×
INTELLIGENT WORK FORUMS
FOR COMPUTER PROFESSIONALS

Log In

Come Join Us!

Are you a
Computer / IT professional?
Join Tek-Tips Forums!
  • Talk With Other Members
  • Be Notified Of Responses
    To Your Posts
  • Keyword Search
  • One-Click Access To Your
    Favorite Forums
  • Automated Signatures
    On Your Posts
  • Best Of All, It's Free!
  • Students Click Here

*Tek-Tips's functionality depends on members receiving e-mail. By joining you are opting in to receive e-mail.

Posting Guidelines

Promoting, selling, recruiting, coursework and thesis posting is forbidden.

Students Click Here

Square splitting

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

Let's see if I understand this.  You're given a square with length n per side and you're told to split it into a number of rectangles with different areas.  What is the condition?  That the single square be split up into a number of rectangles at ONCE?  Or just to see how many different sets of rectangles you can make with different areas.

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

OP's name is Cobolist... so I'm guessing integers only winky smile
 

HTH,

p5wizard

RE: Square splitting

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

RE: Square splitting

(OP)
"I have to list the lengths of every A_i "

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

Quote:

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.
What does that mean in English?

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 & Tragedian
Extra Connections Ltd

RE: Square splitting

(OP)
"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."

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,
glassesDon't let the Diatribe...
talk you to death!tongue

glassesJust traded in my old subtlety...
for a NUANCE!tongue

RE: Square splitting

I don't know if the Lebesgue Measureis the right word for it?
 
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

Since no one has suggested an algorithm yet, I'll give a brute-force solution, but it's horrible.

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

For those who didn't read the previous post beyond the first line (who wants to spoil the fun by getting a bad solution early?), here's an extra twist to the original problem:

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

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

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

I have not considered this "trivial solution" smile,
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

(OP)
"For those who didn't read the previous post beyond the first line (who wants to spoil the fun by getting a bad solution early?), here's an extra twist to the original problem:

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

"n=1 is the only solutions. You can get the Pell equation n^2-8x^2=1 "
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.
smile

RE: Square splitting

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

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

(OP)
A mistake in my computations.
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

Quote:

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.
This does not seem to be clearly true to me.  In fact, it seems that it is incorrect, but I'm not certain I can prove it either way.

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

KornGeek,
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

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.

RE: Square splitting

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.

RE: Square splitting

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

Quote (Cobolist):


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.

RE: Square splitting

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.
 

RE: Square splitting

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

Red Flag This Post

Please let us know here why this post is inappropriate. Reasons such as off-topic, duplicates, flames, illegal, vulgar, or students posting their homework.

Red Flag Submitted

Thank you for helping keep Tek-Tips Forums free from inappropriate posts.
The Tek-Tips staff will check this out and take appropriate action.

Reply To This Thread

Posting in the Tek-Tips forums is a member-only feature.

Click Here to join Tek-Tips and talk with other members! Already a Member? Login

Close Box

Join Tek-Tips® Today!

Join your peers on the Internet's largest technical computer professional community.
It's easy to join and it's free.

Here's Why Members Love Tek-Tips Forums:

Register now while it's still free!

Already a member? Close this window and log in.

Join Us             Close