To: CubeLovers
Subject: A essay on the NxNxN Cube : counting positions and solving it
BCC: mahoney
text follows this line
Thoughts on the NxNxN Cube

Lately I've seen a few comments here on the NxNxN cube, how to build
one, and how what an algorithm to solve one might look like. I have
no idea how the inside mechanics should work, nor have I made
significant progress thinking about how to find God's Algorithm for
these guys, but I did work out a recipe for solving the NxNxN, way
back in 1981, and worked out the number of possible positions.
Perhaps given those questions this is the right time to post a synopsis.
My approach is rather pedestrian, and I wave my hands quite a lot,
but I'm confident that an an arbitrarily large cube can be
unscrambled with the method I describe below.
But first, since this is the first time I've posted to this discussion
group, I guess I should say who I am. I wrote my undergraduate thesis
on Rubik's Cube fifteen years ago, as part of a math/physics degree.
Ironically, even though I was at MIT and this mailing list is based
there, too, I never knew of it until this year, when I started
(slowly) reading through the archives of this mailing list. There's a
lot there, and not all of it is exactly quick reading.
These days I teach physics and astronomy at Marlboro College, where I
have occasionally taught an "ideas of group theory" course based on
puzzles like TopSpin and Rubik's Cube, designed to show mostly
nonmath majors why group theory is so pretty. I see from previous
posts that other people have taught similar courses.
Anyway, what follows is one way of thinking about the NxNxN. Much of
this isn't new, but perhaps it hasn't been said quite this way, and
will therefore be worth saying. Hope it isn't too longwinded, and
that I don't offend the folks who've posted similar things already by
not referencing them; as I said, I've swallowed some but not all of
the 1500 or so posts to this mailing list.
======================================================================
(I) The Cube Itself =================================================
======================================================================
First, I will envision the NxNxN Cube (the whole thing) as a solid,
transparent array of N^3 cubies (the pieces its made of), most of
which are 'hidden' on the inside. (For example, this would imply that
the the 3x3x3 cube has a single hidden cubie at the center.) All the
real mechanical 3x3x3, 4x4x4, 5x5x5 Cubes that I've seen only have
cubies on the outside, but if you can put back all N^3 cubies in the
one I'm describing then you can certainly do the real ones.
(In Dan Hoey's notation, I believe that this means I treat the Cube as
the G+C group, where G is generated by the outer slice rotations, and
C is the rotations of the entire thing. I am not including spatial
inversions, because I'm physicall obtainable positions here. And
while I agree that G is what I see on the 3x3x3, I think that what I
describe here is a more general and elegant approach to the NxNxN.)
Second, let a 'move' be a rotation of any plane of cubies, including
the interior slices. There are 3N of these planes, and each has NxN
cubies in it. Since I'm not going to try to count moves here, it
doesn't matter whether you consider a half turn as one move or two
quarter turns. The slices are numbered from 1 to N, so that rotating
the 1slice or Nslice is a rotation of an outside face, while the
(N+1)/2 slice is through the center of an odd Cube. (I chose this
convention rather than numbering at zero in the center because it lets
me talk about the N'thlayer, as defined below, and the N'thslice in
the same breath without getting myself confused.)
Third, I imagine that each of face of each cubie has a distinct color,
which I will take as usual to be (Front, Back, Up, Down, Left, Right),
and that the unique 'solved' position has all N^3 cubies in the same
orientation, with their colors all aligned.
======================================================================
(II) Layers, Orbits, and Types =====================================
======================================================================
Now I would like to see how many different kinds of cubies there are,
where they live, and how they behave.
The first thing to notice is that there are two distinct kinds of
NxNxN Cubes, depending on whether N is even or odd. For N odd, there
is a single cubie at the center (which I will call the 1layer),
surrounded by the cubies on the outside of the 3x3x3 (which I will
call the 3layer), which in turn are surrounded by those cubies on the
outside of the 5x5x5 Cube (the 5layer), and so on until I reach the
outermost Nlayer. When N is even, the innermost layer is 2x2x2,
which is surrounded by a 4x4x4 "4layer", and so on. Thus the entire
Cube is made up of disjoint layers which are either all odd or all
even. Moreover, it is easy to see that the cubies on a given layer
always stay on that layer; the allowed rotations cycle cubies within a
layer but never between layers.
Next, I will define any complete set of cubies that can move into each
other's position as an "orbit." (This name is at least suggestive of
the group theory notion of a closed sequence of elements.) For
example, the 8 corner cubies on the 3x3x3 Cube form one orbit since
any one of those cubies can be put in any of those eight positions.
Likewise, the 12 edge cubies on the 3x3x3 form another orbit.
Finally, distinct orbits which have similar properties will be called
members of the same "type." For example, the 4x4x4 Cube has an orbit
of eight outer corners on the 4layer, and a second orbit of eight
corner cubies on the inside, in the 2layer. Although these sets
of cubies are in distinct orbits, they are both "Corner" types.
(I know that my notion of what exactly "similar properties" means
is vague here, but I think the general idea is clear.)
One approach to solving the cube, then, is to identify each kind of
type  it turns out there aren't very many  and find some method of
manipulating the cubies in an orbit of that type without disturbing
any other the rest of the Cube. I'll explain one way to do this
further down, after listing the different types.
======================================================================
(III) The Eight Types ==============================================
======================================================================
Without further ado, here they are.
Name What:
 
