# A Hamiltonian circuit for Rubik's Cube!

#### cuBerBruce

##### Member
I have found a Hamiltonian circuit for the quarter-turn metric Cayley graph of Rubik's Cube! In fact, it only uses turns of five of the six outer layers of the cube.

In more basic terms, this is a sequence of quarter moves that would (in theory) put a Rubik's cube through all of its 43,252,003,274,489,856,000 positions without repeating any of them, and then one final move restores the cube to the starting position. Note that if we have any legally scrambled Rubik's Cube position as the starting point, then applying the sequence would result in the cube being solved at some point within the sequence.

Additional information can be found at my web site: http://bruce.cubing.net/index.html

#### cmhardw

Congratulations Bruce! This is a fascinating and amazing result! I downloaded the file, and I can't wait to check it out and attempt to understand it

Last edited:

#### Julian

##### Member
Wow! I thought this result would be way off in the future. Great job!

#### cubernya

Now everytime somebody asks you how to solve it, just give them this.

#### aronpm

##### Member
Wow, this is awesome Bruce

Now everytime somebody asks you how to solve it, just give them this.
Yeah, that sounds plausible.

#### Brest

##### Moderator
Staff member
Awesome Bruce, impressive as always!

O

#### Owen

##### Guest
Yay! I hate B moves!

#### Specs112

##### Member
Bruce should be president.

#### A Leman

##### Member
This is awesome! It must have taken you a long time and a pile of discrete math and number theory books to figure this out. Very impressive!!!

#### qqwref

##### Member
Awesome job! This is a crazy result, and I look forward to seeing how you actually found it.

PS: I, for one, would like to see how fast Feliks can execute it.

#### cuBerBruce

##### Member
Bruce, were you the one to post a Hamiltonian circuit for the 2x2 as well?

Yes, I was also the one who posted the 2x2x2 Hamiltonian circuit (after someone else posted a Hamiltonian circuit of the 2x2x2 <U, R> subgroup). I thought I better post my 2x2x2 result at that time before someone else figured out a way to connect up the 126 cosets. I had actually developed that solution in July of 2010.

It was back in late 2007 that I decided to make it a goal of mine to solve the Rubik's Cube Hamiltonian circuit problem. So this was no overnight solution. I solved the <U, R> subgroup Hamiltonian problem in 2008. I was not successful in arriving at a Hamiltonian circuit for the <U, R, F> subgroup. On Nov. 1, 2011, it finally dawned on me to consider the <U, R, D> subgroup rather than <U, R, F>. This turned out to be much easier for me to solve, and then <U, R, D, L> (only 132 cosets to deal with) was fairly easy to solve as well. This left only 2048 cosets for the final phase. While this had the same sort of difficulty as the <U, R, F> subgroup, the <U, R, F> subgroup problem had over 2.3 million cosets to deal with; over 1000 times more than 2048. By sometime in December I had determined how to finish the solution. It was just a matter of working out the details. On February 1, 2012, I had the problem essentially solved. I still had some work to take the details that had been worked out and put them into a form that describes the Hamiltonian circuit in the actual order that the sub-parts are executed.

#### Cielo

##### Member
Congratulations!

P.S: I noticed a typo in your explanation :"The problem of connnecting up the 2048 cosets".

#### Lucas Garron

Ooh, this is awesome. I've been looking forward to it ever since your previous results suggested it should be feasible. It looked too scary for me, so congratulations for getting a full solution!

- You only use quarter turns, right? That gets rid of the ambiguities around RR vs. R2
- The 7MB zip expands to 236MB (you might want to mention that on the site, too?). Any idea of the actual Kolmogorov complexity of your solution? Can it fit into a MB? Way less?
- It might be kind of cute to write an algorithm that prints out a given (short) subsequence on demand. Sort of to make a point that this algorithm is constructive and we *can* write out any part we want.
- Generalizing this: What puzzles have a Hamiltonian path? Is it obvious whether Pyraminx should have one? Megaminx? Square-1?

#### cuBerBruce

##### Member
- You only use quarter turns, right? That gets rid of the ambiguities around RR vs. R2
Yes, the solution only uses quarter-turns (both clockwise and counterclockwise), but it may use the same quarter-turn more than once consecutively. Of course you can't use the same turn four times in succession, as that would result in repeating a state. As I said, it's a Hamiltonian circuit for the QTM Cayley graph.

A half-turn on an actual cube would have the cube pass through another state midway, so limiting to quarter-turns assures that no state is passed through without being counted as a reached state.

- The 7MB zip expands to 236MB (you might want to mention that on the site, too?). Any idea of the actual Kolmogorov complexity of your solution? Can it fit into a MB? Way less?
I was thinking good lossless compressors tend to compress fairly close to the amount of actual information. But perhaps this isn't so much the case with highly compressible information, so I don't really know. (By the way, Lucas, are there limits to how much space I can use?)

- It might be kind of cute to write an algorithm that prints out a given (short) subsequence on demand. Sort of to make a point that this algorithm is constructive and we *can* write out any part we want.
I'll have to think about this. I also want to calculate the distribution of the 10 different moves that are used.

- Generalizing this: What puzzles have a Hamiltonian path? Is it obvious whether Pyraminx should have one? Megaminx? Square-1?
As mentioned on Jaap's Puzzle Page, there is a mathematical conjecture (so it's not proven) that all Cayley graphs have a Hamiltonian circuit. Cubes larger than 3x3x3 generally have indistinguishable pieces (if not stickered as supercubes) so the positions don't form a group, so I believe the conjecture would not apply to those puzzles. Square-1 positions also do not form a group. For puzzles that are not a group, it may tend to be much harder (even if possible) to find a Hamiltonian circuit, since you then can't make use of group properties.

And thanks for pointing out the typo, Cielo. I'll fix that.

Last edited:

#### Cubenovice

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

#### Stefan

##### Member
I was thinking good lossless compressors tend to compress fairly close to the amount of actual information.

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)

#### ASH

##### Member
Ok, I admit I suck at group theory (took the last course 4 years ago).
So, what do I get wrong:

- If there exists an element of the cube group which generates all elements (of the cube group) this means the group is cyclic, e.g. Cubegroup=<a>, a the proposed element
- All cyclic groups are ablian, which means that for all elements a,b \in Cubegroup: a°b=b°a holds (° is the group's operation)
- This means that 0=a°b-b°a=[a,b] (Commutator)

Which concludes that all commutators do nothing, which is obviously false.

So, tell me why I suck, pls!

#### Stefan

##### Member
So, what do I get wrong

This is about a loooong algorithm which *during* its execution visits all cube states. You're thinking of what happens when you repeat an algorithm and look at the cube only *after* each execution. The cube group isn't cyclic.

#### ASH

##### Member
You're right Stefan.

I was anyway doubting that I beat you in group theory!

At least I've been right about what I thought it was about.

#### cuBerBruce

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