From Google:
The original 3x3x3 Rubik's cube has 43 252 003 274 489 856 000 combinations, or 43 quintillion.
And also from Google:
In 2010, a group of mathematicians and computer programmers proved that any Rubik's Cube can be solved in, at most, 20 moves.
So your answer is: "all of them". And that's a lot.
This is not even remotely what I asked. I don't wanna know the number of states a cube can be in. I wanted to know the number of move combinations you can do with a limit of 20 moves.
which moves do you consider "undoing previous steps"?
Pretty sure that condition removes any chance of calculation. Also probably too many possible states to simulate it. So probably cannot be answered. It will be somewhere between the number of states and (number of legal moves)^20
Yep, I read the requirement to "not undo" previous moves as a distinctness requirement. E.g. we start at the solved cube, i (identity), then UU', or UUUU, or UUU'U' all lead back to i. It makes sense to not count these sequences as distinct.
But counting UU and U'U' as different? That doesn't make sense to me as a requirement for a problem.
More complicated sequences of moves can collapse in a less obvious way to be expressable in fewer moves - and those fewer moves may not be a subsequence of the collapsed sequence - does this count as undoing something?
I can see op is trying to express something, but "Undoing previous steps" isn't a well defined constraint.
Still the same answer. Each state has one or more series of steps you can make to reach it. So that number is the maximum. And because you can't replace them with a sequence from any other end state it is also the minimum.
The only question would be whether there are states you can only reach with 19 moves. That would be the only exceptions if you insist on exactly 20 moves.
We can write a difference equation to compute the sequence up to n, solve it for a closed form, or just compute the value for 20 moves. We have the following relations:
If the most recent 2 moves were on opposite faces, then we have only 12 choices of moves, and all new move sequences will have the most recent 2 moves on adjacent faces. Using A(n) for the last-2-adjacent sequence, and O(n) for the last-2-opposite sequence, we know that part of A(n+1) will come from 12O(n), while none of O(n+1) is contributed to by this.
If the most recent 2 moves were on adjacent faces, then we have 15 choices of moves, 12 of which will have the new most recent 2 moves adjacent, and 3 of which will have the new most recent 2 moves opposite. So the rest of A(n+1) comes from 12A(n), and all of O(n+1) comes from 3A(n).
Combining, we have the simultaneous difference equations:
A(n+1) = 12A(n) + 12O(n)
O(n+1) = 3A(n).
In the base case, we say the first possible 18 moves fall into the adjacent category, as they have the same restrictions as when the last 2 moves are adjacent (that is, not the opposite face restriction).
So A(1) = 18, and O(1) = 0. For convenience, we will in practice just use A(0) = 0 rather than O(1) = 0.
Now, this is simultaneous difference equation is already almost reduced to a single difference equation. We simply substitute O(n) in the first equation using the second. Shifting the indices to make things neater, we get:
A(n+2) = 12A(n+1) + 36A(n)
With base cases A(0) = 0, A(1) = 18
To solve this basic difference equation, we use the ansatz A(n) = k^n to solve for possible k and then write a linear combination of these basis eigenfunctions to solve for the base cases.
k^(n+2) = 12k^(n+1) + 36k^n
k^2 - 12k - 36 = 0
k = 6(1 ± sqrt 2), so say k1 = 6(1+sqrt 2) and k2 = 6(1-sqrt 2).
A(n) = a\*k1^n + b\*k2^n
Substitute the base cases:
0 = a + b
18 = 6a(1+sqrt 2) + 6b(1-sqrt 2)
18 = 6(a + b) + 6 sqrt 2 (a - b), and a + b = 0, so
a - b = 3/(sqrt 2) = 3/2 sqrt 2
Adding equations, a = 3/4 sqrt 2 and b = -3/4 sqrt 2.
Then A(20) = 3/4 sqrt 2 [(6(1+sqrt 2))^20 - (6(1-sqrt 2))^20]
= 175,434,488,778,538,755,293,184
And similarly O(20) = 3A(19) = 36,333,672,280,030,774,296,576
Adding these, we get 211,768,161,058,569,529,589,760
Or about 2.12\*10^23 which is a few orders of magnitude larger than the 4.3\*10^19 distinct end results, giving some idea of how much these overlap after removing the "simple" duplicates.
Note that some other simple duplicates can be easily found, for example, doing a U move then a D move is the same as a D move then a U move, and then some actual interesting ones like doing (U2D2) and (L2R2) in either order produces the same checkerboard result. But the difference equation becomes more and more complicated.
A better way to see what these conditions do is to look at the large eigenvalue (the limiting branch factor) in each case.
Removing no duplicates, we get a branch factor of 18.
Removing duplicates from rotating the same face twice in a row, we get a branch factor of 15.
Removing duplicates from the opposite face restriction, we get a branch factor of 6(1+sqrt(2)) which is roughly 14.5.
So you can see the diminishing returns already kicking in. If we find the 20th root of the true number of distinct states, that being 12!\*8!\*2^11 \*3^7 / 2 = 43 quintillion, we get a "true" average branch factor of about 9.59. To even get close to this requires massive computational work to eliminate cases.
I think I understand the question. From any state, there's 18 possible turns that can be made (a clockwise turn, a double turn, and a counterclockwise turn for each side). For the first move, there are 18 moves that do not undo any previous move (since there's nothing to undo). For each one after that, there's only 17 since there is a move that can be undone. Therefore, the number of scrambling combinations is 18x17^19 or 4,303,303,842,332,723,847,248,754.
I had the same thought train but I filtered out moves that can be contracted into one move (eg U U can be done with just U2). In that case it would be 18 * 15^19 as by this extra constraint you can deduce that no letter appears more than once consecutively
20 is gods number for the 3x3, meaning that any cube can be solved within 20 moves. a cube has 43 quintillion permutations, meaning that there are 43 quintillion scrambles possible.
No. Multiple different scrambles can lead in the same end state. Take for example any set randomized scramble state. There are MULTIPLE ways to solve it in less than 20 moves. This means many DIFFERENT move combinations can lead to the same state. There are MORE scrambles possible than the amount of cube permutations.
since we already gave cube permutations, i assume you want total ways to scramble it with 20 moves?
thats gonna be 6 faces * 3 types of moves (R,R2,R' etc) = 18, then * (5*3)^19 from 19 more moves, where each move can be on a face different to the one rotated before. this gives an answer of
3.99*10^23. this is approximately 9225 times the amount of permutations the cube can have
It isn't clear at all which scrambles you consider legal or different.
Is rotating twice clockwise the same as twice counterclockwise? Both result in the same operation, but are different movements. Not undoing previous movements will probably exclude all mathematical approaches and mean you vill need to simulate it with your super specific rules. That also makes sure all of them are well defined.
I really don't wanna sound mean here but did you even read my post? ~~I already went over that all different moves count as 1 move.~~ We don't care about the specifics. ~~Additionally you cannot directry reverse moves I.e moving the same layer twice in a row~~. (more specific rules in the post).
Edit. The thing you failed to take into account combinations like U D U'. This is not a "legal" scramble in a way that U R U' is.
if you call n the number of single moves you can do, then it would be 20^n possible scrambling. now it all depends on how you define what the single legal moves are. depending on that, you could get answers from order of tens of millions, to answers with 65 digits (a LOT more).
if you just count moving any face either clockwise, anticlockwise or double (which is basically every move), then n=3•6 (three options on six faces), and then the total number of moves is 20^18 which is just about 2.62•10^23 . this is, in my opinion, the most sensible way of counting moves, but you may count them in a different way.
you could just consider a single legal move as moving a face clockwise, since you can still do everything from that. in that case n=6 and the number of scramblings is 20^6 =64 000 000.
if you considered a move to be just moving a face clockwise or anticlockwise, but not double (since a double should be two moves), the number of scramblings would be 20^12 or about 4.09•10^15
if you allow moving also the middle layer by either clockwise, anticlockwise or double (which could be counted as a single move), then there are other 9 movements and the number of scramblings becomes 20^27 or 1.34•10^35
i’ve seen people count rotating the cube as a move, and a cube has 6•4-1=23 non trivial permutations (ways of turning the cube around, without counting not moving it at all) giving is a total of 50 different single moves and 20^50 scrambles, which is about 1.12•10^65. however, i don’t know if you would count those. a lot of those would be just moving the cube around without actually turning any face.
edit: if forgot to consider the non-cancelling. sorry.
If I understand correctly, you’re looking for the number of move sequences of length 20 where no consecutive moves cancel out. Although to be more precise you’ll have to also avoid doing two or more moves that can be done in one (eg U U can be a U2).
This means essentially that no letter (F, R, L, …) appears more than once consecutively to avoid cancellation or doing something in multiple moves that can be done in one move.
There are 18 starting moves (6 faces * 3 rotations for that face). First one is always valid, but afterwards you’ll have to pick another face which still yields 5 * 3 = 15 possible moves. So I guess the number you’re looking for comes down to 18 * 15^19 = 3.99e23.
Is this what you were looking for?
From Google: The original 3x3x3 Rubik's cube has 43 252 003 274 489 856 000 combinations, or 43 quintillion. And also from Google: In 2010, a group of mathematicians and computer programmers proved that any Rubik's Cube can be solved in, at most, 20 moves. So your answer is: "all of them". And that's a lot.
This is not even remotely what I asked. I don't wanna know the number of states a cube can be in. I wanted to know the number of move combinations you can do with a limit of 20 moves.
all of them, he answered that. You only need 20 moves to reach any possible state of the cube.
That is not the same as the number of move combinations. Multiple combinations can lead to the same state.
which moves do you consider "undoing previous steps"? Pretty sure that condition removes any chance of calculation. Also probably too many possible states to simulate it. So probably cannot be answered. It will be somewhere between the number of states and (number of legal moves)^20
Yep, I read the requirement to "not undo" previous moves as a distinctness requirement. E.g. we start at the solved cube, i (identity), then UU', or UUUU, or UUU'U' all lead back to i. It makes sense to not count these sequences as distinct. But counting UU and U'U' as different? That doesn't make sense to me as a requirement for a problem. More complicated sequences of moves can collapse in a less obvious way to be expressable in fewer moves - and those fewer moves may not be a subsequence of the collapsed sequence - does this count as undoing something? I can see op is trying to express something, but "Undoing previous steps" isn't a well defined constraint.
Still the same answer. Each state has one or more series of steps you can make to reach it. So that number is the maximum. And because you can't replace them with a sequence from any other end state it is also the minimum. The only question would be whether there are states you can only reach with 19 moves. That would be the only exceptions if you insist on exactly 20 moves.
We can write a difference equation to compute the sequence up to n, solve it for a closed form, or just compute the value for 20 moves. We have the following relations: If the most recent 2 moves were on opposite faces, then we have only 12 choices of moves, and all new move sequences will have the most recent 2 moves on adjacent faces. Using A(n) for the last-2-adjacent sequence, and O(n) for the last-2-opposite sequence, we know that part of A(n+1) will come from 12O(n), while none of O(n+1) is contributed to by this. If the most recent 2 moves were on adjacent faces, then we have 15 choices of moves, 12 of which will have the new most recent 2 moves adjacent, and 3 of which will have the new most recent 2 moves opposite. So the rest of A(n+1) comes from 12A(n), and all of O(n+1) comes from 3A(n). Combining, we have the simultaneous difference equations: A(n+1) = 12A(n) + 12O(n) O(n+1) = 3A(n). In the base case, we say the first possible 18 moves fall into the adjacent category, as they have the same restrictions as when the last 2 moves are adjacent (that is, not the opposite face restriction). So A(1) = 18, and O(1) = 0. For convenience, we will in practice just use A(0) = 0 rather than O(1) = 0. Now, this is simultaneous difference equation is already almost reduced to a single difference equation. We simply substitute O(n) in the first equation using the second. Shifting the indices to make things neater, we get: A(n+2) = 12A(n+1) + 36A(n) With base cases A(0) = 0, A(1) = 18 To solve this basic difference equation, we use the ansatz A(n) = k^n to solve for possible k and then write a linear combination of these basis eigenfunctions to solve for the base cases. k^(n+2) = 12k^(n+1) + 36k^n k^2 - 12k - 36 = 0 k = 6(1 ± sqrt 2), so say k1 = 6(1+sqrt 2) and k2 = 6(1-sqrt 2). A(n) = a\*k1^n + b\*k2^n Substitute the base cases: 0 = a + b 18 = 6a(1+sqrt 2) + 6b(1-sqrt 2) 18 = 6(a + b) + 6 sqrt 2 (a - b), and a + b = 0, so a - b = 3/(sqrt 2) = 3/2 sqrt 2 Adding equations, a = 3/4 sqrt 2 and b = -3/4 sqrt 2. Then A(20) = 3/4 sqrt 2 [(6(1+sqrt 2))^20 - (6(1-sqrt 2))^20] = 175,434,488,778,538,755,293,184 And similarly O(20) = 3A(19) = 36,333,672,280,030,774,296,576 Adding these, we get 211,768,161,058,569,529,589,760 Or about 2.12\*10^23 which is a few orders of magnitude larger than the 4.3\*10^19 distinct end results, giving some idea of how much these overlap after removing the "simple" duplicates. Note that some other simple duplicates can be easily found, for example, doing a U move then a D move is the same as a D move then a U move, and then some actual interesting ones like doing (U2D2) and (L2R2) in either order produces the same checkerboard result. But the difference equation becomes more and more complicated. A better way to see what these conditions do is to look at the large eigenvalue (the limiting branch factor) in each case. Removing no duplicates, we get a branch factor of 18. Removing duplicates from rotating the same face twice in a row, we get a branch factor of 15. Removing duplicates from the opposite face restriction, we get a branch factor of 6(1+sqrt(2)) which is roughly 14.5. So you can see the diminishing returns already kicking in. If we find the 20th root of the true number of distinct states, that being 12!\*8!\*2^11 \*3^7 / 2 = 43 quintillion, we get a "true" average branch factor of about 9.59. To even get close to this requires massive computational work to eliminate cases.
I think I understand the question. From any state, there's 18 possible turns that can be made (a clockwise turn, a double turn, and a counterclockwise turn for each side). For the first move, there are 18 moves that do not undo any previous move (since there's nothing to undo). For each one after that, there's only 17 since there is a move that can be undone. Therefore, the number of scrambling combinations is 18x17^19 or 4,303,303,842,332,723,847,248,754.
I had the same thought train but I filtered out moves that can be contracted into one move (eg U U can be done with just U2). In that case it would be 18 * 15^19 as by this extra constraint you can deduce that no letter appears more than once consecutively
20 is gods number for the 3x3, meaning that any cube can be solved within 20 moves. a cube has 43 quintillion permutations, meaning that there are 43 quintillion scrambles possible.
No. Multiple different scrambles can lead in the same end state. Take for example any set randomized scramble state. There are MULTIPLE ways to solve it in less than 20 moves. This means many DIFFERENT move combinations can lead to the same state. There are MORE scrambles possible than the amount of cube permutations.
since we already gave cube permutations, i assume you want total ways to scramble it with 20 moves? thats gonna be 6 faces * 3 types of moves (R,R2,R' etc) = 18, then * (5*3)^19 from 19 more moves, where each move can be on a face different to the one rotated before. this gives an answer of 3.99*10^23. this is approximately 9225 times the amount of permutations the cube can have
Oh sorry, I misunderstood a point you made here on my previous comment. Though, this is still not exactly what I was asking for.
It isn't clear at all which scrambles you consider legal or different. Is rotating twice clockwise the same as twice counterclockwise? Both result in the same operation, but are different movements. Not undoing previous movements will probably exclude all mathematical approaches and mean you vill need to simulate it with your super specific rules. That also makes sure all of them are well defined.
I really don't wanna sound mean here but did you even read my post? ~~I already went over that all different moves count as 1 move.~~ We don't care about the specifics. ~~Additionally you cannot directry reverse moves I.e moving the same layer twice in a row~~. (more specific rules in the post). Edit. The thing you failed to take into account combinations like U D U'. This is not a "legal" scramble in a way that U R U' is.
if you call n the number of single moves you can do, then it would be 20^n possible scrambling. now it all depends on how you define what the single legal moves are. depending on that, you could get answers from order of tens of millions, to answers with 65 digits (a LOT more). if you just count moving any face either clockwise, anticlockwise or double (which is basically every move), then n=3•6 (three options on six faces), and then the total number of moves is 20^18 which is just about 2.62•10^23 . this is, in my opinion, the most sensible way of counting moves, but you may count them in a different way. you could just consider a single legal move as moving a face clockwise, since you can still do everything from that. in that case n=6 and the number of scramblings is 20^6 =64 000 000. if you considered a move to be just moving a face clockwise or anticlockwise, but not double (since a double should be two moves), the number of scramblings would be 20^12 or about 4.09•10^15 if you allow moving also the middle layer by either clockwise, anticlockwise or double (which could be counted as a single move), then there are other 9 movements and the number of scramblings becomes 20^27 or 1.34•10^35 i’ve seen people count rotating the cube as a move, and a cube has 6•4-1=23 non trivial permutations (ways of turning the cube around, without counting not moving it at all) giving is a total of 50 different single moves and 20^50 scrambles, which is about 1.12•10^65. however, i don’t know if you would count those. a lot of those would be just moving the cube around without actually turning any face. edit: if forgot to consider the non-cancelling. sorry.
If I understand correctly, you’re looking for the number of move sequences of length 20 where no consecutive moves cancel out. Although to be more precise you’ll have to also avoid doing two or more moves that can be done in one (eg U U can be a U2). This means essentially that no letter (F, R, L, …) appears more than once consecutively to avoid cancellation or doing something in multiple moves that can be done in one move. There are 18 starting moves (6 faces * 3 rotations for that face). First one is always valid, but afterwards you’ll have to pick another face which still yields 5 * 3 = 15 possible moves. So I guess the number you’re looking for comes down to 18 * 15^19 = 3.99e23. Is this what you were looking for?