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

Solving the cube without any decision making

Tronman

Member
Joined
Jan 8, 2010
Messages
5
Please do not make this into an attack on the integrity of my friend. I do not believe for a minute that she is lying (that is, deliberately saying it knowing its not true), simply mis-remembering something. That's not what my question is about.

Let me try a different approach: might there be a simple solution algorithm where once a person learned it, it might "feel" like simple memorization, that is the decisions to make are almost subconscious or automatic?
 

FatBoyXPC

Member
Joined
Nov 28, 2009
Messages
1,796
WCA
2010LACH01
YouTube
Visit Channel
To shorten up the Devil's Algorithm read (well I haven't really read this but I do understand already this works), and to reiterate what one poster already said: Yes, there does exist an algorithm, that at some point in the algorithm (beginning, somewhere in the middle, or end) the cube will end up solved. This algorithm basically just needs to hit every orientation for every "location" (often called permutations here) on the cube, and also move cubes around. Eventually if you repeat this algorithm enough times, the cube will come out solved (somewhere in this said algorithm). The theory works, but proving it is practically useless.

What probably happened is your friend probably misunderstood what she read or was told. Many people have said this to me, and even when I explain algorithms to people I get the common "do you just do something over and over until it works?" sort of thing. I think they say that because that's what they want to believe, so they can then think they can do it too. Now, if they learned, they could do it very easily. They just don't want to have to think about it. It'd take incredibly longer to even run though this algorithm once, than it would most cubers to even just solve (not to mention record holders).
 

meichenl

Member
Joined
Aug 27, 2009
Messages
32
WCA
2009EICH01
YouTube
Visit Channel
Suppose you have a fixed sequence of 30 moves. If you do that sequence, you'll presumably go through 30 different states of the cube (possibly not if the sequence cancels itself out, but let's be optimistic and suppose it does not).

Do the same sequence again. You'll go through 30 more states, for 60 total. Do it again and you'll have gone through 90 total, etc. Because there are 43 quintillion possible states of the cube, in some cases you'd have to do the sequence of 30 moves 43 quintillion/30 = about 1.4 quintillion times before solving the cube.

So if you had a sequence of 30 moves that you could do over and over about 10^18 times without going back to where you started, you might be able to do what the original poster wanted.

However, it is not possible to have a sequence of any length that you do one quintillion times without repeating. The reason is simple. Once you do the sequence, you've done a permutation of the edges, and a permutation of the corners, and maybe also changed some of their orientations. For example, the sequence might take three edges and send them around in a cycle (edge 1 goes to edge 2, edge 2 to edge 3, and edge 3 to edge 1), and also move five corners around in a cycle (corner 1 to corner 2, ... until corner 5 goes back to corner 1). If that was what your series of moves did, and you repeated it three times, the edges would all be back where they started. The first time would send edge 1 to edge 2's spot. The second time would send it to edge 3's spot. The third time would send it home. Then, if you repeated the sequence two more times, for five total, the edges would be messed up again, but the corners would be in place. If you did the entire sequence 15 times, the edges and corners would all be back in their starting places.

Those edges and corners might also be flipped or rotated, but if so, by doing the sequence 90 times (15 * 3 *2, three for the corner orientations to be fixed and two for the edges), all the pieces would have to be oriented correctly, and the cube would be solved. This sequence of moves would be said to have "order 90".

It is possible to find things with order higher than 90, but not much higher. The highest order you could achieve is 1260, which would come about if you put the corners in a three cycle and a five cycle, and the edges in a seven cycle and two two cycles, and then made sure that some corner and edge orientations got messed up. There are some technical reasons why you cannot build cycles that would have even higher order - this is the best you can actually achieve. All of what I've said above is sure-fire (unless I made a mistake counting the cycles that make the highest-possible order element of the cube group), and can be made mathematically precise if it's not convincing.

So if the sequence has 30 moves, somewhere in the first 1260 times you do it the cube will go back to solved, and you've only covered 30*1260, or about 40,000 positions. So you could only solve 40,000 positions that way. The shortest thing you could possibly remember that would go through every position would be 4.3*10^19/1260, or 3.4*10^16 moves long. Your computer's hard drive could not store this sequence.

This doesn't mean a sequence this short exists that does the job, only that any sequence that goes through all the positions must be at least this long.

Reading through the link some people provided earlier in the thread, I see the author of the page on the Devil's Algorithm did the same thing with a 2x2 cube to give a minimum length of the sequence you'd need there.

