• 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 35,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!

A Hamiltonian circuit for Rubik's Cube!

Joined
Oct 8, 2006
Messages
914
Likes
15
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
cuBerBruce
Thread starter #41
Although the q_shortcut file contains "q=", it does not really define the true sequence for q. Each "u" (lower case) in the shortcut file would really need to be replaced by a sequence. To determine that sequence (for each u), you would have to execute the corresponding moves from the q.txt until you reach the same state that you would reach if you just applied the move U at that point instead. (You should then find that the next moves in both files will be the same until the next "u" in q_shortcut.txt; and so on.) These "u" sequences generally are not the same length. The indices in RubiksCubeHamilton.txt are such that each "u" (or other symbol such as "x") is counted as a single "move" (that is, takes up exactly one index position).

I've created a file that provides a mapping between positions in the shortcut sequence to positions in the longer sequence (for each position following a "u" in the shortcut file). I can email this to people who want it.

Q is the inverse sequence of q. I didn't provide files for Q because it should be straightforward to generate these from the q.txt and q_shortcut.txt files (just reverse the order, using the inverse symbol of each symbol in the sequence).
 
Joined
May 7, 2006
Messages
7,287
Likes
40
WCA
2003POCH01
YouTube
StefanPochmann
#42
To determine that sequence (for each u), you would have to execute the corresponding moves from the q.txt until you reach the same state that you would reach if you just applied the move U at that point instead.
Ah yes, I could have seen that. Forgot that you don't visit a state twice...

Q is the inverse sequence of q.
Ok, I've seen it in readme.txt now. I had only checked the definitions in the definition files. Why did you define T/Q/X in readme.txt instead of in misc.txt like the other inverses?
 
Joined
May 6, 2012
Messages
367
Likes
12
Location
Pullman, WA
WCA
2013BRAN01
#44
Of course the vast majority of initial conditions will be solved long before the algorithm indicates: Since the algorithm has thousands of moves, it has to, on average cover all the states thousands of times.

I.e. I'm assuming that the Hamiltonian circuit works in that if we call the algorithm A, then A raised to the J power is not equal to A for any J less than the number of cube positions. But the number of (not different) positions you've actually traversed in doing this is MxA^N where M is the number of 1/4 turns in the algorithm.
 
Joined
Oct 8, 2006
Messages
914
Likes
15
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
cuBerBruce
Thread starter #45
Of course the vast majority of initial conditions will be solved long before the algorithm indicates: Since the algorithm has thousands of moves, it has to, on average cover all the states thousands of times.

I.e. I'm assuming that the Hamiltonian circuit works in that if we call the algorithm A, then A raised to the J power is not equal to A for any J less than the number of cube positions. But the number of (not different) positions you've actually traversed in doing this is MxA^N where M is the number of 1/4 turns in the algorithm.
You seem to be confused about something. The Hamiltonian circuit contains exactly 43,252,003,274,489,856,000 quarter turns. Performing it once will sequence the cube through each of the possible states exactly once until ending up at the initial position again when finished. Repeating it will result in going through the same sequence of 43,252,003,274,489,856,000 positions a 2nd time in the same order.

You seem to be of the impression that the Hamiltonian circuit I've described is some shorter algorithm simply repeated a certain number of times. That's simply not the case at all.
 
Joined
May 6, 2012
Messages
367
Likes
12
Location
Pullman, WA
WCA
2013BRAN01
#46
Thanks for explaining that to me. Now I'm more impressed! It's like a knight's tour of the chessboard (but far longer).

Now I'm wondering if what I was thinking of can exist. That is, is there an algorithm A which raised to the 43 zillionth power is unity and for no smaller power. That could be a lot easier to memorize than the Devil's algorithm (but would take much longer to cycle the cube).
 
Joined
Oct 8, 2006
Messages
914
Likes
15
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
cuBerBruce
Thread starter #47
Thanks for explaining that to me. Now I'm more impressed! It's like a knight's tour of the chessboard (but far longer).

Now I'm wondering if what I was thinking of can exist. That is, is there an algorithm A which raised to the 43 zillionth power is unity and for no smaller power. That could be a lot easier to memorize than the Devil's algorithm (but would take much longer to cycle the cube).
Yeah, the knight's tour problem is one of the more famous Hamiltonian circuit problems.

Didn't you read the Calculating "The Devil's Algorithm" thread?

It's been discussed there and many other places that you will always get back to the initial state after no more than 2520 repetitions of any algorithm (1260 repetitions if the algorithm is restricted to face turns only).

I also note that my Hamiltonian circuit certainly does make use of repetition, but it's a quite a bit more complicated than simply repeating a certain fixed sequence over and over. It also makes use of "interrupts" which I regard as one of the key techniques used to make solving the problem relatively "easy."
 
