Tetris-like combinatorial problem

[bitttttor]

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 !

 

[Matterwave]

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

 

[bitttttor]

Hi Matterwave,
Thank you for asking

what are the rules for combining them?

The rules are: all elements need to be in the solution, without overlapping and covering the whole area of the grid. This is 1 x a, 1 x b, 3 x c, and 3 x d. Like in Tetris, all the pieces need to come together with no empty spaces between them. Also they can be rotated by 90°, i.e. they are vertical or horizontal lines, no diagonals or other shapes.

And what's with the dashes?

Sorry about the dashes, I putted them as graphic representation of separate elements: i.e. there are one element of four cells, one of three, three of two, and three of one. All together they are 16, filling the 16 cells (i.e. X) of the grid.

Is there any formalized way to analyze this, or the only way is to check possible combinations by hand and multiply them?

 

[Matterwave]

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?

 

[bitttttor]

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 http://www.tenthousandvillages.com/media/catalog/product/cache/1/image/9df78eab33525d08d6e5fb8d27136e95/6/8/6891610_1_1.jpg, I need to count all the possible configurations that fulfill the rules inside the constrained grid space.

 

[bitttttor]

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

 

[Matterwave]

Sorry, I was going to respond, but then I got side-tracked.

I can't think of a clever way to do it, and only a brute force counting is apparent to me at this point.

 

[bitttttor]

Thank you Matterwave

only a brute force counting is apparent to me at this point

I started like that, using element size as rule. I reduced all possible locations of the element a) as 2 (border and middle):

XaXX aXXX
XaXX aXXX
XaXX aXXX
XaXX aXXX

These by 4 possible rotations, and by 2 possible mirror-like 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

 

[Matterwave]

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.

 

[xaos]

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.

 

[bitttttor]

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