Discussions on the mathematics of the cube

New estimate for 20f*: 300,000,000

Over the past few weeks I've run 250 random cosets of the Kociemba group, each with 19,508,428,800 positions, out to completion, calculating an optimal solution to all. This is a total of 4,877,107,200,000 positions, almost all unique modulo M+inv. I ran these to try to get a better estimate of the total count of 20f* positions and also to compare the overall histogram of position depths against my previous work to calculate the exact count of 13f* positions, and Kociemba's recent experiment to optimally solve a one hundred thousand random cube positions.

Of these 250 random cosets, 232 had absolutely no distance-20

Syllables and Graphs

I've been reading a little bit about graph theory, and I wish I knew more about it.  So pardon what may perhaps be a bit of naiveté about graphs on my part.

I suspect that everyone who reads this forum is familiar with Cayley graphs and how they relate to Rubik's cube space.  One of the best references in this regard may be found at http://www.jaapsch.net/puzzles/cayley.htm  I also suspect who everyone reads this forum is familiar with the concept of doing a breadth first search while storing all the results as a way of investigating a space such as the Cayley graph for Rubik's cube.

Fast solver for arbitrary target groups

As you know one of the breakthrough of cube computing is Silviu's successful depth calculation of all symmetrical positions. This breakthrough used a two phase algorithm that has the symmetrical positions as its target group. Regular solvers will simply stop once they hit the position they want to solve but Silviu's idea is to never stop until all positions in the target group are hit... This way of solving is very fast and it is what Rokiki has used to calculate the "group that fixes the edges".

My question is can this be applied to arbitrary target groups whose elements share something in common? for example let's say my target group is some conjugacy class of the cube.

DFS

I modified kociemba's optimal solver so that it calculates the depth of sequences in a Depth-first search manner.

The moves order I used is URFDLBU'R'F'D'L'B'.

Here are the initial results after an hour or so of running :
./optiqtm
initializing memory.
initializing tables.........................................................
loading pruning table (538 MB) from disk................
                                 U
