A Hamiltonian circuit for Rubik's Cube!

[Stefan]

I will try to come up with an updated version of the specification in the near future, or at least try to provide more information about the relationship between the q_shortcut.txt and q.txt files so that the subsequences for q and Q can be more easily related to the actual sequences.

I assume you mean q and q? It's called that in both files.

I'm trying to verify the length and the move distribution, and this is where I'm stuck right now. With indexes using q_shortcut.txt but the actual moves in q.txt, I need to know how to match them and it's not obvious to me.

[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