Rubik's 5x5x5 Cube

Factual Questions
1

I just recently bought a Rubik’s 5x5x5 cube, and am happily working out a solution for it. I know it’s going to take a while, though I do remember the general approach from experience with the classic 3x3x3.

But while that’s going on… I was trying to reckon how many different states this 5x5x5 monster has. The only web page I’ve found on the subject is this one, but I disagree with that author’s calculations. So let me present my calculation, and maybe someone can confirm which of us is right, if either of us is.

There are 8 corner cubies which can share each other’s places, making 8! positional arrangements. Each cubie can have 3 possible orientations, although there are only 7 degrees of freedom for the set as a whole, because the last cubie’s orientation is fixed by the other 7. So in total, the corner cubies make 8! x 3[sup]7[/sup] possibilities.

There are 24 side edge cubies which can share each other’s places, and each cubie has 2 possible orientations. Again though, the orientation of any one is fixed by all the others. Thus there are 24! x 2[sup]23[/sup] possibilities for this set of cubies.

There are 12 middle edge cubies, each of which has 2 possible orientations, and the same restriction on their collective orientations. Thus there are 12! x 2[sup]11[/sup] possibilities for this set.

There are 24 inside corner cubies (face cubies nearest the corners). These have no orientation that’s interesting, or even noticeable — unless perhaps I were to draw little marks on them to tell the difference, which I’m not going to do. Also, these cubies come in quartets of the same color, and I don’t care (and couldn’t tell) if any two same-colored cubies were swapped around. So, there are 24! positional arrangements, but every 4! of those arrangements really count as one. Thus, there are 24! / 4! possibilities for this set.

A very similar computation applies to the 24 inside edge cubies (face cubies between the face centers and the middle edges). There are 24! / 4! possibilities for this set.

The 6 face center cubies have no interesting individual orientations, and are also fixed relative to each other. In fact we can put these six into some permanent orientation in space (blue on the bottom, red on the left, etc.), letting all the other cubies move around them. This saves us from having to consider orientations of the cube as a whole, which aren’t significant anyway.

So then, I make the total number of states for the 5x5x5 Rubik’s cube to be the product of the boldface numbers above, which is about 2.328 x 10[sup]73[/sup]. (Which means I can confidently scratch Exhaustive Search off my list of candidate algorithms, if I’d had any doubt. Luckily there’s a backup plan.)

Now the other guy’s number is higher than mine by about an order of magnitude. Even that would seem to be an amazing coincidence of proximity. For example, I don’t know where he’s getting his factorials raised to powers. I don’t know where he’s getting most of what he’s saying, actually. If his approach is the proper way to go about it, someone’s going to have to explain it to me.

Well, no one has to explain anything to me of course, but I sure would be grateful.

2

I haven’t gone through any of the arguments in any detail, but the page you link to agrees with David Singmaster’s answer back in 1982 in his Cubic Circular newsletter.

3

First, when I multiply all your combinations together, I get
8!12!24![sup]3[/sup]2[sup]34[/sup]3[sup]7[/sup]/4![sup]2[/sup] ~= 3.009x10[sup]95[/sup].
But a couple of your calculations are wrong.

First, the side edge pieces have (as the link states) fixed orientation; once you know where one of these pieces is, you know which orientation it must have. (The two pieces along the same edge which look superficially the same are actually chiral and can’t be swapped without flipping their orientation. You can convince yourself of this by seeing where the piece can go under all primitive moves.) This erases your factor of 2[sup]23[/sup]. Second, your calculation for the inner corner and edge pieces uses 24!/4! where it should be using 24!/4![sup]6[/sup] – there are six sets of four indistinguishable groups. With these two changes your total becomes
8!12!24![sup]3[/sup]2[sup]11[/sup]3[sup]7[/sup]/4![sup]12[/sup].

These changes take care of the first four constraints listed in the link. The fifth one (“The permutation of corners and central edges is even”), which gives an extra factor of 1/2, is poorly worded. I’m not sure, but I think he means by “central edge” the “inside corner” piece. Here’s the idea: There are two types of “primitive moves” (moves of a single slice, not counting the central slice) which affect these types of pieces. Rotating an outer face (e.g., slice 1 or 5, counting the vertical slices left-to-right) permutes the corner positions in a 4-cycle, and also permutes the inside corners in a 4-cycle. Rotating an inner side slice (slice 2 or 4) permutes the inside corners in two 4-cycles. A 4-cycle is an odd permutation, but the product of two 4-cycles is even; so each of these moves is an even permutation on this subset of pieces. I have to think a little more about this final factor of 2, though.