So, I'm not sure whether you'd have to remember a sequence of length 43 quintillion or just 34 quadrillion (or possibly longer than 43 quadrillion, since the "Devil's Number" is unknown) to solve the cube with no decision making (other than knowing when to stop), but either way it is not likely to happen.
 
Last edited:

meichenl

Member
Joined
Aug 27, 2009
Messages
32
WCA
2009EICH01
YouTube
Visit Channel
Also, I should point out that when I said "your computer's hard drive could not store this sequence", I meant that it could not be stored uncompressed.

Such a sequence actually contains very little information, and one could write a very short program to generate it.
 

Hiero

Member
Joined
Dec 23, 2009
Messages
221
Location
Dallas
WCA
2010MAND01
YouTube
Visit Channel
This reminds me. I used to know the cure for AIDS but I forgot it. I thought I remembered curing a few people, but I don't remember how I did it. Some person taught me how to do it, but they also forgot.

Oh about the cube thing. Yeah there is a really easy algorithm less than 30 moves that solves the cube, but that's the easy way. We like memorizing a ton of algorithms and doing it that way for the fun of it.


Oh and make sure you edit your old post instead of adding a new one or the guys here get really mad.
 
Last edited:

HALLU

Member
Joined
Oct 1, 2009
Messages
35
The algorithm would have to be so long that it would go through ALL of the possible positions the cube could be in. Possible if you let a computer calculate it, but a person would not be able to solve it like this, simply because the algorithm would be waaaay to long...
 

cuBerBruce

Member
Joined
Oct 8, 2006
Messages
914
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
Visit Channel
It is possible to find things with order higher than 90, but not much higher. The highest order you could achieve is 1260, which would come about if you put the corners in a three cycle and a five cycle, and the edges in a seven cycle and two two cycles, and then made sure that some corner and edge orientations got messed up.

Actually, the highest order being 1260 is only correct if you only consider move sequences that only contain face-layer turns. If you allow double-layer turns or inner-layer turns, then it's possible to have sequences that could be repeated 2520 times before you return to the starting state.
 

meichenl

Member
Joined
Aug 27, 2009
Messages
32
WCA
2009EICH01
YouTube
Visit Channel
Hi Bruce,

Could you explain that some more, please? How are double-layer turns or inner-layer turns any different than face-layer turns? As far as the Rubik's cube group is concerned r = L, for example, and M = R L', so I don't understand how adding in these new moves could make a difference.

I notice the number you quoted is double mine. Are you referring to a redefinition of the Rubik's cube group where the location of the centers in physical space matters? If so, why is the figure doubled rather than quadrupled?
 
Last edited:

cuBerBruce

Member
Joined
Oct 8, 2006
Messages
914
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
Visit Channel
Hi Bruce,

Could you explain that some more, please? How are double-layer turns or inner-layer turns any different than face-layer turns? As far as the Rubik's cube group is concerned r = L, for example, and M = R L', so I don't understand how adding in these new moves could make a difference.

I notice the number you quoted is double mine. Are you referring to a redefinition of the Rubik's cube group where the location of the centers in physical space matters? If so, why is the figure doubled rather than quadrupled?

In terms of move sequences, you can't consider r = L. For instance r U does not put the cube in the same state as L U. Because a sequence containing inner layer turns or double-layer turns can change how the centers are placed with respect to "up," "down," "left," etc., you have to consider how a sequence leaves centers permuted as well as corners and edges. That's why you can get higher orders.
 

meichenl

Member
Joined
Aug 27, 2009
Messages
32
WCA
2009EICH01
YouTube
Visit Channel
In terms of move sequences, you can't consider r = L. For instance r U does not put the cube in the same state as L U.

That is a trivial objection (r U = L F), but I see your point. This way of thinking about the order of the group elements was not relevant to the problem I was originally considering because the cube is considered solved regardless of its orientation in physical space.

I also don't see how this increases the maximum possible order of an element to 2520. 2520 = 2^3 * 3^2 * 5 * 7

The centers cannot be in an 8-cycle, 9-cycle, 5-cycle (since this would mean exactly one center is in the correct place), or 7-cycle, so how does adding in permutations of the center help us reach an order 2520?
 

qqwref

Member
Joined
Dec 18, 2007
Messages
7,834
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
That is a trivial objection (r U = L F)

No, not at all. r U and L F are not the same when you are talking about doing move sequences over and over again: doing r U r U ... will have a much different effect than doing L F L F .... That is why doing double layer turns is not quite the same as doing single layer turns, because when you do the sequence again you do it without reorienting the cube, so the orientation matters a lot.
 

