# Thread: Hamiltonian circuit for the entire 2x2x2 cube group

1. Originally Posted by qqwref
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?

2. If you only check the position after each run of the algorithm, it doesn't matter how long it is.

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

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

5. g=ncabVR

6. 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).

Originally Posted by qqwref
g=ncabVR
Mm-hmm. Hence my confusion, because I only saw that, but not the definition of G.

7. 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:
Spoiler:

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

s=nbgaQdblinQeckdbcanbQmcPmcidoP
t=PPnUUaPdQihkhcecncabdQdcPfPPhaQdlfabnbQdeckcfQigkPdPcfccaPdQdejhhejaoPdcPPefaQe
ijaQhcQijaQnbefaodPPglfaQeckdcPfabQmhidnUUaPdeefknbhaodcPfccncabdodcPjabQdccfcgdc
dbcanbQmcPmciddUUaPdQihkhcecncabdQdcPfPPhaQdlfabnbQdeckcfQigkPdPcfccaPdQdejhhejao
aPdnQdmccQijaQhcQijaQnbefaodPPglfaQeckdcPfabQmhidnUUaPdeefknbhaodcPfccncabdodcPja
QdblinQeckdbcanbQmcPmciddUUaPdQihkhcecncabdQdcPfPPhaQdlfabnbQdeckcfQigkPdPcfccaPd
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```

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

9. Originally Posted by qqwref
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.

Originally Posted by qqwref
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?

10. Originally Posted by stannic
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.

Originally Posted by stannic
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.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•