Discussions on the mathematics of the cube

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.

http://www.physorg.com/news99843195.html

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.

Irreducible Loops

Some ideas for how to possibly proove that the diameter of the Cube-Group would be X.

Hi, I am new to the Cube problem, so probably the ideas are not new, or too naive, but I could not find them anywhere. This is possibly due to my lack of knowledge of terminology. (My background is theoretical solid states physics.)

Thus I would like to share these ideas with you, which you hopefully find useful, or can tell me that these ideas are not new or possibly that they are useless. I kindly ask you to comment. I just go ahead...

How could one calculate the diameter of the Group?

Let A be a random permutation. I start by choosing a (not optimal) path from id to A, say in quarter turn metric, with A=prod_i(ai) (i=1,...,N) where ai in {U,U',D,...}.

Welcome to my Blog

Hello, I am Peter Jung, a physicist from Cologne University.

Only a couple of days ago I got very much interested in the Cube. At wikipedia I found a note that the diameter of the Cube group is not yet known, and a link to this site.

Great work!

Sniffing into the problem, it seems to be quite complex. But some ideas that came to me these days I could not find. That's the purpose of this visit: To ask whether attempts have been made along these lines of thought, and if so, what is the outcome. And if not, I would like to contribute some analysis.

Antisymmetry and the 2x2x2 Cube

Someone on the Yahoo forum asked about how to do a 2x2x2 God's algorithm calculation and mentioned the "1152-fold" symmetry for the 2x2x2. I got to looking at some of the messages in the Cube-Lovers archives that Jerry Bryan had made about B-conjugation and the 1152-fold symmetry of the 2x2x2. He found that there were 77802 equivalence classes for the 2x2x2.

I have used antisymmetry to further reduce the number of equivalence classes for the 2x2x2 to 40296. The following table shows the class sizes of these equivalence classes.

class size  class size/24  count
----------  -------------  -----
     24           1            1
     48           2            1
     72           3            3
     96           4            1
    144           6           14
    192           8           11
    288          12           49
    384          16           22
    576          24          337
    768          32            6
   1152          48         3353
   2304          96        36498
                           -----
                  total    40296

I then performed God's algorithm calculations (HTM and QTM) to find the number of equivalence classes at each distance from the solved 2x2x2 cube. The results are given below. Because the 2x2x2 has no centers that provide a reference for the positions of the other cubies, the number of positions of the corners for the 2x2x2 (the only cubies it has) can be considered to be 1/24 the number of positions of the corners of the 3x3x3 (3674160 instead of 88179840). So in the tables below, I use the factor-of-24 reduced numbers for simplicity. The tables further break down the positions with respect to different class sizes.

Odd Permutations of the Cube Shape of Square-1

Results are presented from an exhaustive search on the odd permutations of Square-1 in its solved shape. A maximum of 31 turns (U, D and /) are needed to solve these positions, which may be a new lower bound on the length of God's Algorithm for Square-1, in this metric.

The method I used was suggested by Tom and Silviu's coset searches for the Rubik's Cube: Starting from a cube-shaped, odd-parity position of Square-1, an iterated depth-first search was made for all even-parity cube-shaped positions, with the search being pruned on [shape]x[parity].