Discussions on the mathematics of the cube

The 4x4x4 can be solved in 77 single-slice turns

Previously I announced that the 4x4x4 cube could be solved in 79 single-slice turns by solving it in five stages, in a manner similar to the Thistlethwaite 4-stage solution for the 3x3x3. (See The 4x4x4 can be solved in 79 moves (STM).) However, I have now realized my solution to the 2nd stage could have allowed the use of more basic turns than I used. I have realized that:
< U,u,D,d,L2,l2,R2,r2,F2,f,B2,b > = < U,u,D,d,L2,l,R2,r,F2,f,B2,b >
So with l and r replacing generators l2 and r2, you still can not reach any additional positions. As a result, I should have included the moves { l, l', r, r' } along with the other 24 allowed slice turns for that stage.

Rubik's cube can be solved in 34 quarter turns

I have proven that Rubik's cube can be solved in 34 quarter turns. The details can be found at:


UFR / UF Coset Space

Following up on an earlier thread I have explored the UFR/UF coset space. The number of UF cosets in the UFR group is given by:

(7 x 3) x (9 x 2) x (8 x 2) x 6 x 26 = 2,322,432

The first three factors are the number of ways the corner cubie position and the two edge cubie positions which are not on the UF faces may be configured. The factor of 6 is for the corner position permutation. Of the 720 corner position permutations on the UF faces achievable using the UFR face turns only 120 are achievable using the UF face turns. Thus the corner permutation may be one of six cosets. The flip of the seven UF edge cubies is constrained under the UF face turns, one cannot perform a double edge flip in this group. This gives rise to a factor of two to the sixth for the edge flip (flip parity determines the flip of the seventh edge cubie). As Bruce Norskrog pointed out in the earlier thread, the above number is the same as the order of the UFR group divided by the order of the UF group, so things check out.

Antisymmetry, Corners of the 3x3x3 Cube, quarter turn metric

Distance  Positions  Positions   Positions
 from                 reduced     reduced
 Start                  by           by
                      Symmetry    Symmetry

  0             1          1          1
  1            12          1          1
  2           114          5          5
  3           924         24         17
  4          6539        149         96
  5         39528        850        469
  6        199926       4257       2289
  7        806136      16937       8768
  8       2761740      57848      29603
  9       8656152     180787      91688
 10      22334112     466220     235710
 11      32420448     676786     342593
 12      18780864     392342     199610
 13       2166720      45600      23818
 14          6624        163        110

Total    88179840    1841970     934778

As I have written before, my programs have seldom worked with positions. They have nearly always worked with representative elements of M-conjugate classes. In the table above, the summary of representative elements is labeled "Positions Reduced by Symmetry". The goal of this approach is to obtain a 48 times speedup in processing time, and also to obtain a 48 times reduction in storage requirements.

Representation of edge permutations and move table

Stimulated by the last thread, where the representations of permutations and orientations was dealt I want to ask, what would be a good representation for the 12! edge permutations on the coordinate level, if the right multiplication of the edge permutation by any of the generators U,L.... should also be done with a MoveTable on the coordinate level like newcoordinate = MoveTable[oldcoodinate][generator].

This MoveTable would have 12!*18 4 Byte entries when we take the coordinate from 0..12!-1 and of course is far too big. Of course we could reduce this by 48 symmetries, but then we still would have a very large table.

Two Face Group

Has the Rubik cube subgroup generated by the turns of two orthogonal faces been exhaustively expanded? My computer runs out of physical memory and bogs down after 18 q turns:

Shell         Classes        Elements

0             1              1
1             1              4
2             3              10
3             6              24
4             15             58
5             35             140
6             85             338
7             204            816
8             493            1970
9             1189           4756
10            2863           11448
11            6862           27448
12            16324          65260
13            38550          154192
14            90192          360692
15            206898         827540
16            462893         1851345
17            992268         3968840
18            1973209        7891990

Totals        3792091        15166872

26f now claimed proven sufficient

It is now claimed proven that 26 face turns is sufficient to solve Rubik's Cube. I heard about this on the Yahoo speedsolving group forum. There is an article about it at the following link, which also contains a link for downloading the paper. That paper was written by two people at Northeastern University.


More on Branching Factors

I think it's useful to define branching factors for some other situations than are normally considered. For the most part, I'll speak to the quarter turn metric, but generalizations to the face turn metric are not hard to come by.

I was pretty sure that I posted an article to this site about Starts-With and Ends-With, but if so I can't find it. In any case, for a position x we define Starts-With(x) to be the set of moves with which a minimal process for x can start, and Ends-With(x) to be the set of moves with which a minimal process for x can end. If Ends-With(x)=Q (the set of quarter turns), then x is a local maximum. A similar formulation of the same idea is that if |Ends-With(x)|=12, then x is a local maximum.

Number of maneuvers for Rubik's Cube

By accident I just ran across a formula I developed many years ago for the number of maneuvers in FTM which cannot be shortened in a trivial way. I did not see it anywhere else, so maybe it is of some interest.

Let r = Sqrt(6) and k the maneuver length, then we have

N(k) = [(3+r)(6+3r)^n + (3-r)(6-3r)^n]/4

which gives 1, 18, 243, 3240, 43254, ...

Round[(3+r)(6+3r)^n] is a good approximation even for small n. and we see that 6+3r = 13.348... is the asymtotic branching factor.

Disjoint Cycles and Twist/Flip Parity Rules

I've been fooling around writing a virtual Rubik's cube program, initially simply as an exercise for teaching myself the Open GL 3D rendering API. In representing the puzzle I was led to assign each cublet an X,Y,Z coordinate specifying its starting position in the cube.
(-1,-1,-1) being the coordinate for the (left,down,back) cublet through to (1,1,1) being the coordinate for the (right,up,front) cublet. The transformed position and orientation of each cublet is then specified as an element of the O symmetry point group, there being a one to one correspondence between the 24 elements of the O point group and the 24 states a cublet may assume via Rubik cube face turns: 12 edge positions with two flip states each or 8 corner positions with 3 twist states each.