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

    Stefan Member

    7,287
    12
    May 7, 2006
    WCA:
    2003POCH01
    YouTube:
    StefanPochmann
    But if the algorithm is very long?
     
  2. qqwref

    qqwref Member

    7,833
    23
    Dec 18, 2007
    a <script> tag near you
    WCA:
    2006GOTT01
    YouTube:
    qqwref2
    If you only check the position after each run of the algorithm, it doesn't matter how long it is.
     
  3. Stefan

    Stefan Member

    7,287
    12
    May 7, 2006
    WCA:
    2003POCH01
    YouTube:
    StefanPochmann
    Ah yes, I misunderstood, sorry. Probably didn't realize what you meant (and what I now see he had said) because I already knew it's impossible :)
     
    Last edited: Dec 30, 2011
  4. Lucas Garron

    Lucas Garron Super-Duper Moderator Staff Member

    A couple of letters in the algorithm are "G", but only "g" is defined. Are these intended to be the same?
     
  5. qqwref

    qqwref Member

    7,833
    23
    Dec 18, 2007
    a <script> tag near you
    WCA:
    2006GOTT01
    YouTube:
    qqwref2
  6. Lucas Garron

    Lucas Garron Super-Duper Moderator Staff Member

    Oh, I'm silly. I was looking at the algs so hard that I forgot the {U, V, R, S, F, G} definitions at the top (which I only read the first time I saw this thread).

    Mm-hmm. Hence my confusion, because I only saw that, but not the definition of G.
     
  7. qqwref

    qqwref Member

    7,833
    23
    Dec 18, 2007
    a <script> tag near you
    WCA:
    2006GOTT01
    YouTube:
    qqwref2
    Oh, sorry. I misread that pretty hard, and assumed that G must have been the one you'd seen, since it was right there at the top. Never mind. (It WAS kinda weird to use S, V, and G - considering that other sequences are inverted throughout the definitions...)

    Any feedback on my bounds and/or idea for generating a full 3x3 Hamiltonian path? Is the idea wrong, or right, or potentially useful?


    PS, a little rewriting to (hopefully) make things slightly easier to understand:
    Code:
    P=UR
    Q=U'R
    
    a=P^5
    b=P^3
    c=Q P^14 Q
    d=Q P^5 Q P^5
    e=Q P^5 c P
    f=P c P^5 Q
    g=Q P^5 c P^8 Q
    h=Q P^8 c P^5 Q
    i=P^7
    j=cc P^5 Q
    k=P^6 Q
    l=Q P^5 cc
    m=Q P^6
    n=Q P^5
    o=Q P
    
    r=adcPefknbhaodcPfccncabdodcPjabQdccfcgdccfccQicaPdnQdljPPejaocdccfcglccadQddPciQ
    cjPcecmcPcadQdgaboPnbeccad
    s=nbgaQdblinQeckdbcanbQmcPmcidoP
    t=PPnUUaPdQihkhcecncabdQdcPfPPhaQdlfabnbQdeckcfQigkPdPcfccaPdQdejhhejaoPdcPPefaQe
    gkglPcadQddPciQchejaoliQQigmcidQnbePePcadQdcabQhPefaQdhcjPgmefPmciddUUaPdQicknbef
    aodcPjabnodlinboPePnbcadQdgciQcgncgcaPdQddPPckPjPcePncabdQccdcPfPPlPQicaPdnQdmccQ
    ijaQhcQijaQnbefaodPPglfaQeckdcPfabQmhidnUUaPdeefknbhaodcPfccncabdodcPjabQdccfcgdc
    cfccQicaPdnQdljPPejaocdccfcglccadQddPciQcjPcecmcPcadQdgaboPnbeccadQnbgaQdblinQeck
    dbcanbQmcPmciddUUaPdQihkhcecncabdQdcPfPPhaQdlfabnbQdeckcfQigkPdPcfccaPdQdejhhejao
    PdcPPefaQegkglPcadQddPciQchejaoliQQigmcidQnbePePcadQdcabQhPefaQdhcjPgmefPmciddUUa
    PdQicknbefaodcPjabnodlinboPePnbcadQdgciQcgncgcaPdQddPPckPjPcePncabdQccdcPfPPlPQic
    aPdnQdmccQijaQhcQijaQnbefaodPPglfaQeckdcPfabQmhidnUUaPdeefknbhaodcPfccncabdodcPja
    bQdccfcgdccfccQicaPdnQdljPPejaocdccfcglccadQddPciQcjPcecmcPcadQdgaboPnbeccadQnbga
    QdblinQeckdbcanbQmcPmciddUUaPdQihkhcecncabdQdcPfPPhaQdlfabnbQdeckcfQigkPdPcfccaPd
    QdejhhejaoPdcPPefaQegkglPcadQddPciQchejaoliQQigmcidQnbePePcadQdcabQhPefaQdhcjPgme
    fPmciddUUaPdQicknbefaodcPjabnodlinboPePnbcadQdgciQcgncgcaPdQddPPckPjPcePncabdQccd
    cPfPPlPQicaPdnQdmc
    w=cQijaQhcQijaQnbefaodPPglfaQeckdcPfabQmhidnU
    
    u=krQsPtwF
    v=u^8 aQrQsPtwUUF'
    p=FU'w't'R'U's'RRRUR'R'UR'U'b'R'FRbPQrU'R'R'R'sPtwUF'
    q=F'U'w't'R'U's'R'UR'R'Ua'R'FU'U'w't'R'U's'R'UR'R'Ua'FRrQsUR'R'R'twUaF'
    x=krQsPtcQijaQhcQijaQnbefaodPPglfaQnQUpbPUpbPUpbockdcPfabQQkaboPUpbPUpbPUpPdPPdnU
    FkrQsPtQUpaabQQijaQhcQicnaUpbdQnbefaodPPgnoPUpbPUpbPUpPQcfaQeckU'paQUpbPcPPcPUpbn
    bQQkabnbPUpbPdPPdnUFaQrQsPtQUpaabQQijaQhcQijaQnbePoUpaidodPPglfaQenbPUqbPQknQUpbP
    nabPU'pPfabQQkPUpUpbUpUpcUpPUpUpPQbUpbQbPUpQUpbPoUpbUUUF'
    
    z=v^6 u^6 x
     
    Last edited: Dec 30, 2011
  8. cuBerBruce

    cuBerBruce Member

    912
    4
    Oct 8, 2006
    Malden, MA, USA
    WCA:
    2006NORS01
    YouTube:
    cuBerBruce
    I thought (as far as my description is concerned) I would reserve capital letters for single moves and lower case letters for sequences. To try to make parsing it by a computer program as simple as I could, I avoided using exponentiation or other form of repetition counts. However, using an inverse operator avoided having to define a lot more variables/sequences, and I had used almost all the lower case letters already.
     
    Last edited: Dec 30, 2011
  9. stannic

    stannic Member

    120
    0
    Jun 16, 2010
    The country of riddles
    If each of two undirected graphs G1 and G2 have a Hamiltonian path then their Cartesian product also has a Hamiltonian path. We can draw |G2| copies of G1 and add edges between copies to get Cartesian product. On all copies of G1, we will mark the same Hamiltonian path. Then we can connect all these paths into one Hamiltonian path.

    Is it true that the cube group is the Cartesian product of G and H?

    Let A=<U,D,R,L,F,B>, B=<U,D,R2,L2,F2,B2>. Let C be the group that arises when we merge positions in A that differ by permutation in B.
    Then |A| = 4.32*10^19, |B| = 1.95*10^10, |C|=2.217*10^9.
    Suppose there is a Hamiltonian path on graph {B, <U,D,R2,L2,F2,B2>}, and there is a Hamiltonian path on {C, <R,L,F,B>}. Can we conclude that there is a Hamiltonian path on {A, <U,D,R,L,F,B>}?
    Is this interpretation correct?
     
  10. qqwref

    qqwref Member

    7,833
    23
    Dec 18, 2007
    a <script> tag near you
    WCA:
    2006GOTT01
    YouTube:
    qqwref2
    Yeah, that's what I was thinking too.

    That's what I was going for. I'm not completely sure it's mathematically valid since it's been a while since I did any serious group theory, but if it does work, the relative sizes of these subgroups should make it a lot easier to find a Hamiltonian path.
     
  11. stannic

    stannic Member

    120
    0
    Jun 16, 2010
    The country of riddles

Share This Page