Discussions on the mathematics of the cube

An analysis of the corner and edge permutations of the 3x3x3 cube

I have generated a distance table using the quarter-turn metric for positions of the Rubik's cube (the standard 3x3x3 cube) where the orientation of the cubies is ignored. That is, the permutation of the corner cubies and the permutation of the edge cubies are considered, but not the orientation of either the edge or corner cubies. This is a set of 8!*12!/2 or 9,656,672,256,000 positions. To the best of my knowledge, this is (now) the largest "subset" of the 3x3x3 cube that this has been done for!

I used symmetry in the corner permutations, so that my programs "only" needed to store values for 984*12!/2 or 235,668,787,200 positions. The "real" size (considering symmetry in both the corner permutations and edge permutations) I found to be 201,181,803,792 positions. So about 17% of the stored positions are redundant with respect to the set of symmetrically distinct positions.

The 4x4x4 centres can be solved in 22 moves

In the yahoo speedcubing forum Chris Hardwick asked a question about analysis of solving the centres of the 4x4x4 cube. I felt that it was an easy thing to look at using my own solving program, so here are the results.

Finding God's Algorithm for the centres only was too hard a task since there are 24!/4!^6 = 3246670537110000 possible centre arrangements. I therefore split it into two stages.

First of all, solving 2 particular opposite centre colours on the 4x4x4 cube, placing them on any 2 opposite faces.

depth 0, positions 6, total 6
depth 1, positions 36, total 42
depth 2, positions 624, total 666

Exhaustive search of the cube space

I have been dabbling with the numbers and here is what I have come up with: Let's assume that Moore's law will hold for another X years. This is not unreasonable following advancements in parallel processor designs, quantum and biological computing. So, in X years according to this model, computers could have the potential computing power of N=2^(X/1.5) times the power of todays computers. If a respectable computer from today could optimally solve (considering the optimal solvers of today) a cube in 30 minutes (1800 seconds)...then a computer from this possible future could solve the cube in about 1800/N seconds. Now, assuming we were to hack away at this until these God computers came about, we would only net the equivalent of twice the computing time on these new computers, or about 36 months. This means that to solve the cube completely by time T in years, we would need to solve around 4.8 billion cubes/second. If we also consider farming this out to other computers of equivalent capabilities and enumerating the reduced cube space of 450541810590509978, then we can solve for a potential time frame on exhaustively searching the cube space.

Antisymmetry and enumeration of LL algorithms

I have been trying to enumerate all LL algorithms, (following Bernard Helmstetter's work) and cannot seem to reduce the 62208 permutations to the 1211 he has come up with. I am unaware of whether or not he used antisymmetry for his reductions. Using GAP and U rotations and reflections I have come up with a total of 8020. Initially considering antisymmetry as well (removing order 2 permutations and the identity from consideration. Note: I did not consider antisymmetric positions with dihedral symmetry or reflections) still does not bring it close to 1211. I was using Martin Schoenert's method in GAP and a very slow algorithm I wrote to determine equivalence classes from conjugation with a group (automorphism) separately with the same results. If anyone would like to see my definitions I will post them.

Inner Automorphisms and Outer Automorphisms

An automorphism (specifically, a group automorphism) is simply an isomorphism that is from a group to itself. Most authors define inner automorphisms and outer automorphisms roughly as follows.

An inner automorphism is an automorpism of the form p(g)=G^h=h'gh for all g in G and for a specific, fixed h in G. An outer automorphism is an automorphism that is not inner.

But occasionally the definition takes a slightly different form. The alternate definition says that automorphisms are of the form p(g)=G^h=h'gh for all g in G. If h is a fixed element of G, then p is an inner automorphism. Otherwise, h is not in G but rather is a fixed element of a larger group of which G is a subgroup, and p is an outer automormphism. The latter definition clearly motivates the names "inner" and "outer".

3x3x3 cube ignoring edge locations

Hello! (I am new to the group.)

I have done an analysis of the 3x3x3 Rubik's cube ignoring the locations of the edges (but not ignoring the orientations). That is, the locations and orientations of the corners were used, as well as the orientation of the edges. I used symmetry to reduce the number of positions from 180,592,312,320 to 3,772,354,560 (1,841,970 corner sym-coordinate values * 2048).

I have created files giving the distances for each of the positions of this problem space for the face-turn and quarter-turn metrics. I have listed the summary of the results I got below (where the numbers given are not symmetry-reduced). I was wondering if anyone has done this analysis before as I haven't been able to find any other such data on the internet to verify my results against.

Distance preserving automorphisms

I have several questions:

Have the number of distance preserving automorphisms of the Rubik's cube and/or Junior cube been counted/enmerated? Is there a way to count/enumerate them with GAP?

Thank you for your time,
-Joe Miller

Rubik's GAP file

Hello everyone!

I am a Senior student of Kent State studying permutation puzzles. (the cube in particular)

Here are the GAP definitions I use for analyzing the cube. I thought that maybe someone else would like to use it.

Notation: U2 is a 180 turn of the top layer, Uc is a 90 counterclockwise turn of the top layer.

U := ( 1, 3, 8, 6)( 2, 5, 7, 4)( 9,33,25,17)(10,34,26,18)(11,35,27,19);
U2 := U*U;
Uc := U2*U;
L := ( 9,11,16,14)(10,13,15,12)( 1,17,41,40)( 4,20,44,37)( 6,22,46,35);
L2 := L*L;
Lc := L2*L;
F := (17,19,24,22)(18,21,23,20)( 6,25,43,16)( 7,28,42,13)( 8,30,41,11);

New Results, 13 Moves from Start, Quarter Turn Metric

Previously, the number of positions out to 12 moves from Start had been calculated for the quarter turn metric. Patterns are the number of positions unique up to symmetry. This is not a new program or a new algorithm. It's just the old program on a faster machine with more memory.

Distance Patterns Positions
from
Start

0 1 1
1 1 12
2 5 114
3 25 1068
4 219 10011
5 1978 93840
6 18395 878880

Rubik's Cube antisymmetry and the shrinking of Cube Space

In this posting we introduce the concept of antisymmetry of Cube positions: antisymmetric positions include self-inverse positions as a special case. We show that the size of Cube Space is reduced by approximately a factor of 2 after taking account of positions that are related to one another by antisymmetry. The "new" real size of Cube Space is found to be 450541810590509978.

[Contribution also posted on sci.math]