On 10/11/95 at 22:56:15 hoey@aic.nrl.navy.mil said:

But I can report that my search found 16 unique (*not* unique up to
conjugacy) half-way positions. I use the term "half-way" advisedly.
The "half-way" positions are 9q from Start and 8q from B or vice
versa. I guess you could say that the vice versa gives you a total
of 32=16+16 half-way positions, but the whole concept of "half-way"
is pretty slippery in this case anyway.

If I understand this, there are 16 positions at 9q from Start and 8q
from B, and there are 16 other positions at 8q from Start 9q from B.
Is each of the first bunch adjacent to exactly one of the other? And
vice versa? It would be good to get them reduced by Q2-conjugacy, as
well.

I don't think I can answer your questions without further analysis,
and I don't have much time to devote to the problem. But let me
clarify as follows. First, the search looked as follows:

Distance from     Distance from      Total       Number of
  Start                 B           Distance      Matching
                                                  Positions

0                   1             1               0
1                   2             3               0
2                   3             5               0
3                   4             7               0
4                   5             9               0
5                   6            11               0
6                   7            13               0
7                   8            15               0
8                   9            17              16

There is a certain arbitrariness in at least two respects. For one
example, to test for a total distance of 11, you could just as well use
distances from Start and B respectively of 4 and 7 instead of 5 and 6.
For another example, the Start-rooted tree and the B-rooted tree have
identical structures, so the first two columns could be reversed.
Indeed, you could get the B-rooted tree simply by pre-multiplying the
Start-rooted tree by B. (This reminds me of one of my most
foolish errors on Cube-Lovers. For search trees where the nodes are
conjugacy classes (or representatives of conjugacy classes), the
tree looks different depending on which class or representative is at
the root. But when the nodes are all the positions, then the tree is
essentially the same in all cases, just pre-multiplied by the root.
I once claimed the tree structure depended on the root for trees
containing all positions, confusing that situation with the situation
for trees of conjugacy classes. Arrg!)

Hence, I am not especially comfortable talking about "half-way" positions.
But continuing anyway, denote the 16 positions which are 8 moves from
Start and 9 moves from B as X_i for i in 1..16. Then, the 16 positions
which are 8 moves from B and 9 moves from Start are B(X_i) for i
in 1..16. A solution to the problem would then look something like
(X_j)Y(X_k)', where Y is in Q-{B,B'}. But I don't think we can say
a priori that there is no Z in Q-{B,B'} and no X_m such that
(X_j)Z(X_m)' is also a solution (Z not equal Y and X_m not equal X_k).

I think to analyze the problem properly you would have to take the
positions X_i for i in 1..16 and the positions B(X_j) for j in 1..16
and match up each X_i with each B(X_j) to see which ones differ
by a quarter turn. Each X_i is going to match up with at least one
B(X_j) and vice versa, but there might be more than 16 matches
overall.

Reduction by Q2-conjugacy is important, but I don't think it would
tell you how many solutions there are that you would really want to
consider to be unique. Recall the solution of Pons Asinorum by
half-depth searches. There are 5 positions unique up to M-conjugacy
which are 6q from Start and 6q from Pons. But most people would
consider that there are only two minimal solutions to Pons that are
really different. The trouble is that 4 of the 5 half-way positions
for the Pons are in the middle of a sub-process which commutes.

 = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
Robert G. Bryan (Jerry Bryan)                        (304) 293-5192
Associate Director, WVNET                            (304) 293-5540 fax
837 Chestnut Ridge Road                              BRYAN@WVNVM
Morgantown, WV 26505                                 BRYAN@WVNVM.WVNET.EDU