So what you're saying is that when I'm solving a 2x2 and someone says something similar to "isn't there just a bunch of moves that will always solve it?" I can just hand them this?
So what you're saying is that when I'm solving a 2x2 and someone says something similar to "isn't there just a bunch of moves that will always solve it?" I can just hand them this?
Originally Posted by cuBerBruce
http://games.groups.yahoo.com/group/.../message/42742
Well, a Hamiltonian path on Rubik's cube is a path that visits each cube state(configuration) exactly once. Bruce found such sequence for 2x2x2 cube. 2x2x2 has 3,674,160 distinct states; so this Hamiltonian path has 3,674,159 moves and visits exactly 3,674,160 configurations of the cube.
(Actually, he found a Hamiltonian cycle that returns to the starting configuration after 3,674,160th move).
When there is no condition "that visits each state exactly once", there is a simple way to make "a bunch of moves" that will always solve cube at some point. The number of moves in this bunch will be at most d*(N-1) where d is diameter of the cube and N is the number of states.
For example, with 2x2x2 and half turn allowed, it is possible to write sequence of at most 11*3,674,159 = 40,415,749 moves. To do this, you can enumerate all cube configurations (solved cube is #1, some other cube configuration is #2, some other is #3, and so on up to #3,674,160). Then, starting from configuration #1, you can reach configuration #2 in at most 11 moves because it is the diameter. Then, starting from #2, you can reach #3 in at most 11 moves, etc.
In other words, when you are solving a 3x3 or even 4x4 and someone asks whether there is a sequence of moves that will always solve it (without the condition "to visit each vertex exactly once"), the answer is yes.
BTW, how this upper bound can be improved? Of course Bruce already found shortest possible path for 2x2x2 cube (3,674,159 moves).
With 3x3x3, simple upper bound is d*(N-1) = 20 * (43,252,003,274,489,856,000 - 1) = 865,040,065,489,797,119,980 moves.
It looks like it is going to be a pretty long move sequence or maneuver (as you call it). But I thought the diameter of 2x2 graph is about 8 (I am sure it is less than 20) right? So, the state that 'z' gives us could be simplified, to a sequence of length less than 8, right?
That wouldn't be a Hamiltonian-circuit (visiting every possible 2x2x2 state exactly once and also returning to the starting state).
Last edited by Stefan; 12-29-2011 at 07:23 PM.
Good point.
And even better, if we allow multiple turns of the same face in a row (and I don't see why we shouldn't for a Hamiltonian path): Consider the set of 3x3 cosets created from the subgroup <U,D>, which has 16 members. It's clear that each coset has a Devil's Algorithm ((UUUD)3UUU), so all we have to do is go through all elements of one coset (15 moves), go to the next (<=20 moves), and repeat. There are 2703250204665616000 of these cosets, so our path contains at most 15 + (20+15)*(2703250204665616000-1) = 94613757162946559980 moves, which is only about 2.1875 times the length of our theoretical Hamiltonian path. You could get a similar and better result by starting with other subgroups: <R,U>, <R2,L2,U2,D2,F2,B2>, etc.
EDIT: Hmm, doesn't a Hamiltonian path (not necessarily cycle) exist for any Cartesian product of two groups that each have a Hamiltonian path? Could we take G=<R,L,U2,D2,F2,B2>, and H be the group of 3x3 equivalency classes (in the sense that equivalent positions differ by a permutation in G), and then find a Hamiltonian path on G, and also a Hamiltonian path on H (using only U,D,F,B moves)? Would that give us a Hamiltonian path for the whole cube?
Last edited by qqwref; 12-29-2011 at 07:33 PM.
Totally my bad. Misinterpretted this to be devil's algorithm (or whatever the algorithm when repeated gives a new state every time it is executed till it covers all the states before reaching the initial state.)
So, if I correctly understand, this when executed on a solved 2x2, should give us the solved 2x2 again, right?
And does this sequence give a new state for each quarter turn, is it?
I guess the above comment answers my last question. It doesn't visit a new state for each quarter turn for sure if the Hamiltonian path is longer than the size of 2x2 space
Last edited by Brest; 12-30-2011 at 01:00 AM. Reason: post merge
It *is* one kind of devil's algorithm. See post #10.
Yes.
Yes, except for the last turn.
It isn't longer. It can't be. Otherwise it wouldn't be Hamiltonian.
Last edited by Stefan; 12-29-2011 at 07:41 PM.
The one that was given is just as long as the number of 2x2 states, so yeah, it does provide a new position every turn until all positions have been reached. But a longer one wouldn't necessarily do that; it would just give every position at some point during its execution.
It's actually impossible to create an algorithm on the 2x2 or 3x3 that, when you repeat it, gives a new position every time it is executed until all positions have been reached. The reason is that no position has a high enough order (number of times it must be executed to return to the initial state) to cover all of the positions on the cube.
Posting Permissions
Reply With Quote
Bookmarks