• Welcome to the Speedsolving.com, home of the web's largest puzzle community!
    You are currently viewing our forum as a guest which gives you limited access to join discussions and access our other features.

    Registration is fast, simple and absolutely free so please, join our community of 40,000+ people from around the world today!

    If you are already a member, simply login to hide this message and begin participating in the community!

A Hamiltonian circuit for Rubik's Cube!

cuBerBruce

Member
Joined
Oct 8, 2006
Messages
914
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
Visit Channel
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
 

A Leman

Member
Joined
Jan 22, 2012
Messages
631
Location
New Jersey
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!!!
 

cuBerBruce

Member
Joined
Oct 8, 2006
Messages
914
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
Visit Channel
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.
 

Lucas Garron

Administrator
Joined
Jul 6, 2007
Messages
3,718
Location
California
WCA
2006GARR01
YouTube
Visit Channel
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! :p

- 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
Joined
Oct 8, 2006
Messages
914
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
Visit Channel
- 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
Joined
Feb 6, 2010
Messages
2,290
Location
Vlaams-Brabant (Belgium)
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
Joined
May 7, 2006
Messages
7,280
WCA
2003POCH01
YouTube
Visit Channel
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
Joined
Nov 11, 2010
Messages
56
Location
Aachen, Germany
WCA
2008HACK01
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
Joined
May 7, 2006
Messages
7,280
WCA
2003POCH01
YouTube
Visit Channel
So, what do I get wrong

The topic of this thread.

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.
 

cuBerBruce

Member
Joined
Oct 8, 2006
Messages
914
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
Visit Channel
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.
 
Thread starter Similar threads Forum Replies Date
O Puzzle Theory 17
C Puzzle Theory 37
Top