A Hamiltonian circuit for Rubik's Cube!

Discussion in 'Puzzle Theory' started by cuBerBruce, Feb 21, 2012.

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. cuBerBruce

    cuBerBruce Member

    910
    1
    Oct 8, 2006
    Malden, MA, USA
    WCA:
    2006NORS01
    YouTube:
    cuBerBruce
    I have found a Hamiltonian circuit for the quarter-turn metric Cayley graph of Rubik's Cube! In fact, it only uses turns of five of the six outer layers of the cube.

    In more basic terms, this is a sequence of quarter moves that would (in theory) put a Rubik's cube through all of its 43,252,003,274,489,856,000 positions without repeating any of them, and then one final move restores the cube to the starting position. Note that if we have any legally scrambled Rubik's Cube position as the starting point, then applying the sequence would result in the cube being solved at some point within the sequence.

    Additional information can be found at my web site: http://bruce.cubing.net/index.html
     
  2. cmhardw

    cmhardw Premium Member

    4,094
    21
    Apr 5, 2006
    Atlanta, Georgia
    WCA:
    2003HARD01
    Congratulations Bruce! This is a fascinating and amazing result! I downloaded the file, and I can't wait to check it out and attempt to understand it :)
     
    Last edited: Feb 21, 2012
  3. Wow! I thought this result would be way off in the future. Great job!
     
  4. theZcuber

    theZcuber Premium Member

    2,077
    0
    May 8, 2011
    Central NY, US
    WCA:
    2012PRAT02
    Now everytime somebody asks you how to solve it, just give them this.
     
  5. aronpm

    aronpm Member

    2,021
    0
    Sep 9, 2009
    Wow, this is awesome Bruce :)

    Yeah, that sounds plausible.
     
  6. Sahid Velji

    Sahid Velji Member

    499
    0
    Jul 5, 2009
    WCA:
    2008VELJ01
    YouTube:
    sv00013
    Bruce, were you the one to post a Hamiltonian circuit for the 2x2 as well?
    Regardless, great job! I tried reading the explanation but I found it difficult to understand, don't get me wrong, it's well written but it's just me.
    Edit: Never mind, I'm still in high school and have no idea what group theory is.
     
  7. Brest

    Brest Super Reconstructor Staff Member

    2,102
    27
    Sep 30, 2010
    WCA:
    2011STUA01
    YouTube:
    BrestCubing
    Awesome Bruce, impressive as always!
     
  8. Owen

    Owen Member

    1,138
    0
    Nov 2, 2009
    Yay! I hate B moves!
     
  9. Specs112

    Specs112 Member

    322
    1
    Dec 19, 2010
    Ithaca, NY
    WCA:
    2011ANDE03
    Bruce should be president.
     
  10. A Leman

    A Leman Member

    631
    1
    Jan 22, 2012
    New Jersey
    This is awesome! It must have taken you a long time and a pile of discrete math and number theory books to figure this out. Very impressive!!!
     
  11. qqwref

    qqwref Member

    7,831
    13
    Dec 18, 2007
    a <script> tag near you
    WCA:
    2006GOTT01
    YouTube:
    qqwref2
    Awesome job! This is a crazy result, and I look forward to seeing how you actually found it.

    PS: I, for one, would like to see how fast Feliks can execute it.
     
  12. cuBerBruce

    cuBerBruce Member

    910
    1
    Oct 8, 2006
    Malden, MA, USA
    WCA:
    2006NORS01
    YouTube:
    cuBerBruce
    Yes, I was also the one who posted the 2x2x2 Hamiltonian circuit (after someone else posted a Hamiltonian circuit of the 2x2x2 <U, R> subgroup). I thought I better post my 2x2x2 result at that time before someone else figured out a way to connect up the 126 cosets. I had actually developed that solution in July of 2010.

    It was back in late 2007 that I decided to make it a goal of mine to solve the Rubik's Cube Hamiltonian circuit problem. So this was no overnight solution. I solved the <U, R> subgroup Hamiltonian problem in 2008. I was not successful in arriving at a Hamiltonian circuit for the <U, R, F> subgroup. On Nov. 1, 2011, it finally dawned on me to consider the <U, R, D> subgroup rather than <U, R, F>. This turned out to be much easier for me to solve, and then <U, R, D, L> (only 132 cosets to deal with) was fairly easy to solve as well. This left only 2048 cosets for the final phase. While this had the same sort of difficulty as the <U, R, F> subgroup, the <U, R, F> subgroup problem had over 2.3 million cosets to deal with; over 1000 times more than 2048. By sometime in December I had determined how to finish the solution. It was just a matter of working out the details. On February 1, 2012, I had the problem essentially solved. I still had some work to take the details that had been worked out and put them into a form that describes the Hamiltonian circuit in the actual order that the sub-parts are executed.
     
  13. Cielo

    Cielo Member

    35
    0
    Mar 22, 2009
    Beijing, China
    WCA:
    2008LUYU01
    Congratulations!

    P.S: I noticed a typo in your explanation :"The problem of connnecting up the 2048 cosets".
     
  14. Lucas Garron

    Lucas Garron Super-Duper Moderator Staff Member

    Ooh, this is awesome. I've been looking forward to it ever since your previous results suggested it should be feasible. It looked too scary for me, so congratulations for getting a full solution! :p

    - You only use quarter turns, right? That gets rid of the ambiguities around RR vs. R2
    - The 7MB zip expands to 236MB (you might want to mention that on the site, too?). Any idea of the actual Kolmogorov complexity of your solution? Can it fit into a MB? Way less?
    - It might be kind of cute to write an algorithm that prints out a given (short) subsequence on demand. Sort of to make a point that this algorithm is constructive and we *can* write out any part we want.
    - Generalizing this: What puzzles have a Hamiltonian path? Is it obvious whether Pyraminx should have one? Megaminx? Square-1?
     
  15. cuBerBruce

    cuBerBruce Member

    910
    1
    Oct 8, 2006
    Malden, MA, USA
    WCA:
    2006NORS01
    YouTube:
    cuBerBruce
    Yes, the solution only uses quarter-turns (both clockwise and counterclockwise), but it may use the same quarter-turn more than once consecutively. Of course you can't use the same turn four times in succession, as that would result in repeating a state. As I said, it's a Hamiltonian circuit for the QTM Cayley graph.

    A half-turn on an actual cube would have the cube pass through another state midway, so limiting to quarter-turns assures that no state is passed through without being counted as a reached state.

    I was thinking good lossless compressors tend to compress fairly close to the amount of actual information. But perhaps this isn't so much the case with highly compressible information, so I don't really know. (By the way, Lucas, are there limits to how much space I can use?)

    I'll have to think about this. I also want to calculate the distribution of the 10 different moves that are used.

    As mentioned on Jaap's Puzzle Page, there is a mathematical conjecture (so it's not proven) that all Cayley graphs have a Hamiltonian circuit. Cubes larger than 3x3x3 generally have indistinguishable pieces (if not stickered as supercubes) so the positions don't form a group, so I believe the conjecture would not apply to those puzzles. Square-1 positions also do not form a group. For puzzles that are not a group, it may tend to be much harder (even if possible) to find a Hamiltonian circuit, since you then can't make use of group properties.

    And thanks for pointing out the typo, Cielo. I'll fix that.
     
    Last edited: Feb 21, 2012
  16. Cubenovice

    Cubenovice Forever Slow

    Congratulations!

    I guess this is a good time to rename God's algorithm:

    Bruce's Algorithm

    Now that this one is out of the way: what is there still to be discovered about the 3x3x3?
     
  17. Stefan

    Stefan Member

    7,289
    2
    May 7, 2006
    WCA:
    2003POCH01
    YouTube:
    StefanPochmann
    NanoZip 0.09 alpha with "cm" setting got it to 2,754,024 bytes, that's 38.8% of your zip's size. But shouldn't a full representation of your construction method/algorithm be even much smaller? (I'm not that familiar with Kolmogorov complexity, don't know what exactly is allowed and how it's counted)
     
  18. ASH

    ASH Member

    56
    0
    Nov 11, 2010
    Aachen, Germany
    WCA:
    2008HACK01
    Ok, I admit I suck at group theory (took the last course 4 years ago).
    So, what do I get wrong:

    - If there exists an element of the cube group which generates all elements (of the cube group) this means the group is cyclic, e.g. Cubegroup=<a>, a the proposed element
    - All cyclic groups are ablian, which means that for all elements a,b \in Cubegroup: a°b=b°a holds (° is the group's operation)
    - This means that 0=a°b-b°a=[a,b] (Commutator)

    Which concludes that all commutators do nothing, which is obviously false.

    So, tell me why I suck, pls! :)
     
  19. Stefan

    Stefan Member

    7,289
    2
    May 7, 2006
    WCA:
    2003POCH01
    YouTube:
    StefanPochmann
    The topic of this thread.

    This is about a loooong algorithm which *during* its execution visits all cube states. You're thinking of what happens when you repeat an algorithm and look at the cube only *after* each execution. The cube group isn't cyclic.
     
  20. ASH

    ASH Member

    56
    0
    Nov 11, 2010
    Aachen, Germany
    WCA:
    2008HACK01
    You're right Stefan.

    I was anyway doubting that I beat you in group theory! ;)

    At least I've been right about what I thought it was about. :p
     

Share This Page