# NxNxN cubes in GAP

Since defining GAP definitions for large cube sizes can be very tedious, I have implemented some GAP code for defining NxNxN cubes. The main function is called GenCube and returns a group representing a cube of the size specified by the parameter n. This function has a 2nd parameter (center_ori) used for odd cubes that allows specifying whether or not you wish to have the orientation of the most central pieces on each face to be considered significant.

The code uses a face-based numbering system. The facelets on the U face are numbered 1 to n2, the L face uses numbers n2 + 1 to 2n2, and the remaining faces are similarly numbered in the order F, R, B, D. For handling orientation of the most central pieces on each face, 18 additional numbers are used, starting at 6n2 + 1.

For 4x4x4 cubes, the inner layers have typically been given lower case letters to distinguish them from the face layers. For large size cubes, it becomes awkward defining distinct symbols for each layer. Therefore, my code uses lists for each of the three axes. So U represents the U face layer, U represents the layer below it, and so on for all the layers for that axis. Similarly, lists L and F are used to represent the layers of the other two axes. Whole cube rotations are also represented through variables x, y, and z using the standard definitions used in the speedcubing community. x is a cube rotation in the same direction as R, y is a cube rotation in the same direction as U, and z is a cube rotation in the same direction as F.

I note that turns of all layers are for the same direction as U, L, or F. So, for instance, the R turn for a 6x6x6 cube would be represented by L^-1. I also note that for both even and odd size cubes, the code supports representing 24 orientations of the cube, so the number of elements in the group may be 24 times larger than what you might expect. You can always create your own groups from the elements of the U, L, and F lists as in the examples below.

Examples:

Standard 5x5x5 supercube group:

```C555 := GenCube (5, true);
Super555 := Group (U, U, U^-1, U^-1, L, L, L^-1, L^-1, F, F, F^-1, F^-1);
```

Group with Fixed DLB corner for 4x4x4 cube:

```C444 := GenCube (4, false);
FixedDLB444 := Group (U, U, U^-1, U*U*U,
L^-1, L^-1, L, (L*L*L)^-1,
F, F, F^-1, F*F*F);
```

(Of course, these examples work without using "^-1" where indicated; but this way, the generators are consistently represented using what we generally consider clockwise turns.)

In large cubes, the face pieces (typically called centers) of the same color and orbit are generally considered indistinguishable. Modelling the puzzle as a permutation group in GAP does not directly allow these pieces to be considered indistinguishable. So the size of the group will generally be much larger than the actual number of positions for non-supercube puzzles.

So, finally, the GAP source code is given below. Let me know if you think you find any bugs.