-1                               UU
--2                              UUR
---3                             UURU
----4                            UURUU
-----5                           UURUUR
------6                          UURUURU
-------7                         UURUURUU
--------8                        UURUURUUR
---------9                       UURUURUURU
----------10                     UURUURUURUU
-----------11                    UURUURUURUUR
------------12                   UURUURUURUURU
-------------13                  UURUURUURUURUU
-------------14                  UURUURUURUURUUR
---------------15                UURUURUURUURUURU
----------------16               UURUURUURUURUURUU
---------------15                UURUURUURUURUURUR
---------------15                UURUURUURUURUURUF
---------------15                UURUURUURUURUURUD
---------------15                UURUURUURUURUURUL
-----------------17              UURUURUURUURUURULU
----------------16               UURUURUURUURUURULR
----------------16               UURUURUURUURUURULF
------------------18             UURUURUURUURUURULFU
-----------------17              UURUURUURUURUURULFR
-----------------17              UURUURUURUURUURULFF
-----------------17              UURUURUURUURUURULFD
-----------------17              UURUURUURUURUURULFL
-----------------17              UURUURUURUURUURULFB
-------------------19            UURUURUURUURUURULFBU
------------------18             UURUURUURUURUURULFBR
------------------18             UURUURUURUURUURULFBF
------------------18             UURUURUURUURUURULFBD
--------------------20           UURUURUURUURUURULFBDU
-------------------19            UURUURUURUURUURULFBDR
-------------------19            UURUURUURUURUURULFBDF
-------------------19            UURUURUURUURUURULFBDD
-------------------19            UURUURUURUURUURULFBDL
-------------------19            UURUURUURUURUURULFBDB
-------------------19            UURUURUURUURUURULFBDU'
-------------------19            UURUURUURUURUURULFBDR'
-------------------19            UURUURUURUURUURULFBDF'
-------------------19            UURUURUURUURUURULFBDL'
-------------------19            UURUURUURUURUURULFBDB'
-------------------19            UURUURUURUURUURULFBL
------------------18             UURUURUURUURUURULFBB
------------------18             UURUURUURUURUURULFBU'
------------------18             UURUURUURUURUURULFBR'
--------------------20           UURUURUURUURUURULFBR'U
-------------------19            UURUURUURUURUURULFBR'F
-------------------19            UURUURUURUURUURULFBR'D
-------------------19            UURUURUURUURUURULFBR'L
-------------------19            UURUURUURUURUURULFBR'B
---------------------21          UURUURUURUURUURULFBR'BU
--------------------20           UURUURUURUURUURULFBR'BR
--------------------20           UURUURUURUURUURULFBR'BF
--------------------20           UURUURUURUURUURULFBR'BD
--------------------20           UURUURUURUURUURULFBR'BL
--------------------20           UURUURUURUURUURULFBR'BB
--------------------20           UURUURUURUURUURULFBR'BU'
--------------------20           UURUURUURUURUURULFBR'BR'
--------------------20           UURUURUURUURUURULFBR'BF'
--------------------20           UURUURUURUURUURULFBR'BD'
--------------------20           UURUURUURUURUURULFBR'BL'
--------------------20           UURUURUURUURUURULFBR'U'
-------------------19            UURUURUURUURUURULFBR'R'
-------------------19            UURUURUURUURUURULFBR'F'
-------------------19            UURUURUURUURUURULFBR'D'
-------------------19            UURUURUURUURUURULFBR'L'
-------------------19            UURUURUURUURUURULFBR'B'
-------------------19            UURUURUURUURUURULFBF'
------------------18             UURUURUURUURUURULFBD'
------------------18             UURUURUURUURUURULFBL'
--------------------20           UURUURUURUURUURULFBL'U
-------------------19            UURUURUURUURUURULFBL'R
-------------------19            UURUURUURUURUURULFBL'F
---------------------21          UURUURUURUURUURULFBL'FU
--------------------20           UURUURUURUURUURULFBL'FR
--------------------20           UURUURUURUURUURULFBL'FF
--------------------20           UURUURUURUURUURULFBL'FD
--------------------20           UURUURUURUURUURULFBL'FL
--------------------20           UURUURUURUURUURULFBL'FB
--------------------20           UURUURUURUURUURULFBL'FU'
----------------------22         UURUURUURUURUURULFBL'FU'U
---------------------21          UURUURUURUURUURULFBL'FU'R
---------------------21          UURUURUURUURUURULFBL'FU'F
---------------------21          UURUURUURUURUURULFBL'FU'D
---------------------21          UURUURUURUURUURULFBL'FU'L
---------------------21          UURUURUURUURUURULFBL'FU'B
---------------------21          UURUURUURUURUURULFBL'FU'U'
---------------------21          UURUURUURUURUURULFBL'FU'R'
---------------------21          UURUURUURUURUURULFBL'FU'F'
---------------------21          UURUURUURUURUURULFBL'FU'D'
---------------------21          UURUURUURUURUURULFBL'FU'L'
---------------------21          UURUURUURUURUURULFBL'FU'B'
---------------------21          UURUURUURUURUURULFBL'FR'
--------------------20           UURUURUURUURUURULFBL'FD'
--------------------20           UURUURUURUURUURULFBL'FL'
--------------------20           UURUURUURUURUURULFBL'FB'
--------------------20           UURUURUURUURUURULFBL'D
---------------------21          UURUURUURUURUURULFBL'DU
--------------------20           UURUURUURUURUURULFBL'DR
--------------------20           UURUURUURUURUURULFBL'DF
--------------------20           UURUURUURUURUURULFBL'DD
--------------------20           UURUURUURUURUURULFBL'DL
--------------------20           UURUURUURUURUURULFBL'DB
--------------------20           UURUURUURUURUURULFBL'DU'
--------------------20           UURUURUURUURUURULFBL'DR'
--------------------20           UURUURUURUURUURULFBL'DF'
--------------------20           UURUURUURUURUURULFBL'DL'
--------------------20           UURUURUURUURUURULFBL'DB'
--------------------20           UURUURUURUURUURULFBL'B
-------------------19            UURUURUURUURUURULFBL'U'
-------------------19            UURUURUURUURUURULFBL'R'
-------------------19            UURUURUURUURUURULFBL'F'
-------------------19            UURUURUURUURUURULFBL'D'
-------------------19            UURUURUURUURUURULFBL'L'
-------------------19            UURUURUURUURUURULFBL'B'
-------------------19            UURUURUURUURUURULFU'
-----------------17              UURUURUURUURUURULFR'
-----------------17              UURUURUURUURUURULFD'
-----------------17              UURUURUURUURUURULFL'
-------------------19            UURUURUURUURUURULFL'U
------------------18             UURUURUURUURUURULFL'R
------------------18             UURUURUURUURUURULFL'F
--------------------20           UURUURUURUURUURULFL'FU
-------------------19            UURUURUURUURUURULFL'FR
-------------------19            UURUURUURUURUURULFL'FF
-------------------19            UURUURUURUURUURULFL'FD
-------------------19            UURUURUURUURUURULFL'FL
---------------------21          UURUURUURUURUURULFL'FLU
--------------------20           UURUURUURUURUURULFL'FLR
--------------------20           UURUURUURUURUURULFL'FLF
--------------------20           UURUURUURUURUURULFL'FLD
--------------------20           UURUURUURUURUURULFL'FLL
--------------------20           UURUURUURUURUURULFL'FLB
--------------------20           UURUURUURUURUURULFL'FLU'
--------------------20           UURUURUURUURUURULFL'FLR'
--------------------20           UURUURUURUURUURULFL'FLF'
--------------------20           UURUURUURUURUURULFL'FLD'
--------------------20           UURUURUURUURUURULFL'FLB'
--------------------20           UURUURUURUURUURULFL'FB
-------------------19            UURUURUURUURUURULFL'FU'
-------------------19            UURUURUURUURUURULFL'FR'
-------------------19            UURUURUURUURUURULFL'FD'
-------------------19            UURUURUURUURUURULFL'FL'
-------------------19            UURUURUURUURUURULFL'FB'
-------------------19            UURUURUURUURUURULFL'D
------------------18             UURUURUURUURUURULFL'B
------------------18             UURUURUURUURUURULFL'U'
------------------18             UURUURUURUURUURULFL'R'
------------------18             UURUURUURUURUURULFL'F'
------------------18             UURUURUURUURUURULFL'D'
------------------18             UURUURUURUURUURULFL'L'
------------------18             UURUURUURUURUURULFL'B'
------------------18             UURUURUURUURUURULFB'
-----------------17              UURUURUURUURUURULD
------------------18             UURUURUURUURUURULDU
-----------------17              UURUURUURUURUURULDR
-------------------19            UURUURUURUURUURULDRU
--------------------20           UURUURUURUURUURULDRUU
-------------------19            UURUURUURUURUURULDRUR
-------------------19            UURUURUURUURUURULDRUF
-------------------19            UURUURUURUURUURULDRUD
-------------------19            UURUURUURUURUURULDRUL
-------------------19            UURUURUURUURUURULDRUB
-------------------19            UURUURUURUURUURULDRUR'
-------------------19            UURUURUURUURUURULDRUF'
-------------------19            UURUURUURUURUURULDRUD'
-------------------19            UURUURUURUURUURULDRUL'
-------------------19            UURUURUURUURUURULDRUB'
-------------------19            UURUURUURUURUURULDRR
------------------18             UURUURUURUURUURULDRF
------------------18             UURUURUURUURUURULDRD
------------------18             UURUURUURUURUURULDRL
------------------18             UURUURUURUURUURULDRB
------------------18             UURUURUURUURUURULDRU'
------------------18             UURUURUURUURUURULDRF'
------------------18             UURUURUURUURUURULDRD'
------------------18             UURUURUURUURUURULDRL'
------------------18             UURUURUURUURUURULDRB'
------------------18             UURUURUURUURUURULDF
-----------------17              UURUURUURUURUURULDD
-----------------17              UURUURUURUURUURULDL
-----------------17              UURUURUURUURUURULDB
-----------------17              UURUURUURUURUURULDU'
-----------------17              UURUURUURUURUURULDR'
-----------------17              UURUURUURUURUURULDF'
-------------------19            UURUURUURUURUURULDF'U
------------------18             UURUURUURUURUURULDF'R

