Calculating "The Devil's Algorithm"

[930913]

Are we sure that there is no solution shorter than the ones suggested above?

[Stefan]

Are we sure that there is no solution shorter than the ones suggested above?

This:

As far as I know, though, there's nothing theoretically stopping us from making a sequence that is about 1/1260 of the length of the full Devil's Algorithm, such that applying the sequence over and over will go through every position at some point (i.e. the sequence 1260 times is its own Devil's Algorithm). It wouldn't help much in practice, though, since it would still be over 10^16 moves long.

[930913]

Are we sure that that is the smallest algorithm possible?

[Stefan]

Only if it exists.

[mocenigo]

whauk, your argument is correct. I think that a bit of group theory simplifies it. If such an algorithm g existed, then the group of the 3x3x3 cube would be cyclic (generated by one element), in particular abelian (commutative). However, it is not, because for instance RU is not equal to UR.

However, one could ask if there is a sequence of movements g such that any position can be obtained WHILE performing g a given number of times. I.e. g*a times and a prefix of the sequence of movements of g. ONe can prove that the maximal order of an element of the 3x3x3 Rubik Group is 1260, i.e. there is no sequence that will only return to the initial state after strictly MORE than 1260 repetitions. Since the cube has 43252003274489856000 positions, the a lower bound for the length of this algorithm would be 43252003274489856000/1260 = 34326986725785600 moves, which would make it quite difficult to memorize...

[Thekirbycross]

What if you a had an algorithm with a traversal of two that would go through half of the possible combinations of a three by three . That seems easier to find.

[ben1996123]

What if you a had an algorithm with a traversal of two that would go through half of the possible combinations of a three by three . That seems easier to find.

you're late. devils alg for 3x3 has already been found.

[piece popper]

Wouldn't it be pointless to have a devils algorithm for the 3x3 since there are so many permutations?

[Swordsman Kirby]

Wouldn't it be pointless to have a devils algorithm for the 3x3 since there are so many permutations?

No one said it'd be useful in practice.