- While we're on this topic I thought I would post something related

that I found.

How could one construct an algorithm that would cycle through all

possible positions of the cube (a "Devil's Algorithm" as I've seen

it written).

The algorithms would be good as long as it cycled though all

43252003274489856000 positions on the cube, regardless of whether it

repeated positions or not.

This is of course possible, even with a random string of notation

that is absolutely enormously larger than the number of possible

combinations to the cube.

However, the interesting question is whether or not it is possible

to have an algorithm of length 43252003274489855999 (staring from

the solved state) that cycles through all possible positions of the

cube (including having started at the solved state). Maybe it

doesn't even have to cycle through all the positions, but just have

the first 43252003274489855999 moves pass through the same number of

states (starting from the solved, or technically any, state.

Maybe you could look at this by drawing a graph with

43252003274489856000 nodes as a bipartite graph including all even

an odd positions, and also grouped together with various

characteristics (say positions that are all 2 moves away from each

other are drawn close together). Each position could only reach 18

others, 17 if you include the fact that you had to do a move to get

to that position. To be more precise, only quarter turns would be

allowed, since performing a double turn is by the purest sense

either doing R R or R' R' or some other equivalent

I honestly haven't put too much thought into this to be honest, but

it is an interesting question nonetheless. Would using graph theory

and trying to create some sort of Hamiltonian chain, or even a

Hamiltonian cycle, work as a way to do this?

Since that would take too much computing power, are there any

patterns we can use to come up with such an algorithm?

Also would this algorithm have any sort of

regularity/symmetry/interesting charateristics, or would it be

totally random in appearance?

There would of course be an infinite number of algorithms that would

achieve this affect, however how many are there with length

43252003274489855999, if any at all? If there aren't any of that

length, what is the shortest possible lentgh you can have to cycle

through all the positions of the cube? Can you do it without

repeating any positions at all?

Can you repeat positions often, though come up with an easy pattern

for writing out a Devil's algorithm?

I guess the holy grail of this would be any algorithm of exactly

length 43252003274489856000 that perfectly cycled through all the

possible positions of the cube. Such that, starting from any state,

if you performed this algorithm you would not only end at the same

state you started at, but have cycled through all possible positions

as well.

Just some questions I thought might spark some conversation.

Chris - --- In speedsolvingrubikscube@yahoogroups.com, cmhardw <no_reply@y...>

wrote:>

Hey Chris,

> Hey David, that's a really cool puzzle!

>

> Just some opening thoughts.

>

> First it would help to know the numer of possible states that can be

> reached using only 2 quarter turns (assuming that repetition of

> turning the same face twice is allowed).

>

> I count 115 positions reachable by doing two quarter turns. 96 if

> they are perpendicular faces, 12 if they are parallel faces, and 7

> if you turn the same face twice in succession.

I had meant all positions involving two sides, but you are allowing

for a side to be turned twice; that's OK with me.

For clarity's sake I'll lay them all the possibilities out.

Two quarter turns allowing the second turn to be the same side as

the first, including repeated positions: (6*2)*(6*2)=144 positions: if

same side twice isn't allowed (6*2)*(5*2)=120

12 are two turns on one side resulting in a double turn

RR, LL, FF, BB, UU, DD

R'R', L'L', F'F', B'B', U'U', D'D'

12 are two turns on one side resulting in a solved cube

RR', R'R, LL', L'L, FF', F'F, BB', B'B, UU', U'U, DD', D'D

6 * 16 = 96 are adjacent sides

RF, RF', R'F, R'F'

RB, RB', R'B, R'B'

RU, RU', R'U, R'U'

RD, RD', R'D, R'D'

LF, LF', L'F, L'F'

LB, LB', L'B, L'B'

LU, LU', L'U, L'U'

LD, LD', L'D, L'D'

FR, FR', F'R, F'R'

FL, FL', F'L, F'L'

FU, FU', F'U, F'U'

FD, FD', F'D, F'D'

BR, BR', B'R, B'R'

BL, BL', B'L, B'L'

BU, BU', B'U, B'U'

BD, BD', B'D, B'D'

UR, UR', U'R, U'R'

UL, UL', U'L, U'L'

UF, UF', U'F, U'F'

UB, UB', U'B, U'B'

DR, DR', D'R, D'R'

DL, DL', D'L, D'L'

DF, DF', D'F, D'F'

DB, DB', D'B, D'B'

6 * 4 = 24 opposite side moves of which 12 are duplicates opposite

one another

RL same as LR

RL' same as L'R

R'L same as L R'

R'L' same as L'R'

FB same as BF

FB' same as B'F

F'B same as B F'

F'B' same as B'F'

UD same as DU

UD' same as D'U

U'D same as DU'

U'D' same as D'U'

All positions minus duplicate and solved positions 144 - 24 = 120

All positions minus doubled turns minus duplicate positions

144 - 24 - 12 = 108

I'll get to the rest later.

My best,

David J