Commutator elements of the cube

I was wondering if the number of commutator elements of the cube is known?

Commutator elements are of the form ABA'B' where A and B are some sequences.

It seems that the subgroup generated by the commutator elements is half the size of the cube, but is it the case that every element of the commutator subgroup is a commutator element? if not how many are they and how far they are from solved?

Conjugacy classes of the cube

I was reading the following :

http://en.wikipedia.org/wiki/Conjugacy_class

and wondered if the number of conjugacy classes of the cube is known?

Challenge with three faces

Ok, I think you all can solve the cube without thinking. So here is a new challenge. First scramble the cube. Next, make the 2x2x2 cube on your 3x3x3 cube. After that, solve the rest of the cube by using three faces only. I can tell you that I know plenty of tricks to solve the cube, but only just enough remain to when you are restricted to three mutually adjacent faces.

Linear formula

Let's assume that there is a linear formula that gives us P(n) using P(k) where 0 <= k <= n-1. P(n) is the number of positions at depth n.

We have then the following formula:

P(n) = sum(R(k)*P(n-k)) for 1 <= k <= n

Calculating R(k) using rokiki's results we deduce :

 1 12                   = 12*1                   
 2 114                  = 12*12                  -30*1                   
 3 1068                 = 12*114                 -30*12                  +60*1                   
 4 10011                = 12*1068                -30*114                 +60*12                  -105*1

Algorithm for Counting Identities

I've been thinking about writing a program to calculate and count duplicate positions - roughly speaking, those positions that are half way through an identity.  What I have in mind will probably be a more time consuming program to write than I would prefer.  So I wonder if I could ask Herbert Kociemba and/or mdlazreg to post a little something about the programs they have already written to find identities.  It may well be that there is a much simpler approach to calculating duplicate positions than what I have in mind.

What I have in mind is an iterative deepening depth first search beginning at the Start position.  If that's all I did, the search would simply count 12n maneuvers for each distance from n, and it would not extract any useful information about how many duplicate positions there are for each n.  To solve these problems, I propose to store all the duplicate positions and not to store those positions that are not duplicate.  This would be for the quarter turn metric.  The program I have in mind would not be able to handle the face turn metric.

God's algorithm for FTM mod 48, 2. Try

In FTM the complete knowledge of the distribution of the symmetric subgroups (first table of http://kociemba.org/symmetric2.htm ) lets us not only give the odd and even entries in the distance table but also the distances mod 48, because all unsymmetric position contribute with a multiple of 48. So we get

distance   positions mod 48

   0              1
   1             18
   2              3
   3             24
   4             39
   5             12
   6             22
   7             12
   8             40
   9              3
  10              4
  11             20