4

I can defend my arithmetic there, if not my overall approach. The product I computed was (8! 3[sup]7[/sup]) (24! 2[sup]23[/sup]) (12! 2[sup]11[/sup]) (24!/4!) (24!/4!) — which is indeed about 2.328 x 10[sup]73[/sup]. (Well, it is unless Python 2.4 has a serious math bug in it anyway.)

The rest of your post pointed out some obvious mistakes I made — obvious to me now, that is. Thanks for the corrections, and I’ll look forward to your next post.

5

Hmm. I’ve checked my arithmetic in bc:


define f (x) {
  if (x <= 1) return (1);
  return (f(x-1) * x);
}

(f(8)*3^7)*(f(24)*2^23)*(f(12)*2^11)*(f(24)/f(4))*(f(24)/f(4))

and got the same result I had earlier gotten using Matlab (well, this time to full integer precision), 3x10[sup]95[/sup]. Can you check again (or post the Python code)?

6

This is tricky, because there may be configurations that are mathematically possible, but not mechanically achievable without dismantling and reassembling the cube - I remember from the 3x3x3 cube that you can’t rotate a single corner, or flip a single edge - or something like that - I know you’ve touched on this in your calculations, but I suspect there will be deeper, subtler limitations. I don’t have any idea how to set about finding them.

7

Yes, the counting is usually done by assuming that the allowable moves permute the different types of pieces almost-independently, and then trying to characterize all of the constraints. (Both of the constraints you give are correct; these are the first and third constraints listed in the OP’s link.)

Thinking more about the 3x3x3 case I now think my earlier idea of his fifth constraint was not quite right. The pieces to consider are the outer corners and the middle edge pieces, both of which are affected only by an outer-face rotation. Again, each such rotation acts as a 4-cycle on each subset, so the overall permutation on the set is even. (Thus “central edge” is the same as “middle edge,” a better translation than “inner corner.” I missed this constraint earlier.) This constraint, BTW, is also present in the 3x3x3; once the corners are solved, for example, the edge permutation is necessarily of even parity, even though odd-parity permutations of the edge pieces are possible when the corners are ignored. Although there is a similar constraint with the outer and inner corner pieces, as I showed above, I think this constraint is not relevant once the four inner corner pieces of each face are viewed as identical.

As to your more general question–do these relatively simple constraints fully specify the group?–the simplest way of showing this (if it’s true) would be to exhibit move sequences which generate the group. For the 3x3x3 (using this as an example because I actually know the relevant sequences) this is fairly trivial: There are two simple sequences of moves, both leaving the corners invariant, one performing a 3-cycle permutation of the edges and the other flipping two edges in place. These suffice to generate the claimed edge subgroup (of size 12! 2[sup]10[/sup]) for a given corner arrangement. Similarly there are simple sequences of moves which swap a pair of corners and which rotate a pair of corners in opposite directions, which generates the claimed corner subgroup. These two proofs translate directly to the 5x5x5 case. Completing the proof would require similar displays for the other three piece types.

8

A few more comments: First, I was able to find moves which generate the remaining subgroups of permutations (of the side edges, the inside corners, and the inside edges; for each of these the orientation is fixed, so we don’t need to consider that). So (unless I made a mistake) this completes the proof that the number given in the link is the correct value. The moves are based on the following four-move sequence M: right inner slice (slice 4, counting from left) up, top face right (CCW), right inner slice down, top face left (CW). By following the pieces around you can see that this acts as a 5-cycle on the inside corners, as a 5-cycle on the side edges, as a 3-cycle on the inside edges, and trivially on the corners and middle edges. So M[sup]5[/sup] acts trivially except on the inside edges, where it acts as a 3-cycle. A 3-cycle is even, so we can use it to generate arbitrary* (see comments below) elements of the A[sub]24[/sub] subgroup of the inside-edge permutations. But because of the indistinguishability of the four inside edges of each face, the group we’re interested in is not S[sub]24[/sub] but S[sub]24[/sub]/(S[sub]4[/sub])[sup]6[/sup]; so this is plenty to generate the full subgroup.