```#GenCube

#Globals used
U := [];
L := [];
F := [];
x := ();
y := ();
z := ();

GenFaceCycle := function (n, face, ring, orb, dir)
local base, n1, n2, n3, n4, g;
base := n*n*(face - 1);
n1 := base + 1 + ring*n + ring + orb;
n2 := base + n + ring*n - ring + orb*n;
n3 := base + n*n - ring*n - ring - orb;
n4 := base + n*n - n + 1 - ring*n + ring - orb*n;
g := (n1, n2, n3, n4);
if dir then
g := g^-1;
fi;
return g;
end;

GenHorizLayerCycle := function (n, layer, orb)
local n1, n2, n3, n4, g;
n1 := n*n + 1 + layer*n + orb;
n2 := 4*n*n + 1 + layer*n + orb;
n3 := 3*n*n + 1 + layer*n + orb;
n4 := 2*n*n + 1 + layer*n + orb;
g := (n1, n2, n3, n4);
return g;
end;

GenVertLayerCycle := function (n, layer, orb)
local n1, n2, n3, n4, g;
n1 := 1 + orb*n + layer;
n2 := 2*n*n + 1 + orb*n + layer;
n3 := 5*n*n + 1 + orb*n + layer;
n4 := 5*n*n - orb*n - layer;
g := (n1, n2, n3, n4);
return g;
end;

FaceCycles := function (n, face, center_ori, g)
local i, j, r, b, n2, xc, nb, h;
h := g;
n2 := Int (n/2);
r := 0;
while r < n2 do
nb := n - 2*r - 1; # for even n, at least
b := 0;
while b < nb do
h := h*GenFaceCycle (n, face, r, b, face >= 4);
b := b + 1;
od;
r := r + 1;
od;
if center_ori then
i := (face-1)*(n^2) + (n^2 + 1)/2;
if i = Int (i) then #odd size cube
xc := 6*(n^2) + 1;
j := xc + (face-1)*3;
if face >= 4 then
h := h*(i,j+2,j+1,j);
else
h := h*(i,j,j+1,j+2);
fi;
fi;
fi;
return h;
end;

LayerCycles := function (n, face, layer, center_ori, g)
local i, b, n2, xc, c1, c2, c3, c4, h, c4list;
n2 := Int (n/2);
h := g;
b := 0;
while b < n do
if face = 1 then
h := h*GenHorizLayerCycle (n, layer, b);
fi;
if face = 2 then
h := h*GenVertLayerCycle (n, layer, b);
fi;
b := b + 1;
od;
if center_ori and (2*n2 < n) then
if layer = n2 then
xc := 6*(n^2) + 1;
if face = 1 then
c1 := xc + 3;
c2 := xc + 12;
c3 := xc + 9;
c4 := xc + 6;
fi;
if face = 2 then
c1 := (n^2 + 1)/2;
c2 := 4*(n^2) + (n^2 + 1)/2;
c3 := xc + 13;
h := h*(c1,c2,c3); #correction to cycle for non-rotating case
c1 := xc + 0;
c2 := xc + 6;
c3 := xc + 15;
c4list := [xc + 14, 4*(n^2) + (n^2 + 1)/2, xc + 12];
fi;
i := 0;
while i < 3 do
if face = 1 then
h := h*(c1+i,c2+i,c3+i,c4+i);
fi;
if face = 2 then
h := h*(c1+i,c2+i,c3+i,c4list[i+1]);
fi;
i := i + 1;
od;
fi;
fi;
return h;
end;

GenCube := function (n, center_ori)
local  layer, g;
#initialize globals (except z which will be assigned directly using x and y later)
U := [];
L := [];
F := [];
x := ();
y := ();
#U-axis layers
layer := 0;
while layer < n do
g := ();
if layer = 0 then
g := FaceCycles (n, 1, center_ori, g);
fi;
if layer = n - 1 then
g := FaceCycles (n, 6, center_ori, g);
fi;
g := LayerCycles (n, 1, layer, center_ori, g);
y := y*g;
layer := layer + 1;
od;
#L-axis layers
x := ();
layer := 0;
while layer < n do
g := ();
if layer = 0 then
g := FaceCycles (n, 2, center_ori, g);
fi;
if layer = n - 1 then
g := FaceCycles (n, 4, center_ori, g);
fi;
g := LayerCycles (n, 2, layer, center_ori, g);
x := x*(g^-1);
layer := layer + 1;
od;
#F-axis layers
layer := 1;
while layer <= n do
layer := layer + 1;
od;
z := x*y*(x^-1);
return Group (Concatenation (U, L, F));
end;
```

## Comment viewing options

### Confirmation

Bruce,
Your GAP code inspired me to do something similar in C. I limited the code to a fixed DLB cubie model. The generator permutations are the actions of the turns on the facelet center points numbered as listed( x = R, y = U, z = F). The turns are labeled proceeding inward from the face turn. Ra is a cw turn of the right face, Rb is a cw turn of the middle slice one in from the right face, etc. Here's my output for the 4x4x4 cube.

4 x 4 x 4 Cube