Joined
Apr 29, 2006
Messages
1,802
Likes
3
#48
Now I'm wondering if what I was thinking of can exist. That is, is there an algorithm A which raised to the 43 zillionth power is unity and for no smaller power. That could be a lot easier to memorize than the Devil's algorithm (but would take much longer to cycle the cube).
It's been discussed there and many other places that you will always get back to the initial state after no more than 2520 repetitions of any algorithm (1260 repetitions if the algorithm is restricted to face turns only).
How about: "every cyclic group is abelian, but the Rubik's Cube group is not"?
 
Joined
Aug 19, 2012
Messages
5
Likes
0
Location
Belgium
#49
Why is the maximum order of an element 2520 in the case you also use middle layer turns, while in the usual Rubik's Cube group (face turns only) the maximum order of an element is 1260? I don't really see why adding middle layer turns double the maximum order?

Or is it because in the face + middle layer turning case, configurations that are equal under octahedral rotation symmetry are not considered to be the same? While in the face turning case you have no multiple configurations that are the same under octahedral rotation symmetry simply because the face pieces are fixed?

Or do you also consider x, y and z as group elements?


_____
Nils
 
Joined
Oct 8, 2006
Messages
914
Likes
15
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
cuBerBruce
Thread starter #50
Why is the maximum order of an element 2520 in the case you also use middle layer turns, while in the usual Rubik's Cube group (face turns only) the maximum order of an element is 1260? I don't really see why adding middle layer turns double the maximum order?
When you allow middle layer turns, you allow centers to move (with respect to the layers you are referring to as U, F, etc.). When centers are allowed to move, the parity constraint of the cube becomes that the total parity of corners, edges, and centers must be even. The constraint that the corner parity must match the edge parity becomes removed! This allows a corner position of order 45 to be combined with an edge position of order 56. This provides an order 2520 position. For example, U R' U2 L' F S.

Or do you also consider x, y and z as group elements?
If you consider x, y, and z as group elements, you end up with a group 24 times larger than the normal Rubik's cube group. But you don't have to use these cube rotations. The above example (U R' U2 L' F S) is an element of the cube group that uses the DB edge as the reference, <U, E, L, R, F, S>. This group is the same size as the normal (fixed centers) cube group, but still has an order 2520 element.
 
Joined
May 17, 2009
Messages
4,972
Likes
14
Location
Ponyville
WCA
2009WHIT01
YouTube
ben1996123
#52
Could someone tell me what B is in terms of U R L D and F?
D' =
R2 U F2 U L2 U B2 U R2
L U L' U R U2 R2 F R F'
R' U2 R
U L' U' L2 U L'
y' U' R U' R' U2 R U' R'
U' F R U R' U' R' F' L F R F' L'
U R2 U R U R' U' R' U' R' U R' U

so you could inverse and rotate that if you want.

F' D F' D F D F D F' D' F' D2 F' U L D' L' U' L D F D F' D' L' F D F D' F2 D F D' F L F' L2 F L F' R' F2 R D R' D' R2 F2 R' F' L F' L' R2 F' U2 F' L2 F' D2 F' R2
 
Joined
Jan 31, 2013
Messages
514
Likes
12
Location
U.S.A.
YouTube
elrog3
#58
This is great and very impressive, but I dare you to come up with one that goes through every possible position the cube can be assembled into. :D Knowing Bruce, hes already done this and just hasn't told anyone.
 

JasonK

Premium Member
Joined
Oct 31, 2010
Messages
1,335
Likes
9
Location
Melbourne, AUS
WCA
2011KILB01
#59
This is great and very impressive, but I dare you to come up with one that goes through every possible position the cube can be assembled into. :D Knowing Bruce, hes already done this and just hasn't told anyone.
Surely that's impossible? You can't get to unsolvable states by doing moves on a solvable cube.
 
Joined
Dec 18, 2007
Messages
7,830
Likes
34
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
qqwref2
#60
(Devil's Alg) [twist corner clockwise] (Devil's Alg) [twist corner clockwise]
(Devil's Alg) [flip edge]
(Devil's Alg) [twist corner clockwise] (Devil's Alg) [twist corner clockwise]
(Devil's Alg) [swap two edges]
(Devil's Alg) [twist corner clockwise] (Devil's Alg) [twist corner clockwise]
(Devil's Alg) [flip edge]
(Devil's Alg) [twist corner clockwise] (Devil's Alg) [twist corner clockwise]
(Devil's Alg)
 
Thread starter Similar threads Forum Replies Date
O Puzzle Theory 17
C Puzzle Theory 30
Top