Sign in to follow this  
HellRaiZer

Tetris packing with complex shapes

Recommended Posts

Hi... I have a problem and i don't know how to search for a possible answer. I have an infinite number of things with this shape: Tetris Block and an empty 2D lattice. I want to fill this lattice with as much of these things as i can, thus minimizing the free space in the lattice. Any object can be rotated +-90 degrees. Because of the shape is symmetric in both x and y axis, only one rotation makes sense. Every colored square in the shape has exactly the same dimensions as the others. This looks a lot like Tetris, but with more complex shapes. I tried to search how this can be done, but i haven't found something useful (a paper, an algorithm). Does somebody have any suggestions/papers on that? Any keywords for searching on Google? Anything? As you can figure out, packing multiple objects like the above, always leave some empty space. This is because you can't have one object perfectly fit inside the other. There will always be some empty cells, left and right of the blue cells. Knowing this, is there any way i can calculate the minimum empty space that can be formed inside an arbitrary lattice? Thanks in advance. And if you have any questions, please ask. HellRaiZer

Share this post


Link to post
Share on other sites
Quote:
Original post by lima
is this a homework assignment?

No. I have stopped doing any homework 1.5 years ago (when i graduated from uni) :)

After all i'm not asking for the solution. I'm asking for directions/suggestions/etc. Something to read on the subject. I don't even know if this is possible, so i'm searching. Don't you think that if this was homework, i would already have something to start searching?

Do you have any info on that?

HellRaiZer

Share this post


Link to post
Share on other sites
Quote:
Original post by HellRaiZer
After all i'm not asking for the solution. I'm asking for directions/suggestions/etc. Something to read on the subject. I don't even know if this is possible, so i'm searching. Don't you think that if this was homework, i would already have something to start searching?
Do you have any info on that?


Look for the algorithm called 'back tracking'...

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this