kociemba's algorithm uses the filtration

G = <U, D, F, R, B, L>        of order   43252003274489856000
H = <U, D, F2, R2, B2, L2>    of order            19508428800
1 = <>                        of order                      1

i've run an exhaustive search on the coset space G / H. the number
of cosets at each distance is:

distance quarter turns face turns

 0                1                1
 1                4                4
 2               34               50
 3              312              592
 4             2772             7156
 5            24996            87236
 6           225949          1043817
 7          2017078         12070278
 8         17554890        124946368
 9        139132730        821605960
10        758147361       1199128738
11       1182378518         58202444
12        117594403              476
13            14072

the computation for face turns was already done by dik winter (see his
message of may 28, 1992), so in particular, this confirms his calculation.

the cosets G / H are described by triples (c, e, l), where

c = corner orientation
e = edge orientation
l = location of middle layer edges (FR, FL, BR, BL)

there are  3^7   = 2187 corner configurations,
           2^11  = 2048 edge configurations, and
          / 12 \
          \  4 / =  495 location configurations,

to give a total of 2187 * 2048 * 495 = 2217093120 configurations.
to reduce this number somewhat, we can utilize symmetry. there are 16
symmetries of the cube that preserve the U-D axis, and therefore
preserve the subgroup H. up to these symmetries, the number of distinct
corner configurations is 168, so we need only consider a mere
168 * 2048 * 495 = 170311680 configurations.

(so far, this is the same approach that dik used for his calculation.)

each configuration is stored with 2 bits of memory and thus the whole
space consumes about 42 megabytes. each configuration is assigned
one of 4 values:

distance is currently unknown
distance = current search depth
distance = current search depth - 1
distance < current search depth - 1

from here, i just used a simple breadth first search.

unfortunately, something unpleasant happened along the way ...

at some point, i realized that the symmetries do not act on the edge
configurations. to define edge flip, one must choose one facelet from
each of the 4 middle layer edges to correspond to the U or D facelet
of the other 8 edges. (i chose the F and B facelets, but this is
completely arbitrary.) but now we've lost some symmetry; these 12 facelets
are not preserved under the 16 symmetries, in particular, the rotation
C_U does not preserve them.

therefore, we need lookup tables for the action of the symmetries on
edge x location space. this gives 16 symmetries * 2048 edge configurations
* 495 location configurations * 4 bytes per integer = 64 megabytes of
lookup tables. ouch!

i was too far along at this point to start all over, and i had the memory
available, so i just continued with this approach. however, in hindsight,
i'd probably use one of the following ideas if i had to start over:

i) only use the 8 symmetries that preserve my choice of
12 edge facelets.

ii) combine the two coordinates edge and location into a single
coordinate and divide this coordinate by the 16 symmetries.

run times were improved significantly by using a simple trick that i hadn't
used in earlier programs. during the first few depth levels, i use
"forward searching", i.e. i examine the neighbors of each configuration
found at the previous depth. however, after at least half the search space
has been found, i switch to "backward searching", i.e. examine the
configurations (and their neighbors) that haven't yet been found.

(have others been using this same idea when running similar search programs?)

closer analysis of this technique suggests that the switch from forward to
backward searching should occur even before half the space has been found.
i didn't do this here since the run times were quite satisfactory:
40 minutes for quarter turns, 47 minutes for face turns. this was done
on a DEC 3000 alpha 700, apparently a very fast machine.

mike