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

cuBerBruce

Member
Joined
Oct 8, 2006
Messages
914
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
Visit Channel
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).
 

Stefan

Member
Joined
May 7, 2006
Messages
7,280
WCA
2003POCH01
YouTube
Visit Channel
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?
 

CarlBrannen

Member
Joined
May 6, 2012
Messages
367
Location
Pullman, WA
WCA
2013BRAN01
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.
 

cuBerBruce

Member
Joined
Oct 8, 2006
Messages
914
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
Visit Channel
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.
 

CarlBrannen

Member
Joined
May 6, 2012
Messages
367
Location
Pullman, WA
WCA
2013BRAN01
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).
 

cuBerBruce

Member
Joined
Oct 8, 2006
Messages
914
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
Visit Channel
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
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"?
 

Nils

Member
Joined
Aug 19, 2012
Messages
5
Location
Belgium
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
 

cuBerBruce

Member
Joined
Oct 8, 2006
Messages
914
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
Visit Channel
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.
 

ben1996123

Banned
Joined
May 17, 2009
Messages
4,972
Location
Ponyville
WCA
2009WHIT01
YouTube
Visit Channel
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
 

Stefan

Member
Joined
May 7, 2006
Messages
7,280
WCA
2003POCH01
YouTube
Visit Channel
You can easily do that yourself, doesn't even take a minute:

2lia0c5.png
 

elrog

Member
Joined
Jan 31, 2013
Messages
518
Location
U.S.A.
YouTube
Visit Channel
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,334
Location
Melbourne, AUS
WCA
2011KILB01
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.
 

qqwref

Member
Joined
Dec 18, 2007
Messages
7,834
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
(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 37
Top