Now consider the 10-move sequence consisting of M, fourth-slice-from-top right, M[sup]-1[/sup], and fourth-slice-from-top left. Here we pull one of the inside-corner pieces out of its five-cycle and put another one back. The effect of this sequence is to give a 3-cycle on the inside corner pieces, with trivial action on all other sets. As above, this is enough to generate the full 24!/4![sup]6[/sup] permutations.

Since we can permute the inside edges and inside corners as desired, we can use these permutations to undo the effects of the single move slice-4-up on these two sets, giving a new move which acts as a 4-cycle on the side edges and trivially on all other sets. A 4-cycle is odd, so it suffices* (again, see below) to generate the full S[sub]24[/sub].
*OK, why can I just say that given a single cycle I can use it to generate the whole group? Clearly I need more than one 4-cycle to generate S[sub]24[/sub], for example. The idea is that for the Rubik’s Cube, the subgroups of permutations (on each subset of pieces of the same type) are not (at least, not usually) just subgroups of S[sub]N[/sub], but normal subgroups. If we have some move sequence M which acts as the permutation p(M) on a single piece subset X while acting trivially on all other piece types, then for any move sequence K, the move sequence M[sub]K[/sub]={K,M,K[sup]-1[/sup]} also acts trivially except on X. On X, M[sub]K[/sub] acts as a permutation conjugate to p(M). So if we can generate the full S[sub]N[/sub] (on X) by move sequences when we ignore the effect on other piece types, then we can generate all conjugates to p(M). Now S[sub]N[/sub], for large N (N>4), has only one nontrivial normal subgroup, A[sub]N[/sub]; so if we can generate a nontrivial permutation on X, with |X|>4, we must be able to generate at least A[sub]N[/sub]. If the nontrivial permutation has odd parity, then we can generate all of S[sub]N[/sub].

(The two move sequences I used above are both of the form “do A, do B, undo A, undo B”; this is called the commutator [A,B] of A and B. These are useful moves when solving the cube because the commutator tends to have a simpler permutation structure than either A or B; the “undo” part can undo whatever damage was caused in the first place, as long as the intervening moves didn’t mess with that part of the cube.)

9

Well crap, I had an off-by-one error in my factorial function. I hate it when that happens. Your result of 3 x 10[sup]95[/sup] is correct. (Well, a correct result for the wrong computation. But thanks for checking.)

So I’m convinced now: the number of states is about 3 x 10[sup]74[/sup].

Wasn’t I the pollyannish fool, thinking there were only a tenth of that? It’s the end of innocence for me.

10

Okay, so what’s the quotient of the 5x5x5 super group by the 5x5x5 magic group? For instance, in the 3x3x3 case it’s Z[sub]4[/sub][sup]6[/sup]/Z[sub]2[/sub].

11

I’m not sure I know the definitions of either of these. Is the “super group” the group of legal permutations on the cube when all piece orientations are taken into account, and the “magic group” this group with indistinguishable states identified? So then, the quotient group is the group of permutations mapping the solved cube to an indistinguishable state?

Assuming those definitions are approximately correct… I’d have to look more closely at the 3x3x3 generators to see what they do to the center orientations; I don’t know offhand how they act. For the inner edge and inner corner pieces, from my previous post I can at least generate independent A[sub]24[/sub] subgroups (in each case, without affecting the center orientations), so this would give at least (S[sub]4[/sub])[sup]6[/sup]/Z[sub]2[/sub] for each one, right?

I suspect that for the inner edges, at least, the Z[sub]2[/sub] goes away; there might just be one overall Z[sub]2[/sub] factor for the whole group.

12

Yes. They originated in the groups of the “magic cube” and the “super cube”, respectively. For the “normal” cube, the only “invisible” actions are rotations of the faces, where the only forbidden motion is a single quarter-turn of a face. Z[sub]4[/sub] for each face modulo a copy of Z[sub]2[/sub].

This is annoying without proper algebraic notation, or a board, or a physical cube to look at together. You assert that you can generate any even permutation of the inside edges and inside corners and that those two don’t restrict each other?

13

So the “magic cube” is the original 3x3x3 Rubik, and the “super cube” has pictures or something to break the centers’ symmetry?

