# Hamiltonian circuit for the entire 2x2x2 cube group



## cuBerBruce (Dec 26, 2011)

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.


Spoiler





```
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
```


----------



## Julian (Dec 26, 2011)

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?


----------



## cuBerBruce (Dec 26, 2011)

Julian said:


> 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 n.ot V?


 
UUU visits more positions than V.

Edit: (Thread title has been fixed.)


----------



## Cubemir (Dec 26, 2011)

Great! This is Hamiltonian cycle or path?


----------



## cuBerBruce (Dec 26, 2011)

Cubemir said:


> Great! This is Hamiltonian cycle or path?


 
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!


----------



## Lucas Garron (Dec 27, 2011)

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?


----------



## cuBerBruce (Dec 27, 2011)

Lucas Garron said:


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



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.


----------



## samehsameh (Dec 27, 2011)

is this not the 3x3x3? http://www.sam.math.ethz.ch/~efonn/stuff/docs/devalg.txt


----------



## cubernya (Dec 27, 2011)

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


----------



## cuBerBruce (Dec 27, 2011)

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.


----------



## Carson (Dec 27, 2011)

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?


----------



## cubernya (Dec 27, 2011)

Yes


----------



## Gaétan Guimond (Dec 27, 2011)

cuBerBruce said:


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



:tu 

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


----------



## stannic (Dec 27, 2011)

Carson said:


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


 
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.


----------



## siva.shanmukh (Dec 30, 2011)

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?


----------



## Stefan (Dec 30, 2011)

siva.shanmukh said:


> So, the state that 'z' gives us could be simplified, to a sequence of length less than 8, right?



That wouldn't be a Hamiltonian-circuit (visiting every possible 2x2x2 state exactly once and also returning to the starting state).


----------



## qqwref (Dec 30, 2011)

stannic said:


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


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?


----------



## siva.shanmukh (Dec 30, 2011)

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


----------



## Stefan (Dec 30, 2011)

siva.shanmukh said:


> Misinterpretted this to be devil's algorithm



It *is* one kind of devil's algorithm. See post #10.



siva.shanmukh said:


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



Yes.



siva.shanmukh said:


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



Yes, except for the last turn.



siva.shanmukh said:


> 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*



It isn't longer. It can't be. Otherwise it wouldn't be Hamiltonian.


----------



## qqwref (Dec 30, 2011)

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.


----------



## Stefan (Dec 30, 2011)

qqwref said:


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


----------



## qqwref (Dec 30, 2011)

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


----------



## Stefan (Dec 30, 2011)

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


----------



## Lucas Garron (Dec 30, 2011)

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


----------



## qqwref (Dec 30, 2011)

g=ncabVR


----------



## Lucas Garron (Dec 30, 2011)

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



qqwref said:


> g=ncabVR


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


----------



## qqwref (Dec 30, 2011)

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





```
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
```


----------



## cuBerBruce (Dec 30, 2011)

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.


----------



## stannic (Dec 30, 2011)

qqwref said:


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



qqwref said:


> 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 (Dec 30, 2011)

stannic said:


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



stannic said:


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


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.


----------



## stannic (Jan 9, 2012)

Just found this page on Jaap's website:
Hamilton Cycles on puzzles


----------



## Lucas Garron (Jul 25, 2021)

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 (Jul 25, 2021)

I thought you were gonna write out the whole thing (which was my idea for a code golf challenge)


----------



## Lucas Garron (Jul 26, 2021)

qwr said:


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

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


----------



## qwr (Jul 26, 2021)

Lucas Garron said:


> Bruce has the whole alg on his site, so that's unfortunately not too exciting.
> 
> 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. )



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 (Jul 26, 2021)

qwr said:


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


----------



## GodCubing (Jul 26, 2021)

How do you make stuff like this?


----------



## qwr (Jul 26, 2021)

Christopher Mowla said:


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


----------

