Orbit of sequence of cube moves determined... by the cube itself

[galvao]

Yesterday some question ocurred to me, but as the Rubik's group is too big, I think that the fellows who work with computational group theory can help me with that.

Suppose we have a 3x3x3 original rubiks cube, with white on top, yellow on bottom.
Then we will write the color of all stickers in red, blue, orange and green faces.

\( S_{0} \) = GGGG[G]GGGG RRRR[R]RRRR BBBBBBBB OOOO[O]OOOO
([R] denotes the red center and so on)

Then we do the first movement, rotating the centers of the cube in the order of the stickers described in the movement \( S_{0} \)

The new state of the cube is,

\( S_{1} \) = WGRW[G]YOGY WWBR[R]YRRY WWOBYBBR WWGO[O]OYYY

Proceding like this:

1) Is that sequence a cycle?

2) If it's not a cycle
i) Which is the cardinality of S, the set formed by all the unique \( S_{i} \) (or, using a better term, the orbit of the sequence starting in a solved rubik's cube).
ii) Which is the size of S*, the cycle contained in S? (existing \( m<n \) such that \( S_m=S_n \), \( S^{*}=\{S_{m}, S_{m+1},...,S_{n-1}\} \) - note that the first question, in other words, is "is that S=S*?"

Thank you

Galvão

 

[cuBerBruce]

If I am understanding you correctly, you are defining a way of generating a sequence of cube positions. For each cube position, you derive a maneuver based on the colors of 36 stickers at given locations on the cube. Then you perform that maneuver to arrive at the next cube position in the sequence.

Since the number of cube positions is finite, repeating such a procedure over and over will eventually result in reaching some position a 2nd time. Once that occurs, you will be in a cycle. For example, let's say that the 25th position happens to be the first occurrence of a duplicate position, let's say its the same as the 11th position. Then from the 25th position on, the sequence would repeat the 11th through the 24th positions over and over. So generally the set of all the positions in the cycle will be smaller than the full set of positions reached, unless the first duplicate happens to be a duplicate of the initial position

Most likely, it would probably take a huge number of moves before you reach a duplicate. It might not even be feasible to determine the cycle by computer simulation. One approach using a computer simulation would be to store each position reached (along with its sequence index) in a hash table. Generate positions in the sequence until you hit one that's already in the hash table, or until the hash table is full (or until memory is exhausted if the hash table is not a fixed size).

I note that by a duplicate position, I'm talking about the state of the whole cube, and not just the 36 stickers you are using to determine the maneuver. You might very well get a duplicate 36-sticker state before you get an actual duplicate cube position. But that doesn't tell you much about how many positions can be ultimately reached. It's not sufficient to know only the 36 stickers in order to know what the next state will be, since some stickers on the top/bottom faces will generally move to the side faces.

 

[galvao]

If I am understanding you correctly, you are defining a way of generating a sequence of cube positions. For each cube position, you derive a maneuver based on the colors of 36 stickers at given locations on the cube. Then you perform that maneuver to arrive at the next cube position in the sequence.

That's it, bro!

So generally the set of all the positions in the cycle will be smaller than the full set of positions reached, unless the first duplicate happens to be a duplicate of the initial position

It would be beautiful if my idea could generate a cycle and come back to a solved state *I'm puking rainbows*, but that's highly improbable. I started thinking more far... (by example, doing similar processes with other faces/numbers of faces).

Most likely, it would probably take a huge number of moves before you reach a duplicate. It might not even be feasible to determine the cycle by computer simulation.

T_T (well, I thought it would take a lot of work to solve that, but I had no idea that it could not be feasible to determine)

I note that by a duplicate position, I'm talking about the state of the whole cube, and not just the 36 stickers you are using to determine the maneuver.

That's right.

 

[cuBerBruce]

I think one can expect it to take a few billion iterations before hitting a duplicate. You could store only every 1000th position or every 1 millionth position in the hash table to reduce the size of the hash table. This will allow you to get the size of the cycle (but not the exact starting point) without needing a really large hash table. It may still take quite a bit of time to calculate many billions of moves on the cube. But it may be within reach if efficiently coded.

EDIT: Assuming that 36 (an even number) quarter turns are applied for each position in the sequence, only even positions can be reached. So the orbit of reachable cube positions has an upper bound of 21,454,366,703,616,000 elements.