[Theory] 2D State Diagrams

Discussion in 'Puzzle Theory' started by qqwref, Jan 12, 2009.

Welcome to the Speedsolving.com. You are currently viewing our boards as a guest which gives you limited access to join discussions and access our other features. By joining our free community of over 30,000 people, you will have access to post topics, communicate privately with other members (PM), respond to polls, upload content and access many other special features. Registration is fast, simple and absolutely free so please, join our community today!

If you have any problems with the registration process or your account login, please contact us and we'll help you get started. We look forward to seeing you on the forums!

Already a member? Login to stop seeing this message.
  1. qqwref

    qqwref Member

    7,833
    23
    Dec 18, 2007
    a <script> tag near you
    WCA:
    2006GOTT01
    YouTube:
    qqwref2
    This is a topic on puzzle theory - specifically, it deals with the theory of symmetrical twisty puzzles. There's no real "theory" section in this forum but it doesn't belong in Off-Topic, so I've put it here so more people will see it. (This does have applications to speedcubing, in terms of solving gelatinbrain puzzles.)

    So, as some of you may know, symmetrical twisty puzzles can be described by talking about the shape and the number of separate types of turns in each of the three basic categories (face turns, edge turns, and vertex turns) which are named around where the axis (which the pieces rotate around) points. A 3x3x3, for instance, is a cube with one type of turn (in the face turn category); in my categorization scheme that would make it type Cf (C for cube, f for face turn). The only other type-Cf puzzle is the 2x2x2, which has a deeper turn that just happens to line up with the turn on the opposite face. (The 4x4x4 and 5x5x5 have two face turn types, so they are type Cff. Similarly the 6x6x6 and 7x7x7 are type Cfff.) Note that I'm considering a 3x3 with slightly shallower or deeper cuts to be the same, because it has the same number and types of pieces and the exact same solution, so the only difference is in the shape of the pieces.

    If we want to talk about symmetrical puzzles with only one type of turn, it's relatively simple, because we can describe the depth of the turn as a single number. But if we have two types of turns, we need two numbers: for instance, on a 5x5x5, if we imagine a turn of depth 0 to turn nothing and a turn of depth 1 to turn the entire cube, the two turns have depths 1/5 and 2/5. But it's hard to imagine exactly what numbers will give a certain puzzle, and which numbers will give a different one. So the question is this: how many possible puzzles are there of a given type, and, more importantly, how can we understand where one puzzle begins and another ends?

    [​IMG]
    My answer to this is the 2D State Diagram. This particular one describes the Tvv-type polyhedra (that is, tetrahedra with two vertex turn types - note that a vertex turn and a face turn are the same thing on a tetrahedron). The two axes correspond to the two depths of turn, and each one goes from 0 (no part of the puzzle is turned) to 1 (the entire puzzle is turned).

    So what are the lines in the diagram? Each one represents some kind of puzzle which only exists for a very specific set of turn depths. The diagonal line from the top-left to bottom-right represents the degenerate case where the two depths are the same (so, type Tv puzzles with only one type of cut). Each of those big spaces between the lines, however, is a specific puzzle, which remains the same anywhere in that space. There are also puzzles on the lines themselves, and each place where lines intersect is another puzzle, albeit a very specific one because even a small change in either of the two depths will make it different. The Pyraminx, for example, is located at the intersection of a horizontal or vertical 2/3 line, and the diagonal line from bottom left to top right.

    Finally, I have prepared an interactive simulation (!) of this state diagram, so that you can play with it to see how it works out. It uses the GeoGebra geometry program, which I'm really fond of. You can download it from my website. To use it, just move the red point around inside the square (use the white pointer symbol to move a point around), and watch how the puzzle changes when you cross or move along lines.

    I hope this is interesting to you, and feel free to ask any questions :)
     
    Last edited: Jan 12, 2009
  2. this sounds pretty cool, could you ,make a diagram that works for simple cuboid shaps, and explain it furthe beacous im interested but i dont fully comprehend.
     
  3. qqwref

    qqwref Member

    7,833
    23
    Dec 18, 2007
    a <script> tag near you
    WCA:
    2006GOTT01
    YouTube:
    qqwref2
    I wrote up the state diagram for type Dff puzzles (dodecahedra with two different depths of face turns). The Gigaminx is from this category. Note that this category is MUCH more complicated than the Tvv type I showed in the first post - I'm not completely sure of the count, but I think there are a whopping 98 puzzles of this type!!! I'm really glad I made an interactive simulation, because there is no way I'd ever want to draw all of them out by hand. You can also see that there are 7 puzzles along the diagonal (these are the Df type puzzles).

    [​IMG]
    In the image, I have marked a few lines as green. Those lines are distinctive because, although they separate different puzzles, the puzzles on the lines themselves are equivalent to one of the puzzles on one side of the line. For instance the Megaminx and Supernova, although they look like they might different puzzles, function exactly the same way.The full way to count the number of puzzles is:
    - Any open space is a separate puzzle, although you have to make sure to only count puzzles on one side of the main diagonal (for everything here).
    - Any line segment (i.e. a line between two intersections) is a separate puzzle, except (i) if the line segment is green; (ii) if the line segment is on the main diagonal; (iii) if the line segment is on the top or left. The second and third cases remove puzzles with essentially only one depth of turn, and the first removes a puzzle that looks like a different puzzle but isn't.
    - Any intersection of lines is a separate puzzle, as long as (i) it isn't on the the top or left or the main diagonal, and (ii) it has at least two black lines crossing it.
    The Tvv case gives 11+10+2 = 23 puzzles like this (I think). Note that, although I haven't added it in yet, the halfway lines and the bottom-left-to-top-right diagonal in the Tvv diagram should also be green. It's only important to know what lines are green and what are not when you are counting puzzles, though.

    Finally, there is a GeoGebra simulation of this, although I have made the two-dimensional slider much larger to compensate for the complexity. That way you can really see what lines you are crossing.


    Cuboids are actually extremely boring when it comes to comparing puzzles, because there are surprisingly few of them. Of course the only symmetrical ones are the cubes, and there are just 2 cube puzzles for each order (2x2 and 3x3 for Cf, 4x4 and 5x5 for Cff, and so on), so the diagram would just a square with one diagonal line drawn in it. 90-degree angles just don't intersect in interesting ways.

    As far as explaining further, if you are confused, I suggest you play around with gelatinbrain puzzles or UltimateMagicCube, to see how changing the depth of layers can get rid of some pieces or create others. If you want to understand it better I really suggest you play with the interactive simulations I made - just imagine that every face of the shape looks the same, and drag the slider slowly to see how the pieces slowly change shape and disappear.
     
  4. twistar

    twistar Member

    3
    0
    Jan 5, 2009
    When I click the links to download the simulation it downloads a zip file containing a .xml file and that GeoGebra program can't open either of those.
     
  5. qqwref

    qqwref Member

    7,833
    23
    Dec 18, 2007
    a <script> tag near you
    WCA:
    2006GOTT01
    YouTube:
    qqwref2
    It should be a .ggb file, not .zip. So after you save it, rename it to .ggb. (It's .ggb on my server, I have no idea why it gets renamed when it is downloaded...)
     
  6. ohhh, cool. haha sorry alll it took was a couple re-reads amd a bit of looking and then reading your responce, this is cool. i like graphing and such this gives me a couple new ideas

    thanks
     
  7. qqwref

    qqwref Member

    7,833
    23
    Dec 18, 2007
    a <script> tag near you
    WCA:
    2006GOTT01
    YouTube:
    qqwref2
    I've been categorizing the second-order puzzles only, because the first-order puzzles can be categorized very easily and because higher orders would require a three-dimensional slider to get any kind of real visualization of where the puzzles begin and end.

    But for each polyhedron there are actually six types of second-order puzzles: the familiar vv, ee, and ff, but also fv, ev, and ef. The first three use only one type of cut, so they're symmetrical, but the other three use two different types of cuts and have much more complicated drawings. As an example I've made one for the Cfv group. There are around 50 puzzles in this group, most of which have probably never been seen before. I hope to eventually make an interactive simulation of all 5*6 categories of second-order regular twisty puzzles. I imagine there will be over 1000 puzzles in total!
     

Share This Page