```# Facelet Positions:
#           Back               Left                Down
# 1     (-3,-3,-4)    17    (-4,-3,-3)    33    (-3,-4,-3)
# 2     (-3,-1,-4)    18    (-4,-3,-1)    34    (-1,-4,-3)
# 3     (-3, 1,-4)    19    (-4,-3, 1)    35    ( 1,-4,-3)
# 4     (-3, 3,-4)    20    (-4,-3, 3)    36    ( 3,-4,-3)
# 5     (-1,-3,-4)    21    (-4,-1,-3)    37    (-3,-4,-1)
# 6     (-1,-1,-4)    22    (-4,-1,-1)    38    (-1,-4,-1)
# 7     (-1, 1,-4)    23    (-4,-1, 1)    39    ( 1,-4,-1)
# 8     (-1, 3,-4)    24    (-4,-1, 3)    40    ( 3,-4,-1)
# 9     ( 1,-3,-4)    25    (-4, 1,-3)    41    (-3,-4, 1)
# 10    ( 1,-1,-4)    26    (-4, 1,-1)    42    (-1,-4, 1)
# 11    ( 1, 1,-4)    27    (-4, 1, 1)    43    ( 1,-4, 1)
# 12    ( 1, 3,-4)    28    (-4, 1, 3)    44    ( 3,-4, 1)
# 13    ( 3,-3,-4)    29    (-4, 3,-3)    45    (-3,-4, 3)
# 14    ( 3,-1,-4)    30    (-4, 3,-1)    46    (-1,-4, 3)
# 15    ( 3, 1,-4)    31    (-4, 3, 1)    47    ( 1,-4, 3)
# 16    ( 3, 3,-4)    32    (-4, 3, 3)    48    ( 3,-4, 3)
#
#          Front                 Up                Right
# 49    ( 3, 3, 4)    65    ( 3, 4, 3)    81    ( 4, 3, 3)
# 50    ( 3, 1, 4)    66    ( 1, 4, 3)    82    ( 4, 3, 1)
# 51    ( 3,-1, 4)    67    (-1, 4, 3)    83    ( 4, 3,-1)
# 52    ( 3,-3, 4)    68    (-3, 4, 3)    84    ( 4, 3,-3)
# 53    ( 1, 3, 4)    69    ( 3, 4, 1)    85    ( 4, 1, 3)
# 54    ( 1, 1, 4)    70    ( 1, 4, 1)    86    ( 4, 1, 1)
# 55    ( 1,-1, 4)    71    (-1, 4, 1)    87    ( 4, 1,-1)
# 56    ( 1,-3, 4)    72    (-3, 4, 1)    88    ( 4, 1,-3)
# 57    (-1, 3, 4)    73    ( 3, 4,-1)    89    ( 4,-1, 3)
# 58    (-1, 1, 4)    74    ( 1, 4,-1)    90    ( 4,-1, 1)
# 59    (-1,-1, 4)    75    (-1, 4,-1)    91    ( 4,-1,-1)
# 60    (-1,-3, 4)    76    (-3, 4,-1)    92    ( 4,-1,-3)
# 61    (-3, 3, 4)    77    ( 3, 4,-3)    93    ( 4,-3, 3)
# 62    (-3, 1, 4)    78    ( 1, 4,-3)    94    ( 4,-3, 1)
# 63    (-3,-1, 4)    79    (-1, 4,-3)    95    ( 4,-3,-1)
# 64    (-3,-3, 4)    80    (-3, 4,-3)    96    ( 4,-3,-3)

Ra := (13,77,49,48)(14,73,50,44)(15,69,51,40)(16,65,52,36)(81,93,96,84)(82,89,95,88)(83,85,94,92)(86,90,91,87);
Rb := (9,78,53,47)(10,74,54,43)(11,70,55,39)(12,66,56,35);
Rc := (5,79,57,46)(6,75,58,42)(7,71,59,38)(8,67,60,34);
Ua := (4,32,49,84)(8,31,53,83)(12,30,57,82)(16,29,61,81)(65,77,80,68)(66,73,79,72)(67,69,78,76)(70,74,75,71);
Ub := (3,28,50,88)(7,27,54,87)(11,26,58,86)(15,25,62,85);
Uc := (2,24,51,92)(6,23,55,91)(10,22,59,90)(14,21,63,89);
Fa := (20,48,81,68)(24,47,85,67)(28,46,89,66)(32,45,93,65)(49,61,64,52)(50,57,63,56)(51,53,62,60)(54,58,59,55);
Fb := (19,44,82,72)(23,43,86,71)(27,42,90,70)(31,41,94,69);
Fc := (18,40,83,76)(22,39,87,75)(26,38,91,74)(30,37,95,73);

G := Group(Ra,Rb,Rc,Ua,Ub,Uc,Fa,Fb,Fc);
Size(G);
[ 707195371192426622240452051915172831683411968000000000```

