# Hamiltonian circuit for the entire 2x2x2 cube group

Discussion in 'Puzzle Theory' started by cuBerBruce, Dec 26, 2011.

1. ### cuBerBruceMember

914
11
Oct 8, 2006
Malden, MA, USA
WCA:
2006NORS01
cuBerBruce
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: Dec 26, 2011
2. ### JulianMember

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?

3. ### cuBerBruceMember

914
11
Oct 8, 2006
Malden, MA, USA
WCA:
2006NORS01
cuBerBruce
UUU visits more positions than V.

Edit: (Thread title has been fixed.)

Last edited: Dec 26, 2011
4. ### CubemirMember

34
0
Jul 18, 2008
Balashiha, RUSSIA
WCA:
2009ROST02
cubemir
Great! This is Hamiltonian cycle or path?

5. ### cuBerBruceMember

914
11
Oct 8, 2006
Malden, MA, USA
WCA:
2006NORS01
cuBerBruce
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!

6. ### Lucas GarronSuper-Duper ModeratorStaff 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?

7. ### cuBerBruceMember

914
11
Oct 8, 2006
Malden, MA, USA
WCA:
2006NORS01
cuBerBruce
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.

8. ### samehsamehMember

27
0
Apr 29, 2011
England

May 8, 2011
Central NY, US
WCA:
2012PRAT02
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

10. ### cuBerBruceMember

914
11
Oct 8, 2006
Malden, MA, USA
WCA:
2006NORS01
cuBerBruce
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.

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?

May 8, 2011
Central NY, US
WCA:
2012PRAT02
Yes

13. ### Gaétan GuimondMember

150
3
Mar 9, 2010
rubiks99
:tu

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

14. ### stannicMember

120
1
Jun 16, 2010
The country of riddles
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.

15. ### siva.shanmukhMember

85
0
Jan 19, 2008
Chennai, India
WCA:
2008SHAN01
shanmukh1729
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?

16. ### StefanMember

7,287
21
May 7, 2006
WCA:
2003POCH01
StefanPochmann
That wouldn't be a Hamiltonian-circuit (visiting every possible 2x2x2 state exactly once and also returning to the starting state).

Last edited: Dec 30, 2011
17. ### qqwrefMember

7,830
35
Dec 18, 2007
a <script> tag near you
WCA:
2006GOTT01
qqwref2
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: Dec 30, 2011
18. ### siva.shanmukhMember

85
0
Jan 19, 2008
Chennai, India
WCA:
2008SHAN01
shanmukh1729
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: Dec 30, 2011
19. ### StefanMember

7,287
21
May 7, 2006
WCA:
2003POCH01
StefanPochmann
It *is* one kind of devil's algorithm. See post #10.

Yes.

Yes, except for the last turn.

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

Last edited: Dec 30, 2011
20. ### qqwrefMember

7,830
35
Dec 18, 2007
a <script> tag near you
WCA:
2006GOTT01