Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Tetris-like combinatorial problem

  1. Apr 11, 2012 #1
    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 !!
     
    Last edited: Apr 11, 2012
  2. jcsd
  3. Apr 11, 2012 #2

    Matterwave

    User Avatar
    Science Advisor
    Gold Member

    what are the rules for combining them? And what's with the dashes?
     
  4. Apr 11, 2012 #3
    Hi Matterwave,
    Thank you for asking

    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.

    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?
     
  5. Apr 11, 2012 #4

    Matterwave

    User Avatar
    Science Advisor
    Gold Member

    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?
     
  6. Apr 11, 2012 #5
    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.
     
  7. Apr 17, 2012 #6
    Nobody...? any similar problem? or an idea on what method to use for tackling it? a book? Anything would help
     
  8. Apr 17, 2012 #7

    Matterwave

    User Avatar
    Science Advisor
    Gold Member

    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.
     
  9. Apr 17, 2012 #8
    Thank you Matterwave

    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
     
    Last edited: Apr 17, 2012
  10. Apr 17, 2012 #9

    Matterwave

    User Avatar
    Science Advisor
    Gold Member

    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.
     
  11. Apr 17, 2012 #10
    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.
     
    Last edited: Apr 17, 2012
  12. Apr 19, 2012 #11
    Thanks, I'll try this way and post any advances,
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Tetris-like combinatorial problem
  1. Combinatorial problem (Replies: 6)

Loading...