The size of the group agrees with the size of the group FixedDLB444 from your post above. Also the size of the 5x5x5 fixed DBL group with indistinguishable center orientation is the same using your generators or mine. So, the programs confirm one another.

### B MacKenzie, thanks for the i

B MacKenzie, thanks for the independent confirmation of the results from my code.

So does your code also work for arbitrary N? I note I tried my GAP function for N as high as 100. (I didn't try to calculate even the size of the group for an 100x100x100 cube, though. It could take awhile even for 7x7x7, so I figured calculating the group size for a 100x100x100 cube was not practical.)

While you fixed the DLB cubie in your code, I basically wanted to produce the permutations for each and every layer. This allows the user to pick which layers he might want to restrict turning, rather than decide that for him. I realize there may be additional permutations that may also be of interest to a user. One is the possible permutations of face pieces only, particularly within the same face. Another is the permutation representing left-right mirroring. For now, I provide an implementation for the latter. Combined with the x, y, and z values my previous code provided, this allows specifying the M symmetry group for the corresponding NxNxN cube.

```GenMirror := function (n, center_ori)
local r, c, n2, g;
n2 := Int (n/2);
g := ();
r := 0; #row, 0-origin
while r < n do
c := 1; #column, 1-origin
while c <= n2 do
g := g*(n*r + c, n*r + n + 1 - c); #U face
g := g*(2*n^2 + n*r + c, 2*n^2 + n*r + n + 1 - c); #F face
g := g*(4*n^2 + n*r + c, 4*n^2 + n*r + n + 1 - c); #B face
g := g*(5*n^2 + n*r + c, 5*n^2 + n*r + n + 1 - c); #D face
g := g*(n^2 + n*r + c, 3*n^2 + n*r + n + 1 - c); #L,R faces
g := g*(3*n^2 + n*r + c, n^2 + n*r + n + 1 - c); #L,R faces
c := c + 1;
od;
r := r + 1;
od;
#central slices
if 2*n2 < n then
if center_ori then
#L,R faces
r := 0;
while r < n do
if r = n2 then
g := g*(n^2 + n*r + n2 + 1, 6*n^2 + 10);
g := g*(6*n^2 + 4, 3*n^2 + n*r + n2 + 1);
g := g*(6*n^2 + 5, 6*n^2 + 12);
g := g*(6*n^2 + 6, 6*n^2 + 11);
else
g := g*(n^2 + n*r + n2 + 1, 3*n^2 + n*r + n2 + 1);
fi;
r := r + 1;
od;
#U face
g := g*((n^2 + 1)/2, 6*n^2 + 1);
g := g*(6*n^2 + 2, 6*n^2 + 3);
#F face
g := g*(2*n^2 + (n^2 + 1)/2, 6*n^2 + 7);
g := g*(6*n^2 + 8, 6*n^2 + 9);
#B face
g := g*(4*n^2 + (n^2 + 1)/2, 6*n^2 + 13);
g := g*(6*n^2 + 14, 6*n^2 + 15);
#D face
g := g*(5*n^2 + (n^2 + 1)/2, 6*n^2 + 16);
g := g*(6*n^2 + 17, 6*n^2 + 18);
else
r := 0;
while r < n do
g := g*(n^2 + n*r + n2 + 1, 3*n^2 + n*r + n2 + 1); #L,R faces
r := r + 1;
od;
fi;
fi;
return g;
end;

#This function requires GenCube(n, center_ori) to be called first, to set globals x and y.
GenCubeSymmetryGroup := function (n, center_ori)
return Group (x, y, GenMirror (n, center_ori));
end;
```

### Symmetry Actions

Yes, my program will work with an arbitrary N up to to the limit of 16 bit signed integers for the facelet coordinates. The actions of the cubic group symmetries on the facelet coordinates are readily accessible with the tools I have at hand. Here's the relevant code for the 4x4x4 cube which could easily be generalized:

```-(void)initPositionTable
{
NCubeCubie  *new;
unsigned    cubie,
symtag;

for( cubie = 0 ; cubie < 56 ; cubie++ )
{
for( symtag = 0 ; symtag < 48 ; symtag++ )
{
new = [[cubies objectAtIndex: cubie] productWithSymtag: symtag];

position[cubie][symtag] = [cubies indexOfObject: new];

[new release];
}
}
}```

The call to the NCubeCubie productWithSymtag: method multiplies the receiver's coordinates by the cubic group transform matrix associated with symtag and creates a new NCubeCubie object with the transformed coordinates. [cubies indexOfObject: new] returns the index of the cubie in the cubies array whose coordinates match new. The columns of the table produced are inverse permutations representing the symmetry elements. This code actually gives the actions of the symmetries on the cubie positions. Equivalent code could be applied to a facelet array.

The above snippet of code comes from a 4x4x4 cube emulation I'm working on. I have the GUI built and spent a day or so learning to solve it. Since it does me no good to memorize arbitrary turn sequences (I will have forgotten them after a week or so) I have to "go all the way around Robin Hood's barn" to fix OLL parity. PLL parity may be fixed by composing short conjugator sequences and is not a problem. Now I have to see if I can put together an auto solve algorithm.

### Works well for the 2x2x2 and

Works well for the 2x2x2 and 3x3x3 as far as I can tell.
However - perhaps your model is slightly flawed for higher dimensions?
The order of the Professor's 5x5x5 cube listed on Wikipedia would
not seem to support your results. Yours is much larger than expected.
All primes > 3 have the correct power exponent having said that.

### The number of elements in the

The number of elements in the 5x5x5 group is larger than the number of positions of the Professor Cube because the Professor cube has indistinguishable pieces. The number on the Wikipedia page is the number of positions, not the size of any group for the 5x5x5.

The group generated by my GenCube function also considers rotations of the central slices, and that increases the size of the group by an additional factor of 24. GenCube(5,false) generates a group of (approx.) 61.983*10^90 elements. The number is exactly 24 times larger the number given on Jaap's Puzzle Page for the 5x5x5 with indistinguishable center pieces (2.58*10^90). Again, the extra factor of 24 is because my group includes generators for central slice moves.

### 2x2x2x2 group

I take your point about the symmetry group of the NxNxN (N>3) cube group being difficult to model in GAP.
Would it be possible to modify your code to attempt
to define generators for the 2x2x2x2 tesseract though?
From an old posting in the cube lovers mailing list there is a poster asserting the number of positions in this is (15!/2)((12^15)/3).

It would be good to have independent verification for this. Even if possible I suppose we would have to divide by 192 to cover the rotational symmetries of the whole 4D cube.

### Ignore the symmetry group comment please

Just to make clear that it makes no sense to talk of the symmetry "group" of the NxNxN (N>3) unless we distinguish between centre pieces. Apologies for not making this clear.
Now what about the permutations of the 2x2x2x2? Do these actually form a group?

### well, I made no attempt to wr

well, I made no attempt to write this code with the idea of extending it to other than 3-D cubes. I think it would require major modifications to make it work for 4-dimensional (or higher order) "cubes." Basically I assumed 6 faces each having N^2 consecutively numbered facelets. (I introduced 18 additional numbers for allowing orientation of the central most pieces on each face to be represented.) I then figured out formulas to describe the permutation cycles for each of the layers, based upon the numbering I used. I also used a symmetry trick for determining the generators for the 3rd axis from the generators calculated for the first two axes. I see no reason something similar can't be done for 4-dimensional tesseracts. I don't particularly plan to do this myself, but someone else could certainly take my code as a sort of model and try to write something similar for tesseracts.

I note that the Wikipedia article http://en.wikipedia.org/wiki/N-dimensional_sequential_move_puzzle gives an expression for the number of positions for the 2x2x2x2 that agrees with Dan Hoey's expression from the cube lovers mailing list. It also gives values for other 4-D and 5-D "cubes."

### Thanks for providing the link

Thanks for providing the link. I note however the numbers do not seem to match as the number of permutations listed here is 4.(15!/2)(4!/2)^14 by my reading.

In case this is not known, the good folk at Magic Cube 4 Applet have provided a software model for this (note the latest Java runtime environment software is needed for this to work). Actually obviously this is more than required to model the 2^4 where all 16 cubes are four-coloured. If I have the time which is doubtful I will try to express this in term of permutation representation generators to settle the matter.

### The two formulas give the sam

The two formulas give the same number. I note, however, that Hoey's post contains the wrong value for the power of 10 in the decimal value.

### Yikes

Yes they do indeed - silly me I had not checked explicitly. Re the power of 10 I would say that is a typo rather than anything else - should have been ~ 3.358 x 10^27.

### Oops, in my previous post, of

Oops, in my previous post, of course I meant that the 2.58*10^90 value refers to the number of positions if the center pieces can be distinguished.

### Indeed

4x4x4 and larger are no groups, exactly because there are indistinguishable pieces.

### Not true

They most certainly are groups. They are subgroups of finite index in the larger group. You are probably aware of the centre spot supergroup wherein each of these can be rotated by a quarter turn but with certain parity restrictions.

### Why the positions do not form a group

Well, the *positions* of the 4x4x4 and larger cubes (where certain sets of centers are viewed as indistinguishable) may be a "subspace" of the corresponding supercube groups, but these subspaces are not groups (and thus, not subgroups - at least not using our usual meaning for what the group operation does). As noted by Jaap in this thread (relating specifically to the 4x4x4), think of the subgroup of permutations of center pieces within their own respective faces as a subgroup H of the supercube group G. Positions of the cube can then be viewed as cosets Hg where g represents an element of G. The ("distinguishable") positions of the puzzle are the set of cosets Hg. But the set of cosets Hg do not form a mathematical group.

Note that in a group, each element has a unique inverse. Consider two elements of h1 and 2 of H, and an element g1 of G. Both h1g1 and h2g1 are elements of the coset Hg1. But their inverses, g1-1h1-1 and g1-1h2-1 are not necessarily in the same coset of the form Hg. By showing such a counterexample, we establish that the Hg1 does not have a unique inverse within the set of cosets Hg, and this proves that the set of cosets Hg does not form a group (and thus, can not be called a *subgroup* of G either).

### Ah so ... I am very much mistaken

I think I was reading what I wanted to. Nowhere on the Wikipedia page does it say that the permutations of the 5x5x5 cube (with indistinguishable centre pieces) form a group.

I had another look at your C444 example above. When we divide the order by 24 and then by (4!)^6 we get a group which is only half the size it should be (either on Jaap's pages or Wikipedia). This is troubling me slightly. What am I missing?

### Group size with parity restrictions

There are many puzzles on my site where the underlying group has a parity restriction, e.g. a set of pieces only allow even permutations, while also having identical pieces amongst that set.
When you solve such a puzzle you can get a 'parity problem', where it looks like you have to swap two pieces, even though this is strictly speaking impossible. In actuality, to do that swap you have to combine it with a swap of two of the identical pieces.

If all you are interested in is to count the number of positions, you might as well act as if every swap swap is actually possible. Simply divide the number of permutations of the pieces (including odd perms), and divide by the number of permutations of the identical pieces (including odd perms).

This calculation does not mirror the structure of the actual groups involved. The group is actually half the size (only even perms), but the achievable number of permutations of the identical pieces is also halved. This still leads to the same answer for the number of positions.

I usually don't bother to explicitly separate out a parity restriction in the calculation if there are identical pieces.

Examples of puzzles on my site where this occurs are the Alexander's Star, 4x4x4 and larger cubes, Butterfly Puzzle / Turnstile / Puzzler, Cohan Circle, Crossover, Dogic, and many others.

Jaap
Jaap's Puzzle Page: http://www.jaapsch.net/puzzles/

### Factor of 2 explanation

On the 4x4x4, a quarter-turn of a face layer changes both the parity of the center pieces and the parity of the corner pieces. An inner layer turn has no effect on either of these parities. So the parity of corner pieces is always the same as the parity of center pieces. So while all 24! permutations of the center pieces are possible (ignoring other pieces), only half of them are possible without any effects on other pieces (specifically, the corner pieces). In other words, any odd permutation of the centers is not possible without the corner pieces also being in an odd permutation. Hence, only half of the permutations of the center pieces are actually elements of the 4x4x4 supercube group. Likewise, if you take the group H from my previous post, if you include both odd and even permututations of the centers, only the even ones are actually elements of the 4x4x4 supercube group. So to have H actually be a subgroup of G, you need to restrict it to even permutations only, so you divide |G| by (1/2)(4!^6), rather than divide by 4!^6.