Central The unique cubie in the center of Cubes with N odd.
Corner Corners in each layer. In each layer there is
1 corner orbit consisting of 8 cubies, each of
which can be in 3 orientations in each of 8 positions.
(8 positions x 3 orientations = 24 total.)
However, while all 8! position rearrangements are
permissible, all rotations are not; as is well known,
only 1/3 of them are.
One way to see this is to define "twist" state
as (0,1,2) for each orientation of a cubie at a
corner, and to notice that the sum of all these states
isn't changed by a single move. This means that
you cannot turn just one corner in place.
EdgeSingle The ones like the outer edges on the 3x3x3.
In each odd layer there is 1 of these orbits,
consisting of 12 cubies, each of which can be in 2 states.
(12 positions x 2 orientations = 24 total.)
All 12! placements are accessible, but again only
some of the flips; you cannot turn just one edge.
FaceCenter The cubies like the centers of the 3x3x3 face.
In each odd layer there is on of these orbits,
which has 6 cubies each of which can be in 4 rotation
states. (12 places x 4 states each = 24 total.)
This time all rotations are possible; however, the
cubies can only move in space as a rigid whole, and
therefore there are 24 different positions
for these cubies, which are completely determined
by the orientation of the central cubie.
EdgeDouble,
FaceCorner,
FaceEdge,
FaceOffset
Each of these orbits consists of exactly 24 cubies,
as shown in the pictures below. There are in general
many of each of these orbits in each layer, as given by
the formulae (simple geometry and counting  see
the diagrams) in the table below.
*None* of these cubies in these orbits
can "flip" or "twist" in place like the Corners
and Single Edges do; in every case there are exactly
24 cubies which implies that there must be only
one orientation at each possible position. Another
way to see this is to draw in an orientation on
each cubie of a given orbit, with arrows, and then
show that no possible move changes the positions
of the arrows.
Here's a summary of the specs for each type. Note that the "number
of positions" given is for both only one parity, that is, for both an
even or odd number of quarter turns, and ignoring the all other
orbits. The number of positions of the whole Cube is *not* a simple
product of all these numbers; the parities of different orbits must
agree. More on this later.
As usual, I use "!" and "^" for factorial and "raisetothepowerof",
i.e. 8!=8*7*6*5*4*3*2*1 and 3^7=3*3*3*3*3*3*3.
 Types  ( n = which layer ) 
Name # of # of orbits per layer. # of positions per orbit
cubies (n odd) (n even) (both even/odd parity)
    
n=1
Central 1 1 0 24
n>1
Corner 8 1 1 (3^7) 8!
EdgeSingle 12 1 0 (2^11) 12!
FaceCenter 6 1 0 (4^6)
n>3
EdgeDouble 24 (n3)/2 (n2)/2 24!
FaceCorner 24 (n3)/2 (n2)/2 24!
FaceEdge 24 (n3)/2 0 24!
n>5
FaceOffset 24 (n3)(n5)/4 (n2)(n4)/4 24!

