Discussions on the mathematics of the cube

Orientation of pieces in permutation puzzles

The goal is to provide a general statement about the orientations of pieces of a certain permutation puzzles. Since there are so many different kinds of permutation puzzles we will have to exactly describe the properties of the puzzles for which the statement will be valid. We also will have to explain how the orientation of pieces can be measured for these puzzles in way as general as possible.

Then we are able to show that under these assumptions for a given kind of pieces with k possible orientations the sum of the orientations of all these pieces module k is invariant under permutations.

We restrict our consideration to permutation puzzles which do not change their shape. We call the moving parts of the puzzle the pieces and the locations of the pieces the places of the pieces. For three-dimensional puzzles we assume that the pieces are polyhedrons which are bounded by faces, for two- dimensional puzzles we assume that the pieces are polygons which are bounded by a circuit of edges. Since our main goal is the examination of three-dimensional puzzles we only use the term "faces" in the following text, but it could be replaced by "edges" to handle the two-dimensional case.

We further assume that at least some pieces can occupy their places in different positions/orientations. Since we restrict to puzzles which do not change their shape, these pieces must have at least one axis of rotational symmetry. We restrict our consideration to puzzles where the different orientations of a piece are defined by exactly one axis of rotational symmetry of order k (which does not seem to be a significant restriction). In this case we pick an arbitrary face which is not fixed by the symmetry and name it f_0. A counter clockwise (as seen from outside the puzzle) rotation by 2Pi/k*j, 1<=j<k, then maps f_0 to another face, which is denoted by f_j. The faces f_0, f_1, f_2... may be visible or not. The faces f_0, f_1 and f_2 of a Rubik's cube corner are for example visible while for the centre pieces of a 4x4x4 cube the faces f_0, f_1, f_2 and f_3 are not visible.

To define the orientation of a given piece at any possible place in any possible position we define a reference frame for the orientations. The geometric positions of the faces f_0, f_1... of a piece at a certain place of the puzzle we call slots. It is important to emphasize that only the faces move when a permutation is applied, not the slots. Applying a permutation, the slots of the places just are "filled" with the faces f_0, f_1... of a different piece of the same kind. Now we arbitrarily choose exactly one slot of every place to and call it the reference slot. We say that the orientation of a piece in this place is i if the reference slot is filled with the face f_i of that piece.

A move M of the puzzle is a permutation of some of its pieces. We hardly can establish any statement about the orientations of the pieces if there is no restriction on the permutations. We call a place P M-unambiguous if applying move M one or several times we cannot have the same piece in different orientations in place P. A place which does not have this property we call M-ambiguous. For example, for all nxnxn Rubik's cubes all places are X- unambiguous for all conceivable moves X except for odd n in the places where the face diagonals meet.

A move M usually affects several pieces and places. If we choose a piece p at a place P_0 this piece p usually visits several places P_0,P_1,... if we apply the move M several times. All the pieces which occupy these places form the M-orbit of p. All these pieces have the same shape as p and the involved places P_0, P_1... are all M-unambiguous or all M-ambiguous. The orbits of any piece of nxnxn Rubik's cube except the centre piece for odd n consist of 4 pieces for example.

With these preliminary considerations we are now able to establish the following proposition:

Proposition 1: Let M be a move of a permutation puzzle which does not change its shape and p a piece with a single k-fold rotational symmetry in a M-unambiguous place P. Then the sum of the orientations of all pieces in the orbit of p does not change its value modulo k if M is applied.

Proof: We name the involved places and slots in a way that it is easy to keep track of the orientations when the move M is applied. The place of piece p is named by P_0, the slot which is filled by face f_i (0<=i<k) of p is referred to as slot_i. Let the size of the M-orbit of p be s. Then applying M j times (0<j<s) moves piece p to a place which we call P_j. The slots of P_j are denoted in the same way as for P_0, using the faces of p – now in place P_j - again as a reference to name the slots. Named in this way we can make the following observation in the table which describes the faces of all pieces of the orbit in the slots of their place:

The faces in the slots of P_0 are well defined by the definition of the slot names. For other places, place P_2 for example we neither know the piece in P_2 nor the face in slot_1 but since the faces of all pieces in the orbit are named in the same way counter clockwise we know that we have face_(a+1) mod k in slot_2 of P_2 and face_(a+2) mod k in slot_3 of P_2.

And most important, in the way the slots and places are named, if we apply move M all entries of the table are cyclically shifted one line down, the entries of line P_(s-1) move to line P_0 (this would not work if the places would be M-ambiguous).

With the following example we show that the sum of the orientations modulo k does not change when applying move M. The orientations are defined by the reference slots which can in principle be chosen arbitrarily, they are highlighted in the example below. Obviously there has to be one reference slot in a line, but for the number of reference slots in a column there are no restrictions.

Before applying move M:

According to the definition of the orientations the sum of the orientations in the orbit modulo k is

26 QTM Moves Suffice

Finally we have shown that 26 or fewer moves suffice to solve any position
of the Rubik's Cube in the Quarter-Turn Metric.

We put up a page with basic information at cube20.org/qtm.

I'm starting this forum topic for discussion; sorry I did not post this when
we made the announcement!

Lower bounds for the 3x3x3 Super Group

For quite a while I was looking for an optimal solution for the 'Pure Superflip' (a Superflip pattern were all centers remain untouched). Such an algorithm would also allow to define the lower bound for the 3x3x3 Super Group. I don't know if there already exist lower and upper bounds for this cube group.

