[next] [prev] [up] Date: Sat, 07 Jan 95 20:04:09 -0500
[next] [prev] [up] From: michael reid <mreid@ptc.com >
[next] [prev] [up] Subject: two stage filtration

i've also run an exhaustive search on the subgroup
H = <U, D, F2, R2, B2, L2>. here are the number of
positions at each distance.

distance quarter turns face turns

 0                1                1
 1                4               10
 2               10               67
 3               36              456
 4              123             3079
 5              368            19948
 6             1192           123074
 7             3792           736850
 8            11263          4185118
 9            34352         22630733
10           102638        116767872
11           287320        552538680
12           810144       2176344160
13          2261028       5627785188
14          5941838       7172925794
15         16291708       3608731814
16         41973415        224058996
17        107458884          1575608
18        269542476             1352
19        628442876
20       1367654200
21       2613422312
22       3997726648
23       4444701268
24       3661653732
25       1906936668
26        407132392
27         34358944
28          1664168
29            14840
30              160

a position at distance 18 face turns was exhibited by hans kloosterman
on may 30 1992. (he also found three others that differ only in the
middle layer edges.) it was then observed by dik winter (also on may 30
1992) that kociemba's algorithm took exceptionally long for this position.
however, this does not appear to be the case for most of the antipodes.
(i will give the antipodes for each metric in separate messages.)

the 4 positions found by kloosterman are also antipodes in the quarter
turn metric, and, up to symmetry, are the only positions which are
antipodal in both metrics. hmmm...

elements of H are described by triples (c, e, m), where

c = corner permutation,
e = U D edge permutation,
m = middle layer edge permutation,

and the total parity is even. there are

8! = 40320 corner configurations,
8! = 40320 U D edge configurations and
4! =    24 middle layer edge configurations,
for a total of  40320 * 40320 * 24 / 2 = 19508428800  positions.

if we divide by symmetry along the corner coordinate, we get 2768 corner
configurations (of course we get the same number if we divide by symmetry
along the U D edge coordinate), so we can reduce to 1339269120 positions.
at 2 bits per configuration, this requires 327 megabytes, which is too
large.

however, if we also divide out by inversion, we can reduce the number of
corner configurations to 1672, the total number of positions to 808980480,
and the memory required to 200 megabytes. this is still a lot, but is
within reach.

the calculations were done on the same machine: DEC 3000 alpha 700,
configured with 256 Mb RAM. run times were much more modest:
10 hours for quarter turns, 7.5 hours for face turns.

mike


[next] [prev] [up] [top] [help]