# A Hamiltonian circuit for Rubik's Cube!

#### cubernya

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

##### Banned
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 $$\approx$$ 152,390,225,190 years $$\approx$$ 11.123 universe ages (assuming the universe is 13.7 billion years old) at 9tps

Last edited:

#### cuBerBruce

##### Member
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.

Last edited:

#### stannic

##### Member
Congratulations on the successful completion of this work!

BTW, how the whole sequence affects six face centers?

#### Cubenovice

##### Forever Slow
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?

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

##### Member
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?

Last edited:

#### cuBerBruce

##### Member
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?
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

##### Member
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.

#### penfold1992

##### Member
super cube wouldnt be much harder... you could just say "if the cube is almost solved with just the centers need twisting then apply one of the remaining 2 algs that will fix this" then just list the 180 turn and the two 90degree algs.

#### musicninja17

##### Member
super cube wouldnt be much harder... you could just say "if the cube is almost solved with just the centers need twisting then apply one of the remaining 2 algs that will fix this" then just list the 180 turn and the two 90degree algs.
Thus removing the whole point of a circuit.

#### vcuber13

##### Member
you both missed the point, a super cube has 12(?) times more combinations

#### vcuber13

##### Member
i thought about it wrong and couldn't remember, and wouldn't it be 2048 (4^6/2)

#### Christopher Mowla

i thought about it wrong and couldn't remember, and wouldn't it be 2048 (4^6/2)
Yes. For the nxnxn supercube, factor increase = number of solved positions of the regular nxnxn cube.

EDIT:

On topic. Congratulations Bruce! This is amazing.

Last edited:

#### cuBerBruce

##### Member
I've tallied up the distribution of the different moves in the Hamiltonian circuit I made. I hope I didn't make any errors. I would like to do a somewhat brute force tally by computer to check the values.

Code:
U:  10,898,125,406,064,467,088
U': 10,727,912,135,641,656,820
R:  10,901,458,532,532,248,688
R': 10,724,506,023,073,643,108
D:             588,588,720,174
D':            588,588,580,818
L:                     268,288
L':                    268,288
F:                       1,370
F':                      1,358
B:                           0
B':                          0
The net clockwise turns of each layer is 0 mod 4, so it indeed will preserve center orientations if my calculations are correct.

#### rokicki

##### Member
Congratulations on the accomplishment. You beat me to it (although I do not
know if my approach would have succeeded in any case). Your approach is
very nice. I am also interested in how concise a formulation of the cycle can

Are there insights you've gained through this work that may help settle the
question in general? *That* would truly be a stunning achievement.

#### cuBerBruce

##### Member
Congratulations on the accomplishment. You beat me to it (although I do not
know if my approach would have succeeded in any case). Your approach is
very nice. I am also interested in how concise a formulation of the cycle can

Are there insights you've gained through this work that may help settle the
question in general? *That* would truly be a stunning achievement.
My goal was basically to come up with a solution as easily as possible, not one that necessarily has a nice structure. Generally, the structure would have been nicer if I solved each hierarchical level by producing a sequence of complete Hamiltonian paths for the cosets connected end to end by non-subgroup moves. However, it seems so much easier to make Hamiltonian circuits for each coset and connect them together with what I think of as the "interrupt approach." You start traversing a Hamiltonian circuit or path for one coset, and part way through you interrupt that traversal to traverse another coset (or multiple cosets) and come back to the original Hamiltonian path/circuit at the point where you left off. You might do several such interrupts before finishing that Hamiltonian path/circuit. While this approach is much easier, it doesn't make for the most concise sort of solutions. Perhaps expressing the solution as an algorithm or actual program code as Stefan mentioned would make it appear more concise.

I'm not quite sure what you mean by the question in general. I'm guessing you might be referring to proving the conjecture that every Cayley graph has a Hamiltonian circuit. It seems easy to use a Hamiltonian circuit for a subgroup if the larger group is generated by adding a generator that commutes with a generator for the subgroup. But if you have to add a generator that doesn't commute with the subgroup generators, you may not have a way to traverse one other coset and return to the interrupted coset at the point where you left off (as is the case with <U,R,F> and subgroup <U,R>). In this case it might be hard to prove that you can make a Hamiltonian circuit for the larger group.

#### fw

##### Member
Hi Bruce,

nice result. I like it very much! So... No offense, but how do we know for sure that your approach is correct? Brute-force-verifying your solution is not an option (right?) and you don't really give a proof that your way of generating it is not flawed (just a really rough sketch).

Flo

#### cuBerBruce

##### Member
Hi Bruce,

nice result. I like it very much! So... No offense, but how do we know for sure that your approach is correct? Brute-force-verifying your solution is not an option (right?) and you don't really give a proof that your way of generating it is not flawed (just a really rough sketch).

Flo
I certainly expect that some people would question the validity of my result. So I am hoping that someone will actually do an indpendent verification of it.

I would certainly agree that a totally brute force verification is not an option. However, I think it is possible to verify (with a computer) that the Hamiltonian paths used at each of the subgroup levels are valid, and that the cycle defined at the top level in fact traverses each of 2048 cosets of the <U,R,D,L> subgroup. In that manner, the Hamiltonian circuit should be verifiable.

I rely on the fact that if I have a sequence s that traverses all element of a subgroup of G called H, then I can start at some arbitrary element of g of G and do the sequence s, and I will traverse all of the elements of the coset gH. I also make use of the fact that if a sequence s is a Hamiltonian path for a group G, then the inverse sequence of s is also a Hamiltonian path for G. I think these concepts are quite elementary results in group theory.

#### Stefan

##### Member
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: