A Hamiltonian circuit for Rubik's Cube!

[cuBerBruce]

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]

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?

 

[cuBerBruce]

Why did you define T/Q/X in readme.txt instead of in misc.txt like the other inverses?

Yes, the definitions for T/Q/X should have been included in the misc.txt file. I'll plan to update the misc.txt file.

 

[CarlBrannen]

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]

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]

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]

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

 

[Swordsman Kirby]

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]

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]

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.

 

[CubeRoots]

Could someone tell me what B is in terms of U R L D and F?

 

[ben1996123]

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

 

[vcuber13]

i think Chris' signature has something like that


yup:
D = R L F2 B2 L' R' U R L B2 F2 L' R'

 

[Stefan]

You can easily do that yourself, doesn't even take a minute:

 

[CubeRoots]

You can easily do that yourself, doesn't even take a minute:

not if you don't have the software!

but thankyou though

 

[Stefan]

Getting the software doesn't take a minute, either

And it's quite useful, so I highly recommend having it.

 

[CubeRoots]

Getting the software doesn't take a minute, either

And it's quite useful, so I highly recommend having it.

I am on it now

 

[elrog]

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. Knowing Bruce, hes already done this and just hasn't told anyone.

 

[JasonK]

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

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