NxNxN cubes in GAP

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;

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.

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.

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."

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.

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 h₁ and ₂ of H, and an element g₁ of G. Both h₁g₁ and h₂g₁ are elements of the coset Hg₁. But their inverses, g₁^-1h₁^-1 and g₁^-1h₂^-1 are not necessarily in the same coset of the form Hg. By showing such a counterexample, we establish that the Hg₁ 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).

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/

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.