Scramble Amounts

[akatami]

How many possible scrambles are there of a 3x3? I need to prove this for my friend, so if you can find official documentation on that, I would be very happy

 

[Simkiss93]

Wikipedia tells me 43,252,003,274,489,856,000 .... not that official, but the mathematics seems sound.

 

[Cride5]

It's pretty much the same question as: "How many states (other than the solved state) does the Rubik's cube have?". The Wikipedia source pointed out by Simkiss93 has the answer, as does our wiki

 

[joey]

It depends which scrambler you're using

 

[cmhardw]

Do you mean how many possible scrambling algorithms could be generated, or how many possible cube states can be generated with a 25 move scrambling algorithm?

I have another question too. Can a 25 move scrambling algorithm reach every possible cube state?



I too think these are interesting questions.

Chris

 

[CubeAddict420]

i agree

 

[Kirjava]

Can a 25 move scrambling algorithm reach every possible cube state?

Yes, but every position doesn't have an equal chance of being generated.

 

[Johannes91]

The number of different move sequences of a given length (with no cancellations) is pretty easy to calculate.

a(n) = b(n) + c(n)
b( 0 ) = 1
b(n+1) = 12*b(n) + 12*c(n)
c( 0 ) = 0
c(n+1) = 3*b(n)

Here a(n) is the number of all move sequences of length n,
b(n) is the number of move sequences of length n that end with two adjacent faceturns, and
c(n) is the number of move sequences of length n that end with two opposite faceturns.

Evaluating a(25) gives 108680036237373301177932840960.

Can a 25 move scrambling algorithm reach every possible cube state?

Using 25 moves you can reach at most 26 different positions.
Using the word algorithm that way makes me cringe. >_<
Rephrased, can every position be reached with exactly 25 moves from the solved state? This was discussed at the yahoo group and the answer is (of course) yes, but I can't think of or remember a nice proof. Don't feel like digging it up right now, either.

Edit: Ninja'd by Kirjava.

 

[Cride5]

I have another question too. Can a 25 move scrambling algorithm reach every possible cube state?

Well if the upper bound number of moves required to solve any state is indeed 22 moves, then theoretically yes. But whether an algorithm which applies 25 random face turns is likely to reach these hardest scrambles is another question. Certainly the chances of reaching these 22-move states by applying 25 random moves are going to be pretty remote!

For the other question of how many 25-move scramble algorithms can be created: The naive answer is \( 18^{25} \), since there are 18 possible moves at each step and 25 total steps. The problem is that a good 25-move scramble algorithm discounts scrambles which turn the same face twice consecutively. They will normally go a bit further to ensure that any part of the scramble is not directly proceeded by moves which invert it - effectively undoing the scramble moves which have just been done.

In my own implementation of a 25-move scrambler, the algorithm prevented any move to be proceeded by a move on the same face. After a move on a given face, only one more move was allowed on the same axis. For example, a U-turn could be followed by a D-turn, but then no more U or D turns would be permitted until another turn was made. Counting the number of scrambles this would allow:

First move: 18 possibilities
Second move: 15 possibilities
Subsequent moves: {if different axis 15 moves - 80% chance, if same axis 12 moves 20% chance}

So the total number of distinct scrambles for my 25-move scramble generator would be:

\( = 18 * 15 * (15*0.8 + 12*0.2)^{23} \)
\( = 18*15*14.4^{23} \)
\( \approx 1.18 * 10 ^ {29} \)

 

[cmhardw]

Can a 25 move scrambling algorithm reach every possible cube state?

Yes, but every position doesn't have an equal chance of being generated.

Can a 25 move scrambling algorithm reach every possible cube state?

Using 25 moves you can reach at most 26 different positions.
Using the word algorithm that way makes me cringe. >_<
Rephrased, can every position be reached with exactly 25 moves from the solved state? This was discussed at the yahoo group and the answer is (of course) yes, but I can't think of or remember a nice proof. Don't feel like digging it up right now, either.

I have another question too. Can a 25 move scrambling algorithm reach every possible cube state?

Well if the upper bound number of moves required to solve any state is indeed 22 moves, then theoretically yes. But whether an algorithm which applies 25 random face turns is likely to reach these hardest scrambles is another question. Certainly the chances of reaching these 22-move states by applying 25 random moves are going to be pretty remote!

It's not obvious to me that all possible cube states are reachable by using exactly 25 turns from the solved state, and Cride writes up my same concern in a very clear way. I will also try to find the discussion on the yahoo group, because if we proved it I'd be interested to know how it was done.

Chris

P.S. I thought it was proven that 21 turns or less suffice for bringing any scrambled state back to the solved state. Was I misinformed, or was the 21 turn proof discredited?

 

[Cride5]

It's not obvious to me that all possible cube states are reachable by using exactly 25 turns from the solved state, and Cride writes up my same concern in a very clear way. I will also try to find the discussion on the yahoo group, because if we proved it I'd be interested to know how it was done.

If you were allowed to use less than 25 moves as well as exactly 25 moves exactly, then the answer is a straightforward yes. But is every state reachable with exactly 25 moves? Well if you imagine an any optimal scramble, it will be less than 25 moves, so you would need to find a way to 'waste' moves. If there were no restrictions on those 25 moves, then you could simply do something like U U' to add two moves, or if the optimal scramble ends in something like F, then it could be altered to F2 F' to add one move. So any number of moves could be added to the end of the scramble in this way. Whether it is possible with the turn restrictions I discussed in my previous post, is a more complex question. What restrictions would you impose?

P.S. I thought it was proven that 21 turns or less suffice for bringing any scrambled state back to the solved state. Was I misinformed, or was the 21 turn proof discredited?

Oh, I thought the last proof was for 22, but I'm probably just not keeping up-to-date Do you have any links to stuff about the 21 move upper bound?


EDIT: Is this the yahoo group discussion Johannes was talking about? I also found this.

EDIT2: Should this thread maybe be moved to puzzle theory?

 

[cmhardw]

What restrictions would you impose?

I would impose the standard restrictions that all scrambling programs use. A face may not be turned twice in succession, and at most two turns are allowed along the same axis before you must switch to a new axis.

Chris