A Hamiltonian circuit for Rubik's Cube!

[cuBerBruce]

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.

[theZcuber]

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

[ben1996123]

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

[cuBerBruce]

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.

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

I think Cubenovice was just sort of trying to compliment me. That post reminded me about the movie Bruce Almighty.

[stannic]

Congratulations on the successful completion of this work!

BTW, how the whole sequence affects six face centers?

[Cubenovice]

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

[cmhardw]

Congratulations on the successful completion of this work!

BTW, how the whole sequence affects six face centers?

Oh wow, I'd also be curious about this.

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?

[Stefan]

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?

[cuBerBruce]

BTW, how the whole sequence affects six face centers?

Oh wow, I'd also be curious about this.

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.

[qqwref]

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.