Yes (if my scribbles are correct). Label the primitive moves x[sub]n[/sub], y[sub]n[/sub], z[sub]n[/sub], for n = -2, -1, 1, 2. n = ±2 are the outer faces, n = ±1 are the inner slices; x, y, z are (of course) the three axes (so that, for example, x[sub]n[/sub], is a rotation of the slice corresponding to the plane x=n, 90° ccw). The center slices remain fixed so that the center faces keep a fixed position (though not orientation). Consider the move M = z[sub]2[/sub][sup]-1[/sup] * x[sub]1[/sub][sup]-1[/sup] * z[sub]2[/sub] * x[sub]1[/sub] (I’m writing these as compositions acting right-to-left, but it doesn’t matter for the cycle analysis): right inner slice up, top face right, right inner slice down, top face left (x increases to the right, z increases upward). This gives a 5-cycle among the inside corners, another 5-cycle among the side edges, and a 3-cycle among the inside edges (it clearly acts trivially on the corners, middle edges, and center orientations). So M[sup]5[/sup] gives a 3-cycle among the inside edges and acts completely trivially otherwise. (The side edges, inside corners, and inside edges all have a single possible orientation, so we don’t have to worry about that.) By conjugation we should then be able to generate an arbitrary 3-cycle and then by composition all of A[sub]24[/sub] on the inside edges.

Now consider the move N = z[sub]-1[/sub][sup]-1[/sup] * M[sup]-1[/sup] * z[sub]-1[/sub] * M. The move z[sub]-1[/sub] only intersects with the pieces permuted by M in a single piece (the lower right inside corner on the front face, x=1, z=-1). So the commutator will only act nontrivially on the inside corners; it’s a commutator, so it’s an even permutation (it turns out to be another 3-cycle). So again we can generate A[sub]24[/sub] on the inside corners.

Does that make sense?

14

Yes. Originally, the super cube was made by simply etching a line from the center of a face cubie to one of the edge cubies. There are ones out there with actual designs now.

It seems to. I really wish I had my own 5x5x5 to play with. Anyhow, one thing I’d be careful about is that there aren’t extra positions to get. Your solution is remarkably similar to Jeff Adams’ solution by commutators, but the commutator subgroup of the 3x3x3 magic group is of order 2 (or maybe 4) in the full group, so there might be an extra twist sitting around to be done.

15

They are still available ($30 from www.rubiks.com). The challenge with the 3x3x3 was to solve the thing without taking it apart, but after playing with the 5x5x5 I would say that the challenge is to solve it without it falling apart. You might be better off with a simulation. I’ve started writing one up in Mathematica; currently it does the position permutations (so it can verify my move sequences above) but not the orientation permutations (so it can’t help with any moves that modify orientable pieces).

Yes, I was not asserting that I’ve found the full kernel group (I’m going to call it that here so I don’t have to say “the quotient of the super group by the magic group” any more), merely that it’s at least that large. One or both of the 1/Z[sub]2[/sub] factors may go away; and earlier I thought (as I noted above) that the factor for the inside edges did go away. But now I don’t think it does; I think that the even permutations generate the whole kernel group. Here’s why:

Here’s a table of the effects of the primitive moves:




positions:     IE      IC      ME      SE       C
---------------------------------------------------
outer slice    (4)     (4)     (4)  (4)(4)     (4)
inner slice    (4)  (4)(4)      -      (4)      -
orientations:  ME(mod 2)  C(mod 3)   O(mod 4)
----------------------------------------------
outer slice     0         0          1
inner slice     0         0          0

Here the piece classes are abbreviated:
IE: inside edge
IC: inside corner
ME: middle edge
SE: side edge
** C**: outside corner
** O**: center
The notation (4) in the position table indicates a 4-cycle; for example, an inner-slice move acts by a product of two (disjoint) 4-cycles on the inside-corner pieces. The numbers in the orientation table are the sums of their orientation changes (listing only the orientable pieces, modulo their order). (For example, depending on the way you’ve defined your orientation, an outer-slice rotation may flip 0, 2, or 4 middle edges; since the middle edges have 2 orientations these all give zero “net orientation change.” This is one way of showing that you can’t flip a single edge or rotate a single corner.)