It's also convenient to define "h" and "H" such that
h = n/2 (n even); H = N/2 (N even)
h = (n1)/2 (n odd); H = (N1)/2 (N odd)
which makes the counting a bit easier. "h" stands for "half", and is
the number of the slice just before the center slice, if there is a
center slice. With this "h", the expressions for the number of orbits
per layer are much simpler, namely
Name # of orbits per layer
 
Double Edge h1
FaceCorner h1
FaceEdge h1
FaceOffset (h1)(h2)
And now for the pictures. This is much easier to visualize in 3D with
real drawings, but I'll do what I can with ASCII.
The smallest layer n that contains all the distinct types (except
the central cubie, of course) is n=7, so I've drawn in one outside
(n=7) plane of a 7x7x7 Cube below and sketched in where they live.
You can either think of this as the outermost layer of an N=7 Cube,
or part of an inner n=7 slice of a larger Cube.
The slices (rows and columns in the pictures) can be numbered either
left to right or right to left, so when I refer to the "nslice" I
also mean the "(N+1n)slice" where N=(size of entire Cube)=7 here,
and 1<=n<=N is a particular slice.
I also note to the right of each picture which slice rotations can
disturb the cubies in that orbit, and whether a quarter turn of that
kind of move gives an even or odd permutation of the cubies. ("even"
or "odd" refers to how many pairwise swaps it takes to get that
permutation. A cycle of 2 cubies is odd, a cycle of 3 cubies is even,
and a cycle of 4 cubies is odd. For example, it takes an even number
of moves to corner number 1 to corner 2's place, corner 2 to 3's
place, and corner 3 to 1's place.) These parities will be discussed
further in the next section.
Where there is more than one possible orbit I have used the labels "p"
and "q" to specify which one is shown. The letter "H" (described
above) is in this case (with N=7) H = (N1)/2 = 3.
7 6 5 4 3 2 1
1 2 3 4 5 6 7


7 1 C . . . . . C nCorner

6 2 . . . . . . . ( N >= n >= H )

5 3 . . . . . . . Moved By Parity
  
4 4 . . . . . . .
 nslice odd
3 5 . . . . . . .

2 6 . . . . . . .

1 7 C . . . . . C
1 2 3 4 5 6 7


1 . . . ES . . . nEdgeSingle

2 . . . . . . . ( N >= n >= H )

3 . . . . . . . Moved By Parity
  
4 ES . . . . . ES
 nslice odd
5 . . . . . . .
 (H+1)slice odd
6 . . . . . . .
 (Note that H+1 is the slice
7 . . . ES . . . through the center.)
1 2 3 4 5 6 7


1 . . . . . . . nFaceCenter

2 . . . . . . . Moved By Parity
  
3 . . . . . . . center (H+1)slice odd

4 . . . FC . . .
 Rotated By
5 . . . . . . . 
 nslice "odd"
6 . . . . . . .

7 . . . . . . .
1 2 3 4 5 6 7


1 . ED . . . ED . npEdgeDouble

2 ED . . . . . ED ( 1 < p <= H; p=2 shown here.)

3 . . . . . . . Moved By Parity
  
4 . . . . . . . nslice even (2 4cycles)
 pslice odd (1 4cycle)
5 . . . . . . .
 (The "pslice" referred to here
6 ED . . . . . ED and in the next figures cuts into the
 Cube in the 3rd dimension not shown
7 . ED . . . ED . into the paper. The "nslice" move
turns this diagram by 90 degrees.)
1 2 3 4 5 6 7


1 . . . . . . . npFaceCorner

2 . FC . . . FC . ( 1 < p <= H; p=2 shown here.)

3 . . . . . . . Moved By Parity
  
4 . . . . . . . nslice odd (4 cubies move)
 pslice even (8 cubies move)
5 . . . . . . .

6 . FC . . . FC .

7 . . . . . . .
1 2 3 4 5 6 7


1 . . . . . . . npFaceEdge

2 . . . FE . . . ( 1 < p <= H; p=2 shown here.)

3 . . . . . . . Moved By Parity
  
4 . FE . . . FE . nslice odd (4)
 pslice odd (4)
5 . . . . . . . (H+1)slice even (8)

6 . . . FE . . .

7 . . . . . . .
1 2 3 4 5 6 7


1 . . . . . . . npqFaceOffset

2 . . FO . x . . ( 1 < p <= H; p=2 shown here;
 1 < q <= H; q=3 shown here;
3 . x . . . FO . p not equal to q. )

4 . . . . . . . Moved By Parity
  
5 . FO . . . x . nslice odd
 pslice odd
6 . . x . FO . . qslice odd

7 . . . . . . . The x's are *not* part of this orbit,
but mark a distinct mirrorimage orbit.
There are no moves which will bring
one of the FO's to one of the x's.
Every cubie on any size NxNxN Cube fits one of these patterns.
For large values of N, nearly all the cubies are in FaceOffset orbits.
======================================================================
(IV) Parity and the Total Number of NxNxN Positions ==================
======================================================================
I'd guess most of you who read this will already understand parity
considerations, but let me run through it quickly anyway.
The basic idea is that any permutation of a group of symbols can be
broken into a sequential set of pair exchanges, and the number of
these pair exchanges, even or odd, determines the parity of the
permutation, even or odd. Thus if ABCDE is rearranged into BAECD,
then this rearrangement is odd because it requires three pair swaps,
and three is odd: (1) swap AB to BA in the original, (2) swap D and E
to get the D at the end, (3) swap the E and C. There are other swap
sequences, but all are odd.
Any slice rotation which cycles four cubies ABCD into BCDA puts those
cubies into an odd permutation since it would require three pair swaps
(AB, AC, AD) to change one into the other.
The point all this is that different orbits must have consistent
parities. The best known Cube example is that on the 3x3x3 cube, a
quarter turn of any outside slice changes the parity of *both* corners
and edges; therefore, positions which have the corners and edges in
different parities are impossible, and therefore one cannot exchange
two corners without exchanging two edges somewhere, too.
On the NxNxN things are a bit messier. Any given slice rotation will
change the parity of some orbits, and leave many others unchanged.
Most choices of arbitrary placements of cubies won't be a possible
cube position, not only because of the "twist" of the corners and
"flip" of the edges (described above briefly) but also because the
parity of all the orbits must be consistent.
Here's one way to do it.
Since each slice n>1 moves exactly one Corner orbit, and since the n=1
slice moves the Central cubie, I can use the N Corner/Central orbits
to *define* the parity of each slice. Then the parity of all other
orbits is fixed, and each has available exactly onehalf (only one
parity) of its total number of positions as given in the table
Another way of doing the same thing is to count the only one parity,
that is 1/2 of *all* the orbits, and then multiply by 2^N as the
number of ways to choose the parity on each of N slices.
So I can now calculate the total number of available positions T(N)
of the NxNxN cube by multiplying the number of possible positions of
each orbit, taking into account how many orbits there are in each
layer, over all N layers, and keeping the parity in agreement. (Note
that here I *am* including a rotation of the entire cube as a new
"position". To take out this factor, divide what follows by 24. Note
also that I'm distinguishing between different rotations of the face
centers, which is also a bit different from what is usually done.)
The counting is a pretty straightforward. Using the initials of the
types as abbreviations, the total number of each type of orbit is:
N odd:
#1 = 1
#C = (N1)/2
#ES = (N1)/2
#FC = (N1)/2
#ED = Sum n= (3, 5, 7, 9, ..., N) of { (n3)/2 } = (N1)(N3)/8
#FC = same as #ED
#FE = same as #ED
#FO = Sum n= (3, 5, 7, 9, ..., N) of { (n3)(n5)/4 }
= (N1)(N3)(N5)/24
N even:
#1 = 0
#C = N/2
#ES = 0
#FC = 0
#ED = Sum n= (2, 4, 6, 8, ..., N) of { (n2)/2 } = (N)(N2)/8
#FC = same as #ED
#FE = 0
#FO = Sum n= (2, 4, 6, 8, ..., N) of { (n2)(n4)/4 }
= (N)(N2)(N4)/24
And so

 T(N) = Total Positions of NxNxN cube, all orientations,
 all N^3 cubies

 = 2^N (24/2)^#1 (3^7 8!/2)^#C (2^11 12!/2)^#ES (4^6/2)^#FC
 * (24!/2)^(#ED+#FC+#FE+#FO)

which simplifies to either
T(N odd)= 24 [3^7 8! 2^10 12! 4^6/2]^((N1)/2) [24!/2]^( (N1)(N3)(N+4)/24 )
= 24 [ 8.85801e+22 ]^((N1)/2) [3.102242e+23]^((N1)(N3)(N+4)/24)
or
T(N even) = [3^7 8!]^(N/2) [24!/2]^( N(N2)(N+2)/24 )
= approx (8.817984e7)^N (3.102242e23)^(N(N2)(N+2)/24),
which is an awful lot of positions no matter how you look at it.
Note that usually the number of 3x3x3 positions is given without the
factor of 24 (spacial rotations) or the 4^6/2 (face center rotations),
which leaves (3^7 8! 2^10 12!) = 4.3e19.
For large N, T(N) is dominated by the (24!/2)^(N^3/24) term, which is
about 9.524^(N^3), which implies that for very big cubes, each of the
N^3 cubies acts as if it has about 9.5 'independent' places it can be.
(Oh, and the notation 1.23e+4 means 1.23 10^4 = 1230.)
=====================================================================
(V) Solving It =====================================================
=====================================================================
Here's where the handwaving really gets going. What I describe here
is closer to an outline of a method than a real algorithm, but you can
probably fill in the details yourself.
The basic idea is to use a generalpurpose idea for cycling three
cubies of any given orbit without disturbing any other part of the
Cube. A small variation on this same theme can be used to twist two
corners or single edges in the place, too.
If I can do this for every type, then all I have to do to solve the
whole cube is the following.
 An NxNxN Recipe 
(A) If N is odd, orient the Central cubie correctly, and
at the same time, turn each FaceCenter so that it is aligned
with the Central cubie. (If you can't see the orientations
of the FaceCenters, as is usually the case on the typical
3x3x3, then just skip that step and move on.)
(B) For each layer, examine the parity of corresponding
Corner orbit. If its parity is odd, make one
arbitrary 1/4 turn rotation on that layer; otherwise,
don't move it. At this point all the Corner orbits
have even parity, and therefore *all* the orbits have
even parity.
(C) And finally, I have these nested loops:
(i) Starting at the innermost layer and working outward,
(ii) on each orbit in that layer,
(iii) 1. Restore each cubie of that orbit to its proper position
with the 3cycle technique described below. Since
all the orbits already have even parity, these evenmove
combinations are enough to restore everything to their
proper places.
2. If the current orbit is a Corner or EdgeSingle,
then once the cubies are in the right places apply
the "twist" and "flip" operations described below
to orient them correctly.
That's it. Now all I have to do is describe three tricks,
(1) how to cycle three cubies on any given type,
(2) how to twist two corners in opposite directions, and
(3) how to flip two EdgeSingles,
all without disturbing anything else.
All these tricks are well known, I think. And there are certainly
many, many other tricks; however, these are the simplest that
I know of that can be generalized to any size Cube. Moreover,
they have the nice property that you can actually "think" your way
through them without actually needing to memorize a long sequence
of moves.
=====================================================================
(VI) How to Cycle Three Cubies =====================================
=====================================================================
The basic idea is to find a move sequence that will (1) take a chosen
cubie off from its "hot seat" on a chosen slice *without* (here's
the trick) disturbing any other cubie on that slice. The rest
of the cube can be completely scrambled by this operation. Then (2)
rotate the chosen slice, (3) undo step (1), putting the original
cubie back into its original slice and undo whatever changes were
made to the other cubies, and (4) undo step 2.
The sequence always of the form
A R A' R'
where "A" is step 1, "R" is a rotation of a single slice, and
the ' mark means, as usual, the inverse operation.
Here's a detailed example, using the Corner orbit of a 3x3x3 cube,
with the top layer as the "chosen slice" and the cubie marked "1" in
the unfolded sketch of a cube below as the focus of attention. In
eight moves the cubies in locations 1, 2, and 3 will trade places.
The starting position:
U
a  1  2  d  (a,1,2,d,e,3,g,h) are a Corner orbit.
 L  F  R  B
e  3  g  h  (U, D, L, R, F, B) are the possible
D clockwise rotations.
(1) Get "b" off the chosen slice, without disturbing any other
cubie on that slice. Replace it with the cubie that you
want to put in its place.
e  a  2  d 
> L >    
3  1  g  h 
e  a  2  d 
> D >    
h  3  1  g 
a  3  2  d 
> L' >     After L D L'
e  h  1  g 
The top layer was (a,b,c,d); now it is (a,f,c,d).
"b" has been taken off the top slice, and "f" is in its place.
(2) Rotate the chosen slice to place a new cubie in the hot seat.
3  2  d  a 
> U >     After (L D L') U
e  h  1  g 
(3) Undo step 1, which pops the chosen cubie "b" back to its
original slice, *and* (here's the key part), restore (nearly) all
other cubies to their original locations, since none of the
disturbed ones were on the slice that rotated in step (2).
3  1  d  a 
> L D' L' >     After (L D L') U (L D' L')
e  2  g  h 
(4) Undo step 2, restoring the chosen slice back to its original position.
a  3  1  d 
> U' >     After (L D L') U (L D' L') U'
e  2  g  h 
So the move sequence to cycle corners (1,2,3) is simply
(L D L') U (L D' L') U' (reading left to right).
With a few extra moves before this sequence (which should be undone
afterwards) to arrange the cubies which should be moved into the
places which are actually modified by this operation (or a similar
one), this trick and its variations can be used to put back all 8
corners into their proper places.
And with a bit of exploration, this same idea can be used to cycle
three cubies of any type, in any orbit, on any layer, without
disturbing anything else. For the EdgeSingles on the 3x3x3, for
example, to bring an edge off the top slice without disturbing
anything else on top, step (1) can be S D S', where "S" vertical is a
rotation of a center slice.
I have actually tried this for all eight of the types of orbits, and
indeed it does work. Yes, I know this is pure handwaving, but this
essay is already long enough, and it really is pretty straightforward
once you get the idea.
=====================================================================
(VII) Turning Corners and Flipping Edges ===========================
=====================================================================
I don't think I need to say too much about this, because
basically the same tricks that work on the 3x3x3 Cube will
work on the orbits in the NxNxN.
My usual approach is to find a sequence that will bring
a corner or singleedge cubie out of its position, and
then back with a turn or flip, *without* changing any cubie on on
slice. Call that entire operation "A". Then just like
before, A R A' R' where "R" is a rotation of the slice which
was left (nearly) unchanged will restore all the parts of the
Cube which were messed up by A, and leave only two corners or
two edges turned or flipped.
For example, on the 3x3x3, this sequence will turn two corners.
[(L DD L') (F' DD F)] U [(F DD F') (L' DD L)] U'
The stuff in the brackets brings a corner cubie off the top (up)
slice, and brings it back with a twist.
If "H" is a clockwise (as viewed from the top) quarter turn
on the horizontal center slice of the 3x3x3 (the plane parallel
to the top and bottom), then this similar sequence will flip two edges.
[ (L HH L') U' (F' HH F) U ] U [ U' (F HH F') U (L' HH L) ] U'
Again, the moves in the brackets bring one of the 3x3x3 edge
cubies off the top layer, and bring it back with a twist.
One can also combine several different 3cycles from section VI
to twist and flip the corners and edges.
=====================================================================
(VII) Comments ===================================================
=====================================================================
Well, that turned out to be a lot longer than I'd planned. If anyone
has actually bothered to read down this far, I hope it was worthwile.
I think that when all is said in done, the 3x3x3 is by far the most
interesting of the sizes. All the new types of orbits on the larger
Cubes are fairly boring, actually, since none of the cubies can be
flipped or turned in place the way that the 3x3x3 corners and edges
can. And I confess that I like how the only cubie on the 3x3x3 that
you can't see  the one that I like to imagine is hidden in the center
 is the only one that's completely specified by the locations of the
other orbits, namely by the positions of the face centers.
When I was first working out this stuff, back in 1981, I built a 7x7x7
Cube out of colored dice. None of them were "stuck" to the others; it
was just stack of dice. Manipulating it was pure hell, but I could
usually squeeze a layer and carefully turn and put it back. One slip
and I had dice all over the room.
I have a few other ideas kicking around in the back of my head,
but they'll have to wait for another time, and another note.
Regards,
Dr. Jim Mahoney mahoney@marlboro.edu
Physics & Astronomy
Marlboro College, Marlboro, VT 05344