Thread: A Hamiltonian circuit for Rubik's Cube!

1. Oops! I had an error in the file x.txt within the .zip archive. The sequence for x had two moves missing from the beginning. I figure I must have typed "x=" while in replace mode instead of insert mode and not realized that. The correct .zip archive is now on the site. The sequence x contains 73483059 moves.

2. Originally Posted by Cubenovice
Congratulations!

I guess this is a good time to rename God's algorithm:

Bruce's Algorithm

Now that this one is out of the way: what is there still to be discovered about the 3x3x3?
Except this is Devil's algorithm, not God's algorithm

3. Originally Posted by qqwref
I, for one, would like to see how fast Feliks can execute it.
43,252,003,274,489,856,000/9 = 4,805,778,141,609,984,000 seconds 152,390,225,190 years 11.123 universe ages (assuming the universe is 13.7 billion years old) at 9tps

4. Originally Posted by Stefan
NanoZip 0.09 alpha with "cm" setting got it to 2,754,024 bytes, that's 38.8% of your zip's size. But shouldn't a full representation of your construction method/algorithm be even much smaller? (I'm not that familiar with Kolmogorov complexity, don't know what exactly is allowed and how it's counted)
Well, I could have done more to make the representation I had more compact, if that's what you mean. The x.txt file is pure sequence of individual moves, for example. But I left it that way so subsequence ranges used in the misc.txt and RubiksCubeHamilton.txt would directly correspond with the sequence as given. Also, I wanted to announce this at the MIT Spring 2012, and didn't really have the time to work on making it more compact.

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.

Originally Posted by Cubenovice
Congratulations!

I guess this is a good time to rename God's algorithm:

Bruce's Algorithm

Now that this one is out of the way: what is there still to be discovered about the 3x3x3?
Originally Posted by theZcuber
Except this is Devil's algorithm, not God's algorithm
I think Cubenovice was just sort of trying to compliment me. That post reminded me about the movie Bruce Almighty.

5. Congratulations on the successful completion of this work!

BTW, how the whole sequence affects six face centers?

6. Originally Posted by theZcuber
Except this is Devil's algorithm, not God's algorithm
pff semantics....

For me Gods alg is one single alg that solves every (legit) cube state.
Bruce achieved just that

7. Originally Posted by stannic
Congratulations on the successful completion of this work!

BTW, how the whole sequence affects six face centers?

Bruce, do you think this result shows that such a Hamiltonian cycle might exist for the supercube 3x3x3 as well? Is this question possibly solvable in a reasonable amount of time and effort, or is the complexity of that problem larger than is reasonable?

8. Originally Posted by cuBerBruce
Well, I could have done more to make the representation I had more compact, if that's what you mean.
What I meant was to not measure the computed move sequences, but to measure the program code that computed them, as that's a representation as well. Surely that is or could be much shorter?

9. Originally Posted by stannic
BTW, how the whole sequence affects six face centers?
Originally Posted by cmhardw

Bruce, do you think this result shows that such a Hamiltonian cycle might exist for the supercube 3x3x3 as well? Is this question possibly solvable in a reasonable amount of time and effort, or is the complexity of that problem larger than is reasonable?
Obviously the B center is unaffected. I also know that the F center ends up in its original orientation. When I finish calculating the distribution counts for the other turns, this will be a trivial calculation. Every F turn can be matched with a corresponding F' turn except for 12 F turns (due to making use of the identity (U' R' U F)6 twice).

Of course, I was not trying to create a supercube Hamiltonian circuit, so I didn't care about tracking the orientations of the center pieces. It's not immediately clear to me if the result can easily be extended to generate a supercube Hamiltonian circuit.

10. Originally Posted by Cubenovice
For me Gods alg is one single alg that solves every (legit) cube state.
Bruce achieved just that
That's Devil's alg, you've just got your terms confused. God's alg is an alg (well, a collection of algs) that can solve any cube state optimally.

I feel like finding a Hamiltonian circuit for supercube positions would be significantly harder than this problem.

Posting Permissions

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