Only the outer-slice moves affect the C and ME pieces. Each such move acts by an odd permutation, and these pieces are all distinct, so each element of the kernel must have an even number of outer-slice moves. (Because each outer-slice move changes the summed center orientations by 1 (mod 4), this tells us that the possible center orientations in the kernel are at most (Z[sub]4[/sub])[sup]6[/sup]/Z[sub]2[/sub], the result you gave earlier.) Now each inner-slice move acts by an odd permutation on the SE pieces, and these pieces (despite appearances) are also all distinct, so each element of the kernel must also have an even number of inner-slice moves. Thus each element of the kernel acts as an even permutation of the positions among all piece classes.

It’s too bad. I was hoping for the Z[sub]2[/sub] factors to all congeal into a single overall Z[sub]2[/sub]; is there a mistake in my argument somewhere?
I’m not familiar with Jeff Adams’ solution. The group generated by the “primitive moves” (inner and outer slice rotations) leaves the centers in fixed positions, so its commutator subgroup will have trivial center rotations, right (each inverse move undoes the original move’s center rotations, since the rotation groups are abelian)? What moves does he consider, to get nontrivial commutator subgroups?

16

As an aside, is there a methodical way to take any cube, with any number of twists made to jumble the squares round and solve the puzzle? There’s a book on solving the cube from the 80s lying around the house somewhere, but on flicking through it I noticed it relied on you taking apart the cube and starting with the squares in a certain way already :dubious:

17

Of course there are methodical methods for solving the Cube. I suspect that the book that you have does not actually advocate disassembling the cube as a method of solving it, but rather as a method for learning how to solve it. By assembling the cube in various interesting puzzle configurations, one could be brought to understand how the different combinations of moves affect different pieces. Once one understands this, one can solve any scrambled cube without disassembling it.

Omphaloskeptic, it sounds like you’re trying to simulate the cube as a stack of 125 three-dimensional cubelets. It might be simpler to consider only the surface of the cube, effectively as a single solid block covered with 6*25 stickers. A move would then take off some subset of the stickers, re-arrange them appropriately, then stick them back on. I once used this approach for a standard 3[sup]3[/sup] cube, and it was much simpler than trying to track the orientation of cubelets. The downside, of course, is that it makes it much harder to program in a solver.

18

Actually, if we want a simpler term we may as well just call it the isotropy group.

There’s a poster around with his solution. I learned it from himself, so…

Anyhow, your solution seems to also be by commutators, which is why I brought it up. Basically, if the group of moves is G, then the moves you’re talking about using to act on the set of inside corners and inside edges can only generate [G,G]. Now, if your full solution uses a different technique, that changes things…

19

Not only are there solutions (one of which we’re discussing), but there are a very large number of them.

20

Well, 98, actually; I only care about the visible ones. I wrote the first version mainly to deal with the three fixed-orientation cubelet classes, so I didn’t concern myself with the orientations. It’s not really any harder to deal with the orientations, just a bit tedious. I’ve mostly finished it now.

Yes, in post #13, where I used the commutators (I do know what the commutator subgroup is), I used an explicit construction to find a subgroup --possibly a proper subgroup-- of the isotropy group; I was not claiming that these moves generated the whole group (I guess I didn’t make that clear). The construction generated two independent factors of A[sub]24[/sub], on the inside corners and the inside edges, though; so we know that we can generate all even permutations, and the action of the isotropy group (on each of IC and IE) contains (S[sub]4[/sub])[sup]6[/sup]/Z[sub]2[/sub]. (We know that the group action on each of these subsets is a subgroup of (S[sub]4[/sub])[sup]6[/sup], though, so each must be either (S[sub]4[/sub])[sup]6[/sup]/Z[sub]2[/sub] or (S[sub]4[/sub])[sup]6[/sup].)

In my next post, #15, I claim that the group actions contain no other elements, so that the entire isotropy group (using your quoted result without verification) is ((Z[sub]4[/sub])[sup]6[/sup]/Z[sub]2[/sub])x((S[sub]4[/sub])[sup]6[/sup]/Z[sub]2[/sub])x((S[sub]4[/sub])[sup]6[/sup]/Z[sub]2[/sub]). But #15 uses a parity argument (any opinions on its validity?) to show that the action of the isotropy group (on IC and independently on IE) contains only even permutations. This means that the group action, in each case, is contained in A[sub]24[/sub].