Home »

The Void Cube in GAP

Submitted by B MacKenzie on Thu, 03/10/2011 - 21:37.

I have been amusing myself messing around with GAP and have modeled the void cube. The void cube is a standard cube with indistinguishable center cubie facelets. The void cube may be modeled by the group: < R , U , F , TR , RU , TF > , where the latter three generators are "Tier" or "Tandem" moves of a face and the adjacent middle slice. Note that the generators do not move the DBL cubie. As such, this is a fixed corner cubie model. The DBL cubie provides the necessary frame of reference which defines which face is Up, which face is Right and so forth. The tandem moves are the fixed corner cubie model counterparts of the L , D , B moves in the standard fixed center facelet model--they perform the same rearrangement of the cubies relative to one another.

Representing the group in GAP as permutations of the 48 corner/edge facelets:

[ Singmaster-Reid facelet order:
[    UF UR UB UL DF DR DB DL FR FL BR BL UFR URB UBL ULF DRF DFL DLB DBR

[ Standard Face Turns:

R := (3,17,11,21)(4,18,12,22)(25,39,46,30)(26,37,47,28)(27,38,48,29);
U := (1,3,5,7)(2,4,6,8)(25,28,31,34)(26,29,32,35)(27,30,33,36);
F := (1,20,9,18)(2,19,10,17)(25,35,40,38)(26,36,41,39)(27,34,42,37);
L := (7,23,15,19)(8,24,16,20)(31,45,40,36)(32,43,41,34)(33,44,42,35);
D := (9,15,13,11)(10,16,14,12)(37,40,43,46)(38,41,44,47)(39,42,45,48);
B := (5,22,13,24)(6,21,14,23)(28,48,43,33)(29,46,44,31)(30,47,45,32);

[ Middle Slice Turns sans the center cubies, which remain fixed.  As such 
[ these moves cannot be performed on the standard cube.

MR := (1,10,13,6)(2,9,14,5);
MU := (17,22,23,20)(18,21,24,19);
MF := (3,8,15,12)(4,7,16,11);

[ Tier Turns:

TR := R * MR;
TU := U * MU;
TF := F * MF;

SuperGroup := Group( R , U , F , L , D , B , TR , TU , TF );
StandardCube := Group( R , U , F , L , D , B );
VoidCube := Group( R , U , F , TR , TU , TF );

SG := Size( SuperGroup );
[ 86504006548979712000

SC := Size( StandardCube );
[ 43252003274489856000

SV := Size( VoidCube);
[ 3604333606207488000

SG / SC;
[ 2

SG / SV;
[ 24

First note that the tier turns have odd position parity. They move twelve cubies in three, odd parity, four cycles. In contrast to the standard cube, it is possible to swap two cubies on the void cube. For example the UF and UR cubies may be swapped by:

[ Cubie Swap: R F U TU' F' TR' TU' F' U R' TR U' F TU

CubieSwap := TU * F * U^-1 * TR * R^-1 * U * F^-1 * TU^-1 * TR^-1 * F^-1 * TU^-1 * U * F * R;
[ (1,3)(2,4)

Thus, represented in this way the void cube group is not a subgroup of the standard cube group. Rather, it is the subgroup of a super group of the standard cube group which includes odd position parity states. The void cube group is the subgroup of the super group with the DBL cubie in the identity state. Thus the order of the void cube group is 1/24 the order of the super group. The standard cube group is the subgroup of the super group with even position parity and is 1/2 the size of the super group.

It is possible to map the elements of the void cube 1:1 to cosets of a subgroup of the standard cube group. This subgroup is the Dots group, the group of cube states with the edge and corner facelets of each face the same color:

[ Six spot pattern 1:  R' U' D F' B R' L D

Dots1 := D * L * R^-1 * B * F^-1 * D * U^-1 * R^-1;

[ Six spot pattern 2:  B' U' D R' L B' F D

Dots2 := D * F * B^-1 * L * R^-1 * D * U^-1 * B^-1;

DotsGroup := Group( Dots1 , Dots2 );


Size(DotsGroup);
[ 12

List( DotsGroup );
[ 
(), 
(1,13)(2,14)(3,11)(4,12)(5,9)(6,10)(7,15)(8,16)(17,21)(18,22)(19,23)(20,24)
    (25,46)(26,47)(27,48)(28,37)(29,38)(30,39)(31,40)(32,41)(33,42)(34,43)
    (35,44)(36,45), 
(1,5)(2,6)(3,7)(4,8)(9,13)(10,14)(11,15)(12,16)(17,23)(18,24)(19,21)(20,22)
    (25,31)(26,32)(27,33)(28,34)(29,35)(30,36)(37,43)(38,44)(39,45)(40,46)
    (41,47)(42,48), 
(1,9)(2,10)(3,15)(4,16)(5,13)(6,14)(7,11)(8,12)(17,19)(18,20)(21,23)(22,24)
    (25,40)(26,41)(27,42)(28,43)(29,44)(30,45)(31,46)(32,47)(33,48)(34,37)
    (35,38)(36,39), 
(1,17,4)(2,18,3)(5,19,12)(6,20,11)(7,10,22)(8,9,21)(13,23,16)(14,24,15)
    (25,26,27)(28,36,38)(29,34,39)(30,35,37)(31,41,48)(32,42,46)(33,40,47)
    (43,45,44), 
(1,23,12)(2,24,11)(3,6,22)(4,5,21)(7,14,18)(8,13,17)(9,19,16)(10,20,15)
    (25,32,48)(26,33,46)(27,31,47)(28,30,29)(34,45,38)(35,43,39)(36,44,37)
    (40,41,42), 
(1,19,8)(2,20,7)(3,10,24)(4,9,23)(5,17,16)(6,18,15)(11,14,22)(12,13,21)
    (25,41,33)(26,42,31)(27,40,32)(28,39,44)(29,37,45)(30,38,43)(34,36,35)
    (46,47,48), 
(1,21,16)(2,22,15)(3,14,20)(4,13,19)(5,23,8)(6,24,7)(9,17,12)(10,18,11)
    (25,47,42)(26,48,40)(27,46,41)(28,45,35)(29,43,36)(30,44,34)(31,32,33)
    (37,39,38), 
(1,4,17)(2,3,18)(5,12,19)(6,11,20)(7,22,10)(8,21,9)(13,16,23)(14,15,24)
    (25,27,26)(28,38,36)(29,39,34)(30,37,35)(31,48,41)(32,46,42)(33,47,40)
    (43,44,45), 
(1,16,21)(2,15,22)(3,20,14)(4,19,13)(5,8,23)(6,7,24)(9,12,17)(10,11,18)
    (25,42,47)(26,40,48)(27,41,46)(28,35,45)(29,36,43)(30,34,44)(31,33,32)
    (37,38,39), 
(1,12,23)(2,11,24)(3,22,6)(4,21,5)(7,18,14)(8,17,13)(9,16,19)(10,15,20)
    (25,48,32)(26,46,33)(27,47,31)(28,29,30)(34,38,45)(35,39,43)(36,37,44)
    (40,42,41), 
(1,8,19)(2,7,20)(3,24,10)(4,23,9)(5,16,17)(6,15,18)(11,22,14)(12,21,13)
    (25,33,41)(26,31,42)(27,32,40)(28,44,39)(29,45,37)(30,43,38)(34,35,36)
    (46,48,47)
 ]

The Dots group elements are the actions of the twelve T rotation symmetries on the facelets—the two fold rotations about the principal axes of the cube and the three fold rotations about the cube diagonals. Thus each state of the void cube corresponds to twelve states of the standard cube which have the same arrangement of the edge and corner cubies relative to one another but differ in their relation to the center cubies. On the standard cube the following two turn sequences give two different cube states corresponding to the above UF / UR cubie swap:

B F' R B' R' B' L' B F' D F R B R'
R D' B L R' U' B R' U' L R' B F D' U R'

They differ only in the orientation of the permutation relative to the center cubies and represent the same void cube state. As facelet permutations neither of the two, indeed none of the twelve coset members, is an element of the void cube group. This element has odd position parity and is represented by an element of the super group outside of the standard cube group.

» login or register to post comments | previous forum topic | next forum topic

Comment viewing options

Select your preferred way to display the comments and click 'Save settings' to activate your changes.

Void Cube Distribution

Submitted by B MacKenzie on Mon, 03/28/2011 - 07:26.

Continuing to work with the void cube, I have found optimal q-turn solutions for a set of 1000 random cubes. Here is the distribution found:

Depth Count Percent
 16       2    0.2%
 17      10    1.0%
 18      81    8.1%
 19     334   33.4%
 20     417   41.7%
 21     156   15.6%
Ave 19.6
Trials 1000

This may be compared to the distribution found by Rokicki for the standard cube:

Depth    Count  Percent
  15q        7   0.0%
  16q      103   0.0%
  17q      870   0.1%
  18q    8,617   0.9%
  19q   69,284   6.9%
  20q  330,490  33.0%
  21q  430,142  43.0%
  22q  159,916  16.0%
  23q      571   0.1%
Ave  20.7
Trials 1,000,000

The distributions are remarkably similar—the two being offset ca. one q-turn from one another. With a slightly smaller early branching factor, ca. 9.27 for the void cube compared to ca. 9.35 for the standard cube, and a factor of 12 difference in the size of the state spaces, a difference of ca. one q-turns is about right.

» login or register to post comments

Void 3x3x3 cube naive question(s)

Submitted by secondmouse on Fri, 03/18/2011 - 04:22.
Can two adjacent colours (faces) be swapped?
What about two opposite colours (or faces, e.g. U and D)?
I suspect the answer is no in both cases but it would be good to have confirmation.

Are there any obvious physical constraints that would prohibit this that I have overlooked (assuming the answer is no)?
» login or register to post comments

Hypothetical dots patterns

Submitted by B MacKenzie on Fri, 03/18/2011 - 08:21.

The answer is no in both cases. Referring to the coloration of the commercial cube ( U=white, D=yellow, F=green, B=blue, R=red, L=orange) swapping the Up and Right face colors would require a white-green-yellow corner cubie for one. And swapping the colors of the Up and Down faces would require mirror image corner cubies. Listing the colors in clockwise order, you would need a white-green-red corner cubie as opposed to the normal white-red-green corner cubie.

Here is as close as one can get to swapping the Up-Down face colors:
R R U R L F B R L F' B' R' L' F' B' U' F F B' B' L' L'
» login or register to post comments

Void diameter in the QTM

Submitted by secondmouse on Fri, 03/18/2011 - 12:51.
Okay that was a pretty dumb question in retrospect. Let me ask a more challenging one. How about the manoeuvre in which two opposite colours or faces get swapped which is possible in the void?

I don't think this lends itself to the {U,F,R,TU,TF,TR} model you have provided for the void cube with DBL fixed.

But do you think it will be possible to reach these this position (3 in total considering symmetry) in < 26 moves using {U,F,R,D,B,L} (and of course any of the 24 rotational symmetries)?

This contradicts what I asserted in an earlier posting - perhaps these do come into play after all in the void cube? What does Rokicki have to say on this?

Part of the difficulty is agreeing on a standard set of generators which is more difficult without the centre spots as a frame of reference.
» login or register to post comments

Turn Sets

Submitted by B MacKenzie on Fri, 03/18/2011 - 16:01.

Let me ask a more challenging one. How about the manoeuvre in which two opposite colours or faces get swapped which is possible in the void?

The answer is the same as for the σh dots pattern. Swap the colors of the Up and Down faces on the void cube and you have a mirror image void cube. Can't be done.

I must reiterate that the < R , U , F , L , D , B > turn set is no different than the < R , U , F , TR , TU , TF > turn set. TR after all is the same as L CR. TR and L differ only in the orientation of the cube—one gives the cube rotated 90° wrt the other. Any turn sequence may be expressed in either system. For example the following two turn sequences yield the cube-in-cube pretty pattern:

R R U F R' TU F' U' TU F' R' TR F U F' TR' TU TU 
R R U F R' D  R' U' D  B' L' R  D B D' R'  D  D

Take two cubes and perform the two turn sequences side by side. Turn by turn the two cubes will be in the same state—but not necessarily in the same orientation. The standard turns perform the maneuver in a manner which keeps the center cubies unmoved and the other performs the turns in a manner which keeps the DLB cubie unmoved. Other than that, they are exactly the same.

The problem with using < R , U , F , L , D , B > on the void cube is that it is possible to produce the same void cube state in twelve different orientations. Using < R , U , F , TR , TU , TF > one always gets a particular cube state oriented in the same orientation. The latter situation allows one to analyze the states of the void cube as a mathematical group.

» login or register to post comments

You're right of course

Submitted by secondmouse on Sat, 03/19/2011 - 16:02.
I found my 3x3x3 cube today after a short separation and it quickly became obvious that no such position as I described can be possible in the void :-(
» login or register to post comments

Diameter of the void 3x3x3 cube

Submitted by secondmouse on Sun, 03/13/2011 - 07:38.
The void cube is not something that I have studied in any detail.
I have read the wikipedia page on this which at time of writing makes
no mention of the diameter w.r.t. Singmaster generators {U,F,R,D,B,L}.
But perhaps this is presumption on my part and it is preferable to keep the DBL cubelet fixed and use the generators you describe (which if I have understood correctly this is 3 mutually othogonal corner moves plus 3 corresponding slice moves).
But what is the current state of thinking re. diameter of the void using Singmaster moves - 24? The infamous centre spot + superflip of Reid at length 26 obviously does not come into play.
» login or register to post comments

Diameter

Submitted by B MacKenzie on Sun, 03/13/2011 - 08:38.

Rokicki addressed the diameter issue in this thread. He proved the diameter is at least 20 in the f-turn metric or 24 in the q-turn metric. Now that the cube diameter is proved to be 20 f-turns, this result can be carried over to the void cube. The task of determining the actual diameter for the void cube in the q-turn metric would be only slightly less daunting as that of the standard cube—the state space is still 3.6 x 1018.

Whether one models the problem as a coset space of the < R , U , F , L , D , B > group or as the < R , U , F , TR , TU , TF > group, one gets the same Cayley graph. There is a 1:1 mapping of turn sequences from one system to the other.

» login or register to post comments

Actual, Physical Void Cube

Submitted by Jerry Bryan on Fri, 03/11/2011 - 09:20.
Interesting that this message about the void cube just came in. I just purchased the first Rubik's cube of any sort that I have purchased in many years. And guess what, it's a void cube.

It looks very much like a standard 3x3x3 Rubik's cube except that the six face center cubies are missing and the invisible "center of the whole cube" cubie is missing. All that are there are the 8 corner cubies and the 12 edge cubies, for a total of 20 cubies. It's not like those other cubies are there and have had their color tabs peeled off or anything like that. The missing cubies really aren't there.

The most interesting thing about this gadget is how can it work and not fall apart. I have to confess that I have not yet full discerned what the mechanical mechanism is yet, except that for sure it is not magnets and it is not rubber bands. There appear to be little grooves that lock the cubies together. The grooves that, for example, connect the Front layer of cubies to the middle layer between the Front and Back layer form a circle and as you perform the move F the cubies in the Front layer follow this circle around.
» login or register to post comments

Void Cube

Submitted by B MacKenzie on Sat, 03/12/2011 - 17:40.
I did a void cube google a year ago after the void cube was mentioned on this forum. I got a couple of hits mentioning a commercial version such as you describe. My impression was that these originated in Japan. I was not aware it was available in the US.

Have you worked on solving it? Naively, one might suppose one could apply the same method one uses to solve the standard cube. I use a layer method. Applying this method, it occurs to me that one has a 50:50 chance of ending up with an odd parity permutation of the last layer which could not be solved using standard cube techniques.
» login or register to post comments

> Have you worked on solving

Submitted by Jerry Bryan on Sun, 03/13/2011 - 16:38.
> Have you worked on solving it? Naively, one might suppose one could
> apply the same method one uses to solve the standard cube. I use a
> layer method. Applying this method, it occurs to me that one has a
> 50:50 chance of ending up with an odd parity permutation of the last
> layer which could not be solved using standard cube techniques.

I have not yet tried solving it. But even so, it seems very clear that the same method used to solve the standard cube will work. It also seems very clear that the 50:50 chance that your layer method would fail really isn't true. In fact, nobody else's standard method would fail, either.

Well, you could create a situation where your method and everybody else's method would fail. To do so would require imposing a restriction on your solution that seems so picayune that almost no one would accept the restriction.

The issue is that a real, physical cube has a certain freedom that does not exit in a GAP model of the cube, nor in any other mathematical model of the cube. Namely, nearly everybody who works with a physical cube feels free to make full cube rotations without counting such rotations as moves. After all, full cube rotations do not change the positions of any of the cubies with respect to each other. But GAP models or other similar mathematical models do not have this freedom.

Let's take my newly purchased void cube in the solved state and position it such that red and orange are Front and Back, green and blue are Up and Down, and yellow and white are Left and Right. Second, let's rotate it "forward" by grasping the Right face and rotating the whole cube clockwise without displacing any of the cubies with respect to each other. At this point, the cube still looks solved. But blue and green are now Front and Back, red and orange are now Up and Down, and yellow and white are still Left and Right. Your task is to return the void cube to it's original state with red and orange as Front and Back, etc., making only moves from <F,B,U,D,L,R>. It can't be done.

But nobody would accept that restriction of using moves only from <F,B,U,D,L,R> because on a physical cube they would feel free to make whole cube rotations.  Or as a mathematically equivalent alternative, they would consider the cube to be solved if each of the six faces consisted of only one color, even if the colors were not in their original positions.

It's useful to think about this problem in terms of the original 3x3x3 Rubik's cube that's not void. As before, decide on a correspondence between the colors and the Front, Back, etc. directions. And as before before, give the cube a whole cube rotation that leaves it still looking solved.  Finally, try to solve the cube using only moves from <F,B,U,D,L,R>, where "solving" means restoring all the colors to their original positions. You clearly can't do so because all the moves in <F,B,U,D,L,R> fix the face centers, so the face centers will not be restored to their original positions. In this case, it's not even necessary to appeal to a parity argument as is necessary for the void cube. The subtle point about a GAP or other mathematical model is that as compared to a physical cube, all such models in effect establish a fixed correspondence between colors and directions.

Jerry

» login or register to post comments

Odd parity

Submitted by B MacKenzie on Sun, 03/13/2011 - 20:03.

No. I'm afraid the difficulty has nothing to do with whole cube rotations. Consider the standard cube. A void cube solution takes a scrambled cube to a member of the dots group, which are the states of the cube produced by applying the twelve tetrahedral rotations to the cubies. There are twelve more cubic group rotations which may be applied to the cubies to produce dots patterns. These patterns are forbidden because the states violate position parity.

So, take a standard cube and cover the center facelets with tape. Scramble it, an try to solve it by the layer method. On average, half the time one will end up with an odd parity permutation of the Up layer. What's going on? Take the tape off the center cubies. Whoops, one is trying to solve the cube by taking it to an odd parity dots pattern. To proceed, one could apply an odd parity MU q-turn. Now the cube should be soluble using the familiar even parity maneuvers.

Or, one can add a couple void cube single swap maneuvers to one's bag of tricks.

The recourse to referring to the center cubies is only necessary because we are all familiar with the standard cube. In the context of the group treatment outlined above the need for odd parity maneuvers is implicit in the mathematics of the void cube in and of itself.

» login or register to post comments

Well, I think we are both r

Submitted by Jerry Bryan on Mon, 03/14/2011 - 11:03.

Well, I think we are both right.  We are just coming at the problem from a little different direction.  But having said that, I think you are more right than I am. (grin!)

Your example of "taking a standard cube, covering the center facelets with tape, scrambling it, and trying to solve it ..." is great.  I have been assuming that for the purposes of this exercise, I would scramble the cube using only moves from <F,B,U,D,L,R>.  I have been assuming that having covered the center facelets, I would still remember or otherwise know the relationship between the colors and the directions (F, B, U, etc.).  And I have been assuming that neither during the scrambling process nor during the solving process, I would do anything to the cube that would disturb the locations of the now covered center facelets.  Under these circumstances, I do not run into any parity problems and the scrambled cube can be solved 100% of the time by making moves only from <F,B,U,D,L,R>.

But that's a lot of assuming.  And the excessive degree of assuming that I was doing is why I think you are more right than I am about this situation.  For example, you might scramble a standard 3x3x3 cube and tape over the center facelets as described without letting me watch what you are doing, and you might then toss the cube to me through the air - with the cube spinning as it is tossed.  If I then tried to solve the cube as if it were a standard 3x3x3 cube, I would fail about 50% of the time as you describe.  It would not matter whether I was using your layer method or some other method.  Any method that restricted itself to making moves only from <F,B,U,D,L,R> would have exactly the same problem.

As a clarification before we proceed, it should be pointed out that "solving the cube" in this context means getting all the corner and edge cubies in the proper position with respect to each other.  It does not mean getting them in the correct position with respect to the covered face centers.  Since you scrambled the cube without me seeing what you were doing, and since you tossed me the cube through the air to destroy any rotational orientation information for the cube as a whole, I don't have enough information to solve the cube properly with respect to the covered face centers.

So let's see if I can finagle a way to solve the cube with covered face centers 100% of the time using only moves from <F,B,U,D,L,R> rather than only being able to solve it 50% of the time using only moves from <F,B,U,D,L,R>.  In other words, I'm going to cheat, but what is the nature of that cheating?

After you tossed me a scrambled cube with the face centers covered, here is how I would solve it using only moves from <F,B,U,D,L,R>.

  1. I would agree with myself as to which face was Front, which face was Up, etc. I only have to choose any two adjacent faces, and the rest are automatically specified.  I now have a frame of reference.
  2. I would look at all the cycles of the corner cubies and edge cubies with respect to the chosen frame of reference to determine if there is a parity problem.  If there is not a parity problem, I would proceed to step #4.
  3. If I get to this step, I know that I have to do something to correct the parity of the overall cube.  Therefore, I would do something to the cube to rotate one of the middle layers by 90 degrees.  The "something" I would have to do to the cube would not be a move from <F,B,U,D,L,R>, so this step is sort of cheating.  But it's a necessary step.  There are three different ways to rotate one of the middle layers by 90 degrees.
    1. Rotate the whole cube by 90 degrees.  This step sounds counterintuitive because it does not change the position of any of the corner or edge cubies with respect to each other.  Therefore, it seems like it doesn't do anything.  But it changes the positions of all the corner and edge cubies with respect to the chosen frame of reference, and with respect to the chosen frame of reference the parity of the cube is thereby changed.  Or, ....
    2. Rotate any one of the three middle layers by 90 degrees.  This is the most intuitive way to change the parity of the cube.  Or, ....
    3. Rotate any single face layer and its associated middle layer by 90 degree.  I'm just including this option for completeness.  Rotating a single face layer by 90 degrees does not change the parity of the overall cube.  It changes the parity of the edges and it changes the parity of the corners, but those two parity changes cancel out.  It's the rotation of the middle layer that changes the parity of the over all cube
  4. Finally, I would solve the cube as usual while making moves only from <F,B,U,D,L,R>.  The only additional complication as compared to solving the standard 3x3x3 cube is deciding which colors correspond to which directions.  In the scenario where you have scrambled a cube, covered the face centers, and tossed me the cube to destroy any information about the rotational orientation of the entire cube, I would map colors to directions simply by choosing the current position and orientation of any one arbitrary corner cubie to be the correct position and orientation for that cubie.  Having done so, all the mappings between colors and directions would be completely specified.

Jerry

» login or register to post comments

Void Cube Algorithm

Submitted by B MacKenzie on Mon, 03/14/2011 - 19:16.

Since my last post I have hacked my Virtual Rubik program so as to not render the center cubies and fooled around solving the void cube. In my algorithm for manually solving the cube I first position the down layer edges in the proper order on a face picked at random. I then move a middle layer edge and a down layer corner into position to complete a 2x2x2 corner of the cube. At that point I've locked myself into either an even parity or an odd parity void cube permutation. This doesn't become apparent until the last step of my algorithm where I am left with either an even or an odd permutation of the Up layer corners. To correct an odd parity I have to rotate the the middle slice and reform the 2x2x2 block, which means I have to go back almost to square one. I can avoid this by applying a corner swap:

R U F' TR' U F' R' TF' TU' F TU TF R TU' TR F U'

» login or register to post comments