![[next]](go_next_btn.gif)
![[prev]](go_prev_btn.gif)
![[up]](go_up_btn.gif)
Date: Sun, 15 Jan 95 01:17:00 WET
From: Martin Schoenert <Martin.Schoenert@math.rwth-aachen.de
>
Subject: Re: Difficulty of SkewbDer Mouse wrote in his e-mail message of 1995/01/10
The size of the thing is thus somewhere on the order of 500 million
configurations. This is why I called it trivial next to the 3x3x3. :-)
The group structure in terms of facicles, for what's-his-name to sic
GAP on should he care to, derived from the following facicle labeling
Of course ``what's-his-name'' couldn't resist ;-).
Here are my findings about the SKEWB.
The SKEWB Puzzle ================
I took the liberty to renumber the points. This makes the orbits easier
recognizable.
up
+----------+
| 9 10 |
| 27 |
left | 12 11 | right back
+----------+----------+----------+----------+
| 5 6 | 18 17 | 1 2 | 22 21 |
| 26 | 29 | 25 | 30 |
| 8 7 | 19 20 | 4 3 | 23 24 |
+----------+----------+----------+----------+
| 13 14 |
| 28 |
| 16 15 |
+----------+
down
I call the 8 possible turns LUB, LUF, RUB, RUF, LDB, LDF, RDB, RDB.
Here LUB denotes the turn around the corner common to the L(eft),
U(p), and B(ack) faces that turns L to U, U to B, and B back to L.
Those turns all have order 3, and I denote the inverses with <gen>^-1
(at least there is no question which metric to use for the SKEWB ;-).
With respect to the above numbering, the generators are the following
permutations.
## corner other corners centers RUF := ( 1,11,17) ( 2,12,20)( 4,10,18)(22, 6,14) (25,27,29); RUB := ( 2,10,22) ( 1, 9,23)( 3,11,21)(17, 5,15) (25,27,30); LUF := ( 6,12,18) ( 5,11,19)( 7, 9,17)(21, 1,13) (26,27,29); LUB := ( 5, 9,21) ( 6,10,24)( 8,12,22)(18, 2,16) (26,27,30); RDF := ( 4,14,20) ( 1,15,19)( 3,13,17)( 7,11,23) (25,28,29); RDB := ( 3,15,23) ( 2,14,24)( 4,16,22)( 8,10,20) (25,28,30); LDF := ( 7,13,19) ( 6,16,20)( 8,14,18)( 4,12,24) (26,28,29); LDB := ( 8,16,24) ( 5,13,23)( 7,15,21)( 3, 9,19) (26,28,30);
With r, u, and f I denote the 3 rotations of the rigid cube,
which generate the full automorphism group of the cube.
Here r means the rotation around the axis going through the
r and l faces, turning the r face in clockwise direction.
## corners opposite centers
r := ( 1, 2, 3, 4) ( 6, 5, 8, 7) (27,30,28,29)
(11,22,15,20)(12,21,16,19)(10,23,14,17)( 9,24,13,18);
u := ( 9,10,11,12) (16,15,14,13) (30,25,29,26)
(22, 1,18, 5)(23, 4,19, 8)(21, 2,17, 6)(24, 3,20, 7);
f := (17,20,19,18) (21,22,23,24) (25,28,26,27)
( 1,14, 7,12)( 2,15, 8, 9)( 3,16, 5,10)( 4,13, 6,11);
Let G be the group generated by the 8 turns;
G = < LUB, LUF, RUB, RUF, LDB, LDF, RDB, RDF >.
Let C be the group generated by the 3 rotations; C = < r, u, f >. Obviously |C| = 24 and C ~ S_4. Let C' be the derived subgroup of C; C' = <Comm(r,u),Comm(f,r),Comm(u,f)>. Obviously |C'| = 12 and C' ~ A_4.
Then the group CG = < C, G > is the set of all positions a puzzler could
observate. There are 24 solved position in CG (solved up to rotations).
The group CG has size 2 * 6!/2 * ((3^4*4!/2) * (3^4*4!/2) / 3^2). The group G has size 6!/2 * ((3^4*4!/2) * (3^4*4!/2) / 3^2) (and is a normal subgroup of CG, since |CG/G| = 2). Note that this implies that |C <intersect> G| = 12. This is not suprising, since G obviously contains all the commutators: Comm(u,f) = LUB * RDF, Comm(r,u) = LUF * RDB, Comm(f,r) = RUB * LDF, Comm(u,f^-1) = RUF * LDB, (those are the rotations of the entire cube around the 4 diagonals), and so G must contain the derived subgroup C' of C.
The numbers imply that of the 6! * 3^8 * 8! position one can obtain by
taking the puzzle apart and randomly reassembling it, only ~ 0.04% are
solvable. Much less than the ~ 8.3% one gets for Rubik's cube.
If you choose to puzzle that way, it is certainly a lot more difficult
than Rubik's cube ;-).
The Structure of the SKEWB Group ================================
G has three orbits on [1..30]. Namely the six face centers F = [25..30],
the odd corners C1 = [1,3..23], and the even corners C2 = [2,4..24].
C shall denote the set of all corners, i.e., the union of C1 and C2.
The two orbits on the corners are the two tetrahedral sets of corners
mentioned by der Mouse.
Let G[F] be the operation of G on the faces centers, i.e., G[F] = G/G_F,
where G_F is the stabilizer in G of the face centers (the subgroup of
those elements of G that fix all face centers). Let G[C] be the
operation of G on the corners, i.e., G[C] = G/G_C, where G_C is the
stabilizer in G of the corners.
As usual with the operation of a group on several orbits, the stabilizers
are normal subgroups, and they intersect trivially. On the other hand
the size of G_C is 6!/2 and the size of G_F is (3^4*4!/2 * 3^4*4!/2)/3^2.
So |G|=|G_C||G_F| and we see that G is the direct product of G_C and G_F.
What that means puzzle-wise is that there are no dependencies between the
operations on the faces and corners. So take any achivable position x[F]
of the faces and any achivable position y[C] of the corners. Then there
is a position z that has simultaineously z[F] = x[F] and z[C] = y[C]
(in the case of Rubik's cube this is not possible, you can flip a single
edge if you ignore what happens at the corners, but you cannot combine
this flip of a single edge with a trivial operation on the corners).
So we can fully understand the structure of G simply by understanding the
structures of G_C and G_F. Of course we can also analyse G[F] and G[C],
since the isomorphism theorem tells us that G_C ~ G[F] and G_F ~ G[C].
Obviously G[F] is simply the alternating group A_6. That means we can
achieve any even permutation on the center faces. This is not suprising.
All 8 generators effect 3-cylces on the center faces. And with 8
3-cycles, one expects the full alternating group to pop up.
G[C] has the 2 orbits C1 and C2. Clearly G[C1] and G[C2] are isomorphic.
G[C1] is the wreath product of the cyclic group C_3 and the alternating
group A_4. That means you can twist each corner independently and
achieve any even permutation on the four corners. That you can only
achieve even permutations is obvious, since all generators of G[C]
permute 3 corners in a 3-cycle. So |G[C1]| = |G[C2]| = 3^4*4!/2.
Now G[C] is the subdirect product of G[C1] and G[C1]. That means it is isomorphic to a subgroup of the direct product of G[C1] and G[C2]. It is a subgroup of index 9. That means |G[C]| = |G[C1]| |G[C2]| / 9 = (3^4*4!/2 * 3^4*4!/2) / 3^2.
G[C] is the subgroup of G[C1] * G[C2] of those permutations where each
(anti)clockwise twist of a corner in C1 is combined with a
(anti)clockwise 3-cycle of corners in C2 and each (anti)clockwise twist
of a corner in C2 is combined with a (anti)clockwise 3-cycle of corners
in C1.
This was the most surprising observation for me, so allow me to talk a
little bit more about this aspect.
The subdirect product G[C] is a product where we ``glue'' together a
common factor group of G[C1] and G[C2]. Now this common factor group is
the direct product C_3*C_3 of two cyclic groups of size 3. One of them,
K say, comes from the normal subgroup C_3^4 of those elements that only
twist the corners. The other, L say, comes from the alternating group
A_4. Now those factor groups are glued together crosswise, that is,
K of G[C1] is glued to L of G[C2], and L of G[C1] is glued to K of G[C2].
In case anybody cares, G has trivial center. This is because the central
elements of G[C1] must be combined in G[C] with non-central elements of
G[C2] and vice versa. And of course G[F] has trivial center.
The Normal Subgroups of the SKEWB Group =======================================
I have also computed the lattice of normal subgroups of the SKEWB group.
Since the group is so small, I don't need any complicated argument.
G is a little bit too large to simply try 'NormalSubgroups(G);' in GAP.
But G[F] and G[C] are both small enough. G[F] is almost trivial
(GAP finds in a few seconds that G[F] has no proper normal subgroups).
G[C] is a little bit more difficult (but it took me much longer to draw
a reasonable picture, then it took GAP to compute the normal subgroups).
Anyhow, allow me to first present the normal subgroups lattice of G[C1],
which is of course identical to the normal subgroups lattice of G[C2].
G[C1] (972)
//|\
/ / | \
L1 L2 L3 K[C1] (324)
\ \ | / \
\\|/ \
(108) G[C1]' \
\ V[C1] (81)
\ / \
\ / \
(27) W[C1] \
\ \
\ \
\ \
\ Z[C1] (3)
\ /
\ /
<1>
Here V[C1] is elementary abelian subgroup (the vector space) of those 3^4
elements of G[C1] that only twist the corners, but do not permute them.
G[C1]/V[C1] is the A_4 permuting the corners. K[C1]/V[C1] is the
subgroup of G[C1]/V[C1] of the double transpositions, i.e, the elements
that permute the corners in two pairs of two corners each. G[C1]' is the
derived subgroup of G[C1], i.e., G[C1]/G[C1]' is the largest abelian
factor group of G[C1] (b.t.w. note that the fact that G is a direct
product implies that G[C1]' = G'[C1]). L1, L2, and L3 are three more
normal subgroups of index 3, which I don't know how to describe easily.
Z[C1] is the center of G[C1].
And now the lattice of normal subgroups of G[C].
G[C] (104976)
//|\
/ / | \
L1 L2 L3 K[C] (34992)
\ \ | / \_
\\|/ | \
(11664) G[C]' \ \
\_ V1 V2 (8748)
| \ / X \
\ X / \ \
(2916) W1 W2 \ \
/ X \ \ \
|_/ \ \ \ \
/ \ \ \ \
(729) W[C] \ \ \ \
\ \ \ \ \
\ \ \ Z1 Z2 (324)
\ \ \ / /
\_ \ X /
| \ S1 S2 (108)
\ \ / /
\ \ / /
\ X /
T1 T2 (27)
/ /
/ /
/ /
|_/
/
/
/
/
<1>
S1 and S2 are the stabilizers G[C]_C1 and G[C]_C2, so the normal subgroup
lattices above S1 and S2 are identical to the normal subgroup lattices of
G[C1] (= G[C2]). Those two lattices over S1 and S2 share the normal
subgroups over G[C]' (this is where G[C1] and G[C2] are glued together).
W[C] (the intersection of W1 and W2) is the elementary abelian subgroups
(the vectorspace) of those elements of G[C] that only twist the 8
corners, but do not permute them. G[C]/W[C] is the A_4*A_4 permuting the
two sets of corners. G[C]' is the derived subgroup of G[C], i.e.,
G[C]/G[C]' is the largest abelian subgroup of G[C].
Now we get the normal subgroup lattice of G by taking the above picture
twice, once below G_F (because G_F ~ G[C]), and once above G_C (because
G/G_C ~ G[C]).
G_______
//|\ \
LLL K \
D \ \
\ VV \
WW \\ G_F
W \\ \\ //|\
\ \\ ZZ LLL K
\\ SS D \
TT \ VV
// WW \\
/ W \\ \\
G_C \ \\ ZZ
\ \\ SS
\ TT
\ //
\_______ /
<1>
God's algorithm for the SKEWB =============================
The next was to compute God's algorithm for the SKEWB.
G is not very large, but is is easier to use a smaller model.
Let H be the subgroup generated by the 4 turns LUB, LUF, RUB, and RUF.
Repeated application of the rules
<turn> <rotation> -> <rotation> <other-turn>, LDB -> Comm(u,f^-1) * RUF^-1, LDF -> Comm(f,r) * RUB^-1, RDB -> Comm(r,u) * LUF^-1, RDF -> Comm(u,f) * LUB^-1,
allows us to translate any process in CG to one that starts with a single
rotation and continues with a process in H, i.e., it starts with a
rotation and continues with a process that involves only LUB, LUF, RUB,
and RUF and their inverses.
Note however, that H is *not* a supplement for C in CG. This is because
the intersection of H and C is not trivial. Namely H contains d^2, i.e.,
the rotation by 180 degree around the axis through the down face (which
is fixed by H) and the up face.
That means that H contains 2 solved positions, and each position of H
contains to 12 positions of CG. In other word H has index 12 in CG.
Here is the table for H. The first column contains the lenght. The
second column contains the number of positions of that length in H.
The third column contains the number of positions of that length that are
local maxima, i.e., the number of positions <pos> such that for no
generator <gen> the position <pos>*<gen> is longer. The fourth column
contains the number of positions such that for one generator <gen> the
position <pos>*<gen> is longer. And so on. So the eleventh column
contains the number of positions <pos> such that for all eight generators
<pos>*<gen> is longer (this happens of course only for the 2 solutions).
length #pos #loc max 0 2 0 0 0 0 0 0 0 0 2 1 16 0 0 0 0 0 0 16 0 0 2 96 0 0 0 0 0 0 96 0 0 3 576 0 0 0 0 0 0 576 0 0 4 3456 0 0 0 0 0 240 3216 0 0 5 20496 0 0 0 48 729 2766 16953 0 0 6 118608 48 161 1231 4228 14779 32993 65168 0 0 7 630396 8266 33358 76349 121363 153892 137755 99413 0 0 8 2450966 1025322 621763 381098 234661 128570 47822 11730 0 0 9 2911712 2768641 126056 15344 1422 199 50 0 0 0 10 162056 161876 180 0 0 0 0 0 0 0 11 180 180 0 0 0 0 0 0 0 0
To get the table for CG, simply multiply each number by 12.
This was computed with a small C program in 200 seconds on a Pentium 90
system using approx 16 MByte of memory. Since this is my first
computation of this kind, I would be glad if somebody could independently
verify this table.
The SuperSKEWB ==============
If we do not ignore the orientation of the face centers we obtain the
SuperSKEWB. This could for example be done by drawing a line over
one corner and the center for each face of the cube.
Mathematically I modelled the SuperSKEWB by representing each face center
with a set of four numbers (instead of a single number). That pushed
the total number of moved points from 30 to 48 (still pretty small).
The size of the SuperSKEWB group SG is a factor 32 greater than G's size, i.e., it is (2^5*6!/2) * ((3^4*4!/2) * (3^4*4!/2) / 3^2). The size of CSG (closure of C and SG) is also a factor 32 greater than CG's size, i.e., it is 2*(2^5*6!/2) * ((3^4*4!/2) * (3^4*4!/2) / 3^2).
It is easy to see that you cannot turn a face center by 90 degrees in SG.
Namely the corner pieces fall into two tetrahedral sets, which are not
interchanged by SG. Now a given edge of a face center will always be
adjacent to corners in one of those two sets of corner pieces.
Simply by looking at the generators of SG, we see that each
element of SG must turn an even number of face centers.
So we can turn at most five of the six face centers independently;
after that the orientation of the sixth face center is determined.
So there are at most 2^5 different orientations possible. Since
|SG| = 2^5 |G|, we see that all 2^5 orientations are indeed achievable.
The structure of SG is of course very similar to the structure of G.
SG[C] is identical to G[C]. Remember that G[F] was A_6.
SG[F] is a subgroup of index 2 in the wreath product 2 <wreath> A_6.
The index 2 is because one cannot turn a single face.
Note that SG has a nontrivial center, namely the element that turns
all face centers at once.
Thus the lattice of normal subgroups of SG is very similar to the lattice
of G. The only difference is that SG_C (and of course also SG/SG_F) has
two nontrivial normal subgroups with sizes 32 and 2 (resp. with sizes
32*104976 and 2*104976).
I cannot compute God's algorithm for the SuperSKEWB. Would I use the
same approach that I used for the SKEWB, I would need 32 times as much
memory, i.e., ~ 1/2 GByte. Does anybody have an idea how to tackle the
SuperSKEWB (provided anybody cares, I certainly don't)?
Have a nice day.
Martin.
PS: No, I don't own a SKEWB. Yes, I intent to order one.
-- .- .-. - .. -. .-.. --- ...- . ... .- -. -. .. -.- .- Martin Sch"onert, Martin.Schoenert@Math.RWTH-Aachen.DE, +49 241 804551 Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany
![[top]](go_top_btn.gif)
![[help]](help_btn.gif)