• 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
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:

cmhardw

Premium Member
Joined
Apr 5, 2006
Messages
4,115
Location
Orlando, Florida
WCA
2003HARD01
YouTube
Visit Channel
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

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

Member
Joined
Dec 18, 2007
Messages
7,834
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
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
Joined
Mar 31, 2009
Messages
103
Location
Bristol, UK
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
Joined
Dec 5, 2008
Messages
482
WCA
2010FISK01
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.
 

cuBerBruce

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

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

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
Joined
Aug 1, 2007
Messages
120
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
Joined
Oct 8, 2006
Messages
914
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
Visit Channel
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
Joined
May 7, 2006
Messages
7,280
WCA
2003POCH01
YouTube
Visit Channel
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:
Thread starter Similar threads Forum Replies Date
O Puzzle Theory 17
C Puzzle Theory 37
Top