Hamiltonian circuit for the entire 2x2x2 cube group

Discussion in 'Puzzle Theory' started by cuBerBruce, Dec 26, 2011.

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

    911
    1
    Oct 8, 2006
    Malden, MA, USA
    WCA:
    2006NORS01
    YouTube:
    cuBerBruce
    I have found a Hamiltonian circuit for the entire 2x2x2 cube group (3674160 elements).

    I note that my solution was developed independently from the solution for the <U,R> subgroup posted by cubemir.

    For compactness, I use variables to define sub-sequences of moves.
    The following conventions are used.
    Upper case letters are used for the basic quarter-turn moves of the 2x2x2 puzzle.
    · U represents turning the top face a quarter-turn clockwise.
    · V represents turning the top face a quarter-turn counterclockwise (conventionally denoted U').
    · R represents turning the right face a quarter-turn clockwise.
    · S represents turning the right face a quarter-turn counterclockwise (conventionally denoted R')
    · F represents turning the front face a quarter-turn clockwise (used in Appendix B).
    · G represents turning the front face a quarter-turn counterclockwise clockwise (conventionally denoted F').

    Variables denoted with lower case letters represent sequences of multiple moves.
    Many of them are defined in terms of other lower case variables.
    So recursive expansion is requred to get a plain sequence of individual moves.
    If a letter is followed by an apostrophe, then the inverse of the indicated sequence is to be used.
    This means that the order of the moves and direction of the moves must be reversed.
    A line with a letter and an equal sign starts the definition for a maneuver.
    The definition may extend over several lines until there is a line where another definition is started.
    The variable z is used to represent the entire Hamiltonian circuit.
    Code:
    b=URURUR
    a=bURUR
    i=bbUR
    c=VRiiVR
    n=VRa
    d=nn
    e=ncUR
    f=URcaVR
    g=ncabVR
    h=nbcaVR
    j=ccaVR
    k=bbVR
    l=ncc
    m=nUR
    o=VRUR
    r=adcURefknbhaodcURfccncabdodcURjabVRdccfcgdccfccVRicaURdnVRdljURURejaocdc
    cfcglccadVRddURciVRcjURcecmcURcadVRdgaboURnbeccad
    s=nbgaVRdblinVReckdbcanbVRmcURmcidoUR
    t=URURnUUaURdVRihkhcecncabdVRdcURfURURhaVRdlfabnbVRdeckcfVRigkURdURcfccaUR
    dVRdejhhejaoURdcURURefaVRegkglURcadVRddURciVRchejaoliVRVRigmcidVRnbeUReU
    RcadVRdcabVRhURefaVRdhcjURgmefURmciddUUaURdVRicknbefaodcURjabnodlinboURe
    URnbcadVRdgciVRcgncgcaURdVRddURURckURjURceURncabdVRccdcURfURURlURVRicaUR
    dnVRdmccVRijaVRhcVRijaVRnbefaodURURglfaVReckdcURfabVRmhidnUUaURdeefknbha
    odcURfccncabdodcURjabVRdccfcgdccfccVRicaURdnVRdljURURejaocdccfcglccadVRd
    dURciVRcjURcecmcURcadVRdgaboURnbeccadVRnbgaVRdblinVReckdbcanbVRmcURmcidd
    UUaURdVRihkhcecncabdVRdcURfURURhaVRdlfabnbVRdeckcfVRigkURdURcfccaURdVRde
    jhhejaoURdcURURefaVRegkglURcadVRddURciVRchejaoliVRVRigmcidVRnbeUReURcadV
    RdcabVRhURefaVRdhcjURgmefURmciddUUaURdVRicknbefaodcURjabnodlinboUReURnbc
    adVRdgciVRcgncgcaURdVRddURURckURjURceURncabdVRccdcURfURURlURVRicaURdnVRd
    mccVRijaVRhcVRijaVRnbefaodURURglfaVReckdcURfabVRmhidnUUaURdeefknbhaodcUR
    fccncabdodcURjabVRdccfcgdccfccVRicaURdnVRdljURURejaocdccfcglccadVRddURci
    VRcjURcecmcURcadVRdgaboURnbeccadVRnbgaVRdblinVReckdbcanbVRmcURmciddUUaUR
    dVRihkhcecncabdVRdcURfURURhaVRdlfabnbVRdeckcfVRigkURdURcfccaURdVRdejhhej
    aoURdcURURefaVRegkglURcadVRddURciVRchejaoliVRVRigmcidVRnbeUReURcadVRdcab
    VRhURefaVRdhcjURgmefURmciddUUaURdVRicknbefaodcURjabnodlinboUReURnbcadVRd
    gciVRcgncgcaURdVRddURURckURjURceURncabdVRccdcURfURURlURVRicaURdnVRdmc
    w=cVRijaVRhcVRijaVRnbefaodURURglfaVReckdcURfabVRmhidnU
    u=krVRsURtwF
    v=uuuuuuuuaVRrVRsURtwUUG
    p=FVw't'SVs'RRRUr'SUSVb'SFRbURVRrVSSSsURtwUG
    q=GVw't'SVs'SUr'SUa'SFVVw't'SVs'SUr'SUa'FRrVRsUSSStwUaG
    x=krVRsURtcVRijaVRhcVRijaVRnbefaodURURglfaVRnVRUpbURUpbURUpbockdcURfabVRVR
    kaboURUpbURUpbURUpURdURURdnUFkrVRsURtVRUpaabVRVRijaVRhcVRicnaUpbdVRnbefa
    odURURgnoURUpbURUpbURUpURVRcfaVReckVpaVRUpbURcURURcURUpbnbVRVRkabnbURUpb
    URdURURdnUFaVRrVRsURtVRUpaabVRVRijaVRhcVRijaVRnbeURoUpaidodURURglfaVRenb
    URUqbURVRknVRUpbURnabURVpURfabVRVRkURUpUpbUpUpcUpURUpUpURVRbUpbVRbURUpVR
    UpbURoUpbUUUG
    z=vvvvvvuuuuuux
    
     
    Last edited: Dec 26, 2011
  2. Nice! Although a mistake in the title.

    I thought I understood what you meant by all the variables, but then I saw 'UUU' on the second-last line. Why not V?
     
  3. cuBerBruce

    cuBerBruce Member

    911
    1
    Oct 8, 2006
    Malden, MA, USA
    WCA:
    2006NORS01
    YouTube:
    cuBerBruce
    UUU visits more positions than V.

    Edit: (Thread title has been fixed.)
     
    Last edited: Dec 26, 2011
  4. Cubemir

    Cubemir Member

    34
    0
    Jul 18, 2008
    Balashiha, RUSSIA
    WCA:
    2009ROST02
    YouTube:
    cubemir
    Great! This is Hamiltonian cycle or path?
     
  5. cuBerBruce

    cuBerBruce Member

    911
    1
    Oct 8, 2006
    Malden, MA, USA
    WCA:
    2006NORS01
    YouTube:
    cuBerBruce
    It's indeed a cycle, not merely a path. Omitting the last quarter turn will give a Hamiltonian path, of course.

    I note your subgroup cycle appears not to ever move the same layer twice in a row. Nice!
     
  6. Lucas Garron

    Lucas Garron Super-Duper Moderator Staff Member

    This is pretty cool. I'm starting to think we'll see a full algorithm for 3x3x3 soon enough.

    How much of this was brute force, and how much of it was clevering about with cosets?
     
  7. cuBerBruce

    cuBerBruce Member

    911
    1
    Oct 8, 2006
    Malden, MA, USA
    WCA:
    2006NORS01
    YouTube:
    cuBerBruce
    I guess I would say arriving at my solution had more to do with cleverness than with brute force searching. A major portion of the solution involved a rather simple and efficient search algorithm. It didn't really involve any massive computer power. Rather it involved coming up with the right tricks to reduce the problem into a few relatively simple computer searches.
     
  8. theZcuber

    theZcuber Premium Member

    2,076
    0
    May 8, 2011
    Central NY, US
    WCA:
    2012PRAT02
    No, it isn't. Devil's algorithm only passes through each position once. That even says it is over 1,000 times longer than there are positions. If it was Devil's algorithm, it would only be 43 quintillion, not 43 sextillion
     
  9. cuBerBruce

    cuBerBruce Member

    911
    1
    Oct 8, 2006
    Malden, MA, USA
    WCA:
    2006NORS01
    YouTube:
    cuBerBruce
    Different people have different definitions of exactly what "Devil's Algorithm" means. Some say it can reach some positions multiple times before all positions are reached and some do not. Some may allow repeating the sequence multiple times, so it can be shorter in length than the number of positions. So whether or not something is a "Devil's algorithm" generally depends on what definition you accept. That's why I avoided using the term.
     
  10. Carson

    Carson Premium Member

    So what you're saying is that when I'm solving a 2x2 and someone says something similar to "isn't there just a bunch of moves that will always solve it?" I can just hand them this?
     
  11. Gaétan Guimond

    Gaétan Guimond Member

    150
    3
    Mar 9, 2010
    Canada Quebec Montreal
    YouTube:
    rubiks99
    :tu

    http://games.groups.yahoo.com/group/speedsolvingrubikscube/message/42742
     
  12. stannic

    stannic Member

    118
    0
    Jun 16, 2010
    The country of riddles
    Well, a Hamiltonian path on Rubik's cube is a path that visits each cube state(configuration) exactly once. Bruce found such sequence for 2x2x2 cube. 2x2x2 has 3,674,160 distinct states; so this Hamiltonian path has 3,674,159 moves and visits exactly 3,674,160 configurations of the cube.
    (Actually, he found a Hamiltonian cycle that returns to the starting configuration after 3,674,160th move).
    When there is no condition "that visits each state exactly once", there is a simple way to make "a bunch of moves" that will always solve cube at some point. The number of moves in this bunch will be at most d*(N-1) where d is diameter of the cube and N is the number of states.
    For example, with 2x2x2 and half turn allowed, it is possible to write sequence of at most 11*3,674,159 = 40,415,749 moves. To do this, you can enumerate all cube configurations (solved cube is #1, some other cube configuration is #2, some other is #3, and so on up to #3,674,160). Then, starting from configuration #1, you can reach configuration #2 in at most 11 moves because it is the diameter. Then, starting from #2, you can reach #3 in at most 11 moves, etc.
    In other words, when you are solving a 3x3 or even 4x4 and someone asks whether there is a sequence of moves that will always solve it (without the condition "to visit each vertex exactly once"), the answer is yes.
    BTW, how this upper bound can be improved? Of course Bruce already found shortest possible path for 2x2x2 cube (3,674,159 moves).
    With 3x3x3, simple upper bound is d*(N-1) = 20 * (43,252,003,274,489,856,000 - 1) = 865,040,065,489,797,119,980 moves.
     
  13. siva.shanmukh

    siva.shanmukh Member

    85
    0
    Jan 19, 2008
    Chennai, India
    WCA:
    2008SHAN01
    YouTube:
    shanmukh1729
    It looks like it is going to be a pretty long move sequence or maneuver (as you call it). But I thought the diameter of 2x2 graph is about 8 (I am sure it is less than 20) right? So, the state that 'z' gives us could be simplified, to a sequence of length less than 8, right?
     
  14. Stefan

    Stefan Member

    7,287
    9
    May 7, 2006
    WCA:
    2003POCH01
    YouTube:
    StefanPochmann
    That wouldn't be a Hamiltonian-circuit (visiting every possible 2x2x2 state exactly once and also returning to the starting state).
     
    Last edited: Dec 30, 2011
  15. qqwref

    qqwref Member

    7,832
    17
    Dec 18, 2007
    a <script> tag near you
    WCA:
    2006GOTT01
    YouTube:
    qqwref2
    Good point.

    And even better, if we allow multiple turns of the same face in a row (and I don't see why we shouldn't for a Hamiltonian path): Consider the set of 3x3 cosets created from the subgroup <U,D>, which has 16 members. It's clear that each coset has a Devil's Algorithm ((UUUD)3UUU), so all we have to do is go through all elements of one coset (15 moves), go to the next (<=20 moves), and repeat. There are 2703250204665616000 of these cosets, so our path contains at most 15 + (20+15)*(2703250204665616000-1) = 94613757162946559980 moves, which is only about 2.1875 times the length of our theoretical Hamiltonian path. You could get a similar and better result by starting with other subgroups: <R,U>, <R2,L2,U2,D2,F2,B2>, etc.

    EDIT: Hmm, doesn't a Hamiltonian path (not necessarily cycle) exist for any Cartesian product of two groups that each have a Hamiltonian path? Could we take G=<R,L,U2,D2,F2,B2>, and H be the group of 3x3 equivalency classes (in the sense that equivalent positions differ by a permutation in G), and then find a Hamiltonian path on G, and also a Hamiltonian path on H (using only U,D,F,B moves)? Would that give us a Hamiltonian path for the whole cube?
     
    Last edited: Dec 30, 2011
  16. siva.shanmukh

    siva.shanmukh Member

    85
    0
    Jan 19, 2008
    Chennai, India
    WCA:
    2008SHAN01
    YouTube:
    shanmukh1729
    Totally my bad. Misinterpretted this to be devil's algorithm (or whatever the algorithm when repeated gives a new state every time it is executed till it covers all the states before reaching the initial state.)

    So, if I correctly understand, this when executed on a solved 2x2, should give us the solved 2x2 again, right?

    And does this sequence give a new state for each quarter turn, is it?

    I guess the above comment answers my last question. It doesn't visit a new state for each quarter turn for sure if the Hamiltonian path is longer than the size of 2x2 space
     
    Last edited by a moderator: Dec 30, 2011
  17. Stefan

    Stefan Member

    7,287
    9
    May 7, 2006
    WCA:
    2003POCH01
    YouTube:
    StefanPochmann
    It *is* one kind of devil's algorithm. See post #10.

    Yes.

    Yes, except for the last turn.

    It isn't longer. It can't be. Otherwise it wouldn't be Hamiltonian.
     
    Last edited: Dec 30, 2011
  18. qqwref

    qqwref Member

    7,832
    17
    Dec 18, 2007
    a <script> tag near you
    WCA:
    2006GOTT01
    YouTube:
    qqwref2
    The one that was given is just as long as the number of 2x2 states, so yeah, it does provide a new position every turn until all positions have been reached. But a longer one wouldn't necessarily do that; it would just give every position at some point during its execution.

    It's actually impossible to create an algorithm on the 2x2 or 3x3 that, when you repeat it, gives a new position every time it is executed until all positions have been reached. The reason is that no position has a high enough order (number of times it must be executed to return to the initial state) to cover all of the positions on the cube.
     

Share This Page