# Hamiltonian circuit for the entire 2x2x2 cube group

#### cuBerBruce

##### Member
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
s=nbgaVRdblinVReckdbcanbVRmcURmcidoUR
t=URURnUUaURdVRihkhcecncabdVRdcURfURURhaVRdlfabnbVRdeckcfVRigkURdURcfccaUR
dnVRdmccVRijaVRhcVRijaVRnbefaodURURglfaVReckdcURfabVRmhidnUUaURdeefknbha
UUaURdVRihkhcecncabdVRdcURfURURhaVRdlfabnbVRdeckcfVRigkURdURcfccaURdVRde
RdcabVRhURefaVRdhcjURgmefURmciddUUaURdVRicknbefaodcURjabnodlinboUReURnbc
mccVRijaVRhcVRijaVRnbefaodURURglfaVReckdcURfabVRmhidnUUaURdeefknbhaodcUR
dVRihkhcecncabdVRdcURfURURhaVRdlfabnbVRdeckcfVRigkURdURcfccaURdVRdejhhej
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:

#### Julian

##### Member
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

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

Last edited:

#### Cubemir

##### Member
Great! This is Hamiltonian cycle or path?

#### cuBerBruce

##### Member
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

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

#### cuBerBruce

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

#### cubernya

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

##### Member
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

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?

Yes

#### Gaétan Guimond

##### Member
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

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

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

##### Member
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

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

Last edited:

#### qqwref

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

Last edited:

#### siva.shanmukh

##### Member
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:

#### Stefan

##### Member
Misinterpretted this to be devil's algorithm

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

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

Yes.

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

Yes, except for the last turn.

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.

Last edited:

#### qqwref

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