• Welcome to the Speedsolving.com, home of the web's largest puzzle community!
    You are currently viewing our forum as a guest which gives you limited access to join discussions and access our other features.

    Registration is fast, simple and absolutely free so please, join our community of 40,000+ people from around the world today!

    If you are already a member, simply login to hide this message and begin participating in the community!

Hamiltonian circuit for the entire 2x2x2 cube group

Stefan

Member
Joined
May 7, 2006
Messages
7,280
WCA
2003POCH01
YouTube
Visit Channel
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.

But if the algorithm is very long?
 

Stefan

Member
Joined
May 7, 2006
Messages
7,280
WCA
2003POCH01
YouTube
Visit Channel
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:

qqwref

Member
Joined
Dec 18, 2007
Messages
7,834
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
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:

cuBerBruce

Member
Joined
Oct 8, 2006
Messages
914
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
Visit Channel
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:

stannic

Member
Joined
Jun 16, 2010
Messages
120
Location
The country of riddles
Hmm, doesn't a Hamiltonian path (not necessarily cycle) exist for any Cartesian product of two groups that each have a Hamiltonian path?
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.

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?

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?
 

qqwref

Member
Joined
Dec 18, 2007
Messages
7,834
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
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.
Yeah, that's what I was thinking too.

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

Lucas Garron

Administrator
Joined
Jul 6, 2007
Messages
3,718
Location
California
WCA
2006GARR01
YouTube
Visit Channel
I know it's been a while on this thread, but last night I used `cubing.js` to load the whole 2x2x2 Devil's alg. :-D

You can try it out at https://experiments.cubing.net/cubing.js/stress-tests/2x2x2-devils-alg.html
The whole thing would take over 1000 hours to animate, but you can skip to any part almost instantly (after it loads). Every 2x2x2 state on a single animation timeline. :-D

Some devices may run into issues, so here's a quick recording of how it looks.
 

qwr

Member
Joined
Jul 24, 2019
Messages
3,371
YouTube
Visit Channel
I thought you were gonna write out the whole thing (which was my idea for a code golf challenge)
 

Lucas Garron

Administrator
Joined
Jul 6, 2007
Messages
3,718
Location
California
WCA
2006GARR01
YouTube
Visit Channel
I thought you were gonna write out the whole thing (which was my idea for a code golf challenge)
Bruce has the whole alg on his site, so that's unfortunately not too exciting. :p

It does sound like a pretty good code challenge, though!

(One good challenge for me would be to try to display where in each alg the animation is, but perhaps some day when I have too much spare time on my hands. :p)
 

qwr

Member
Joined
Jul 24, 2019
Messages
3,371
YouTube
Visit Channel
Bruce has the whole alg on his site, so that's unfortunately not too exciting. :p

It does sound like a pretty good code challenge, though!

(One good challenge for me would be to try to display where in each alg the animation is, but perhaps some day when I have too much spare time on my hands. :p)

the point of code golf (kolmogorov complexity category) is to be able to produce the string with fewer characters than the entire string. so it boils down to how cleverly can you compress the string and write a decoder
 

Christopher Mowla

Premium Member
Joined
Sep 17, 2009
Messages
1,184
Location
Earth
YouTube
Visit Channel
the point of code golf (kolmogorov complexity category) is to be able to produce the string with fewer characters than the entire string. so it boils down to how cleverly can you compress the string and write a decoder
If you're not writing out the entire string, then didn't Bruce come up with the best result for this already? The 3.6 million move string is can be expressed in compressed (compact) form on a single page (maybe two pages) of paper.
 

qwr

Member
Joined
Jul 24, 2019
Messages
3,371
YouTube
Visit Channel
If you're not writing out the entire string, then didn't Bruce come up with the best result for this already? The 3.6 million move string is can be expressed in compressed (compact) form on a single page (maybe two pages) of paper.
you need to write a computer program or function to do the decompression. because there's inverse moves, it's not a completely trivial search and replace. also it's possible that there exist shorter programs that hardcode more.
 
Thread starter Similar threads Forum Replies Date
O Puzzle Theory 17
C Puzzle Theory 60
Top