Register to reply

Tetris-like combinatorial problem

by bitttttor
Tags: brainteaser, combinatorics, geometry
Share this thread:
bitttttor
#1
Apr11-12, 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 !!
Phys.Org News Partner Science news on Phys.org
Wearable 4MM jetpack tested on speed, agility for runners (w/ Video)
How did evolution optimize circadian clocks?
Corn spots: Study finds important genes in defense response
Matterwave
#2
Apr11-12, 03:55 AM
Sci Advisor
Matterwave's Avatar
P: 2,944
what are the rules for combining them? And what's with the dashes?
bitttttor
#3
Apr11-12, 08:32 AM
P: 11
Hi Matterwave,
Thank you for asking

Quote Quote by Matterwave View Post
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.

Quote Quote by Matterwave View Post
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
#4
Apr11-12, 04:14 PM
Sci Advisor
Matterwave's Avatar
P: 2,944
Tetris-like 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?
bitttttor
#5
Apr11-12, 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.
bitttttor
#6
Apr17-12, 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
Matterwave
#7
Apr17-12, 02:06 AM
Sci Advisor
Matterwave's Avatar
P: 2,944
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
#8
Apr17-12, 02:36 AM
P: 11
Thank you Matterwave

Quote Quote by Matterwave View Post
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
#9
Apr17-12, 01:54 PM
Sci Advisor
Matterwave's Avatar
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.
xaos
#10
Apr17-12, 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.
bitttttor
#11
Apr19-12, 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