Date: Sat, 07 Jan 95 20:24:35 -0500
From: michael reid <mreid@ptc.com >
~~~ ~~~ Subject: new upper bounds

from these calculations, we get new upper bounds on the length of
"god's algorithm": 42 quarter turns, 29 face turns. (no, i didn't
add incorrectly.) the previous upper bounds were 56 quarter turns,
37 face turns. the best known lower bounds are 21 quarter turns,
18 face turns.

here's how to get these upper bounds. note that the last twist in
stage 1 is always a quarter turn of either F, R, B or L, and the
direction doesn't matter. thus by choosing the direction of this
quarter turn properly, we hope to be able to avoid the positions at
maximal distance in stage 2.

the program verified that no two positions at distance 30 quarter
turns differ by F2, R2, B2 or L2, so we may avoid these bad cases.
i expected to be able to avoid the positions at distance 29 quarter
turns as well, but alas, things do not always go as planned. the
following two positions at distance 29 quarter turns differ by B2:

```position 1:
D1 R2 D3 L2 D3 R2 U3 D3 R2 U1 B2 D3 L2 D3 R2 D3 F2 D1 B2 D1   29q

position 2:
R2 U3 L2 U3 D3 L2 D1 L2 D1 R2 F2 D1 F2 D3 L2 B2 D1 B2 D1   29q
```

there are probably many other examples.

similarly, the positions at distance 18 face turns were checked and
no two of these differ by F2, R2, B2 or L2, so these positions
may be avoided.

```this gives upper bounds of  13 + 29 = 42  quarter turns and
12 + 17 = 29  face turns.
```

i expect to be able to reduce the 42 quarter turns slightly. for
example, to improve it to 41 quarter turns, i just need to check
that any position in stage 2 can be solved in at most 28 quarter
turns, where we now allow all turns. of course, this only requires
testing the positions at distance 29 and 30. i expect this to be
straightforward, but i don't know how much improvement i can get
with this approach.

the same approach doesn't seem plausible for face turns. in order
to get just 1 face turn improvement, all positions at distance 17
face turns would need to be solvable in at most 16 face turns.
this doesn't seem promising. probably most of these require 17
face turns even with all turns available.

mike