Years ago I computed all optimal solutions of the 'Superflip' pattern in ftm (face turn metric) to see if any of the 4416 algorithms may leave the centers unchanged. Unfortunately all these algorithms twist either 4 or 5 of the centers.

I figured out that such an algorithm must be within the range of 23 and 24 moves, but I never was able to prove it. It took just too long for solvers these days to compute a solution.

God's Algorithm out to 18q*: 368,071,526,203,620,348

Almost exactly four years after 17q* was announced by Thomas
Schuenemann, we have calculated the number of positions at a distance
of exactly 18 in the quarter-turn metric. This is more than one in
twenty positions.

This number matches (mod 48) the count of distance-18 symmetric
positions; this provides a bit of confirmation that it is correct
(or rather, about 5.6 bits of confirmation).

The approach we used does not permit us to calculate the number of
positions mod M or mod M+inv without significantly increasing the
amount of CPU required; these computations will have to wait for

Fifteen Puzzle MTM

I wrote a fifteen puzzle simulation back in 2010 which I recently went back to and updated before submitting it as freeware to the Apple App Store.

Playing around, I then plugged my model into my coset solver framework and performed a states at depth enumeration in the multi-tile metric out to depth 23:

XV Puzzle Enumerator Client(bdm.local)

XV Coset Solver
	Fixed tokens in subgroup: 0, 1, 2, 3, 4, 8, 12, 15.
	518,918,400 cosets of size 20,160

Cosets solved since launch: 165,364,141
Average time per coset: 0:00:00.001

Server Status:
XV Puzzle Enumerator Server
Enumeration to depth: 23

Snapshot: Thursday, June 12, 2014 at 11:11:29 AM Central Daylight Time

 Depth             Reduced             Elements
   0                     1                    1 
   1                     3                    6 
   2                    11                   18 
   3                    29                   54 
   4                    87                  162 
   5                   253                  486 
   6                   752                1,457 
   7                 2,213                4,334 
   8                 6,379               12,568 
   9                18,205               36,046 
  10                51,785              102,801 
  11               145,489              289,534 
  12               405,728              808,623 
  13             1,118,586            2,231,878 
  14             3,043,537            6,076,994 
  15             8,153,139           16,288,752 
  16            21,464,200           42,897,301 
  17            55,475,870          110,898,278 
  18           140,272,410          280,452,246 
  19           346,202,190          692,243,746 
  20           831,610,844        1,662,949,961 
  21         1,938,788,875        3,877,105,392 
  22         4,370,165,315        8,739,560,829 
  23         9,490,811,983       18,980,345,944 

 Sum        17,207,737,884       34,412,307,411 

518,918,400 of 518,918,400 cosets solved

27 QTM Moves Suffice

Every position of the Rubik's Cube can be solved in at most
27 quarter turns.

This work was supported in part by an allocation of computing time
from the Ohio Supercomputer Center. It was also supported by
computer time from Kent State University's College of Arts and
Sciences. In order to obtain this new result, 25,000 cosets of
the subgroup U,F2,R2,D,B2,L2 were solved to completion, and
34,000,000 cosets were solved to show a bound of 26. No new
positions at a distance of 26 or 25 were found in the solution
of all of these cosets.

Twenty-Eight QTM Moves Suffice

Every position of the Rubik's Cube can be solved in at most
28 quarter turns. The hardest position known in the quarter-turn
metric requires only 26 moves, so this upper bound is probably
not tight.

This new upper bound was found with the generous donation of
computer time from Kent State University's College of Arts and
Sciences. In order to obtain this new result, 7,000 cosets of
the subgroup U,F2,R2,D,B2,L2 were solved to completion. Each
coset took approximately an hour on a 6-core Intel CPU. No new
positions at a distance of 26 or 25 were found in the solution
of all of these cosets.

2x2x2 Cube

I recently added the 2x2x2 cube to my Virtual Rubik app. Playing around with the code I threw together a breadth first god's algorithm calculation using anti-symmetry reduction. This is old stuff but I thought I would post the results just the same.

2x2x2 States At Depth
Depth   Reduced(Oh+)       States
 0             1             1
 1             1             6
 2             3            27
 3             4           120
 4            13           534
 5            35         2,256
 6           126         8,969
 7           398        33,058
 8         1,301       114,149
 9         3,952       360,508
10        10,086       930,588
11        14,658     1,350,852
12         8,619       782,536
13         1,091        90,280
14             8           276
15             0             0

Group Order: 3,674,160

  1 R R U R F R' U R R U' F U' F' U'

  2 R R U R R F' U R F' R F' U R' F'

  3 R R U R' U F U' R F R' U' R U R

  4 R R U F F R' U' R F' R F' U U F

  5 R R U R' F R R U' R F R' U R R

  6 R R U R R U F U' R F' U R U' R

  7 R R U R R U' R F' U R' U R U U

  8 R U R R F' R F R U' F' U R U' F

Old Domain Names now restored

Hi Everybody,

I've re-activated the old domain names cubezzz.dyndns.org and cubezzz.homelinux.org so all the old links to the Domain of the Cube forum should be working now.

Now that I've thought about it more it actually feels good to get the original URL working again.

You can all thank Tom for coaxing me into it. I still wish dyndns.org could have helped us more, but I guess you get what you pay for.


Domain name changed (again)

Hi folks,

I'm reverting back to http://cubezzz.dyndns.org/drupal

The other URLs should also work but this one is the canonical URL for the cube forum.

Note that it should also be possible to access the forum directly via