Page 5 of 7 FirstFirst ... 3 4 5 6 7 LastLast
Results 41 to 50 of 63

Thread: A Hamiltonian circuit for Rubik's Cube!

  1. #41
    Member Stefan's Avatar
    Join Date
    May 2006
    WCA Profile
    2003POCH01
    YouTube
    StefanPochmann
    Posts
    6,402

    Default

    Quote Originally Posted by cuBerBruce View Post
    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.
    Last edited by Stefan; 03-21-2012 at 06:34 AM.

  2. #42
    Member
    Join Date
    Oct 2006
    Location
    Malden, MA, USA
    WCA Profile
    2006NORS01
    YouTube
    cuBerBruce
    Posts
    798

    Default

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

  3. #43
    Member Stefan's Avatar
    Join Date
    May 2006
    WCA Profile
    2003POCH01
    YouTube
    StefanPochmann
    Posts
    6,402

    Default

    Quote Originally Posted by cuBerBruce View Post
    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...

    Quote Originally Posted by cuBerBruce View Post
    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?

  4. #44
    Member
    Join Date
    Oct 2006
    Location
    Malden, MA, USA
    WCA Profile
    2006NORS01
    YouTube
    cuBerBruce
    Posts
    798

    Default

    Quote Originally Posted by Stefan View Post
    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.

  5. #45
    Member
    Join Date
    May 2012
    Location
    Pullman, WA
    WCA Profile
    2013BRAN01
    Posts
    367

    Default

    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.

  6. #46
    Member
    Join Date
    Oct 2006
    Location
    Malden, MA, USA
    WCA Profile
    2006NORS01
    YouTube
    cuBerBruce
    Posts
    798

    Default

    Quote Originally Posted by CarlBrannen View Post
    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.

  7. #47
    Member
    Join Date
    May 2012
    Location
    Pullman, WA
    WCA Profile
    2013BRAN01
    Posts
    367

    Default

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

  8. #48
    Member
    Join Date
    Oct 2006
    Location
    Malden, MA, USA
    WCA Profile
    2006NORS01
    YouTube
    cuBerBruce
    Posts
    798

    Default

    Quote Originally Posted by CarlBrannen View Post
    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."

  9. #49
    Member
    Join Date
    Apr 2006
    WCA Profile
    2007SUNT01
    Posts
    1,798

    Default

    Quote Originally Posted by CarlBrannen View Post
    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).
    Quote Originally Posted by cuBerBruce View Post
    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"?
    Team #

  10. #50
    Member
    Join Date
    Aug 2012
    Location
    Belgium
    Posts
    5

    Default

    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

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •