Register to reply 
Tetrislike combinatorial problem 
Share this thread: 
#1
Apr1112, 03:13 AM

P: 11

Hello All,
I'm programming an applet and run over a problem I can't solve (hope this is the right place to post it): Having a 4 by 4 2d grid and 8 lineal elements: a) 1 of 4 square, b) 1 of 3 squares, c) 3 of 2 squares, and d) 3 of 1 suare: _grid: XXXX XXXX XXXX XXXX _elements: a) XXXX b) XXX c) XX  XX  XX d) X  X  X How many combinations are possible? Any piece can be rotated by 90° and any combination must use all the available elements. Any help on how to tackle the problem will be much appreciated.... thank you !! 


#2
Apr1112, 03:55 AM

Sci Advisor
P: 2,944

what are the rules for combining them? And what's with the dashes?



#3
Apr1112, 08:32 AM

P: 11

Hi Matterwave,
Thank you for asking Is there any formalized way to analyze this, or the only way is to check possible combinations by hand and multiply them? 


#4
Apr1112, 04:14 PM

Sci Advisor
P: 2,944

Tetrislike combinatorial problem
By combination, you mean different ways to fit them together, correct?
Do you want to count different rotations differently or as the same? For example, if I had the exact same lay out as one rotated 90 degrees, do I count those as 2 or 1? 


#5
Apr1112, 05:42 PM

P: 11

Hello,
Yes, I need to count all the possible ways to fit them together, counting different rotations of the same configuration as different solutions. A way to illustrate it it is as a framed puzzle, I need to count all the possible configurations that fulfill the rules inside the constrained grid space. 


#6
Apr1712, 01:07 AM

P: 11

Nobody...? any similar problem? or an idea on what method to use for tackling it? a book? Anything would help



#7
Apr1712, 02:06 AM

Sci Advisor
P: 2,944

Sorry, I was going to respond, but then I got sidetracked.
I can't think of a clever way to do it, and only a brute force counting is apparent to me at this point. 


#8
Apr1712, 02:36 AM

P: 11

Thank you Matterwave
XaXX aXXX XaXX aXXX XaXX aXXX XaXX aXXX These by 4 possible rotations, and by 2 possible mirrorlike turns (not counting diagonal symmetries, but not sure if I should): e.g. rotation of 1 by 90° to the right: XXXX aaaa XXXX XXXX etc. Then, in the remaining space of these two (X's), I found 6 possible arrangements of the element b) also by 4 rotations, and by 2 mirror turns. E.g.: XXXX aaaa bXXX bXXX bXXX etc. Then, using the elements c), was able to find 116 possible arrangements of the combination c)  d). This gives me 116 x 48 x 16 = 89,088 combinations... but now the problem is to be sure that 116 is the right number, or to eliminate similarities between groups (e.g. in the group of elements a) some symmetries are similar to some rotations). Any help/comment is more than welcomed... thanks 


#9
Apr1712, 01:54 PM

Sci Advisor
P: 2,944

The problem I see is that I don't think the answer can simply be some numbers multiplied together since putting some pieces in different ways will preclude some possibilities. For example, if I put my XXXX piece on an edge, then I have 10 ways I can put my XXX piece, but if I put my XXXX piece in the center somewhere then I only have 6 ways to put the XXX piece.



#10
Apr1712, 02:39 PM

P: 161

i think you'll need brute force and heavy use of symmetries. for example, when placing xxx piece on the 3x4 subboard, while there are 10 total placements, there are only 4 that are distinct. [edit] also notice that some subconfigurations are not possible with the remaining pieces.



#11
Apr1912, 04:47 AM

P: 11

Thanks, I'll try this way and post any advances,



Register to reply 
Related Discussions  
Combinatorial problem  Differential Geometry  6  
Combinatorial problem  General Math  0  
1st combinatorial problem  Precalculus Mathematics Homework  3  
3rd Combinatorial problem  Precalculus Mathematics Homework  1  
2nd combinatorial problem  Precalculus Mathematics Homework  2 