meichenl

Member
Joined
Aug 27, 2009
Messages
32
WCA
2009EICH01
YouTube
Visit Channel
No, not at all. r U and L F are not the same when you are talking about doing move sequences over and over again: doing r U r U ... will have a much different effect than doing L F L F .... That is why doing double layer turns is not quite the same as doing single layer turns, because when you do the sequence again you do it without reorienting the cube, so the orientation matters a lot.

I didn't say r U r U = L F L F. I said r U = L F. r U r U = L F L D. You can similarly change any sequence with double layer turns into an equivalent sequence of single layer turns. Double layer turns do not add anything.

Edit: Okay, I think I see your point. Doing r U over and over isn't the same as doing L F over and over. That makes sense. It threw me off because this is not the order of a group element in the standard Rubik's cube group any more - two cubes that are related to each other solely by cube rotations have to be considered different scrambles in order for this definition to form a group. That seems a strange way of thinking about the cube. Also, I could use an example of something with order 2520, because for the reason I raised before I don't see how including center permutations allows for group elements with higher order.
 
Last edited:

cuBerBruce

Member
Joined
Oct 8, 2006
Messages
914
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
Visit Channel
Also, I could use an example of something with order 2520, because for the reason I raised before I don't see how including center permutations allows for group elements with higher order.

I mentioned a way to get an order-2520 position in a thread over two years ago ([post=20826]link[/post]).

An order-2520 position can be obtained with misoriented corner cycles of 3 and 5, misoriented edge cycles of 4 and 7, and a 4-cycle of centers. Note that when the centers are in an odd permutation (such as a 4-cycle), the cubie permutation parity for the edges and corners must be opposite, rather than the same. In the above, the centers don't really increase the order. The center permutation merely permits corners and edges to have opposite parity instead of the same parity, allowing a combination that gives an order of 2520 which is not possible when corner parity must match edge parity.
 

Lucas Garron

Administrator
Joined
Jul 6, 2007
Messages
3,718
Location
California
WCA
2006GARR01
YouTube
Visit Channel
Also, I should point out that when I said "your computer's hard drive could not store this sequence", I meant that it could not be stored uncompressed.

Such a sequence actually contains very little information, and one could write a very short program to generate it.
Interesting exercise: Prove that it's easy to come up with a "reasonable" algorithm (on the order of about 10^19 moves) that goes through each state, such that its nth move can be computed almost instantly.
You can't really write down the whole algorithm, but you could write down any portion on demand.
 

meichenl

Member
Joined
Aug 27, 2009
Messages
32
WCA
2009EICH01
YouTube
Visit Channel
Interesting exercise: Prove that it's easy to come up with a "reasonable" algorithm (on the order of about 10^19 moves) that goes through each state

Maybe you break the Rubik's cube group down into cosets, for example the cosets of <U2, D2, F2, B2, R, L>, then find a mini Devil's algorithm (Beelzebub's Algorithm?) that takes you through each member of the coset. Then you just need a short algorithm that takes you from coset to coset at the completion of each Beelzebub's Algorithm.

If the Beelzebub's Algorithm is too long, you might iterate the process.

Is this the right track at all?
 

Lucas Garron

Administrator
Joined
Jul 6, 2007
Messages
3,718
Location
California
WCA
2006GARR01
YouTube
Visit Channel
Interesting exercise: Prove that it's easy to come up with a "reasonable" algorithm (on the order of about 10^19 moves) that goes through each state

Maybe you break the Rubik's cube group down into cosets, for example the cosets of <U2, D2, F2, B2, R, L>, then find a mini Devil's algorithm (Beelzebub's Algorithm?) that takes you through each member of the coset. Then you just need a short algorithm that takes you from coset to coset at the completion of each Beelzebub's Algorithm.

If the Beelzebub's Algorithm is too long, you might iterate the process.

Is this the right track at all?
I'm not sure if that works, although it's nice when it does (Floppy?).

I was thinking of something much more straightforward and brainless, since you're allowed to revisit states.
 

qqwref

Member
Joined
Dec 18, 2007
Messages
7,834
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
What do you mean by "on the order of 10^19 moves", Lucas? There are already 4 times that many states, so I'm not sure how much more leeway you're giving us.

I know an easy way to get an alg that has an upper-bounded length of roughly 8.6 * 10^20, but that's as good as I can prove without a cleverer idea.
 
Top