[This message is being sent to Dan Hoey, and refers to his message of
9-Jan-81, subject: The Supergroup -- Part 2: at least 25 qtw and why]
Appended to this message is a longish message I recieved, which has
some good ideas to use. In particular, what about using your technique
on a 2x2x2 cube, or an (idealized) edge-only cube? And then comparing
it with his clculations for the 2x2x2.
I'm not sure without a 2x2x2 in front of me, but I think there are
only 2 distinct 1 qtw per set of opposite faces, and only one 2qtw move.
And that the period is only 2. Is that true? However, there should be
more low-number-of-twists identities.
I'm distrustful of the actual calculations in the message below, because
I don't see the 9 new configurations after only 1 twist. I think there are
only 6. Or am I missing something?
Also, Dan or someone else on the cube-lovers network: how about compiling
all the messages about lower bounds and identities (after a while) into
one file we can ftp and look at all together.
11-Sep-81 12:26:52-PDT,6785;000000000001
Mail-from: ARPAnet host BERKELEY rcvd at 11-Sep-81 1223-PDT
Date: 11 Sep 1981 11:43:07-PDT
From: ARPAVAX.sjk at Berkeley
To: isaacs@sri-kl
Subject: in case you haven't seen this ...

Article 16:
>From csvax:mhtsa!harpo!chico!esquire!psl Wed Sep 9 17:16:32 1981
Subject: Rubik's Cube
Newsgroups: net.games

Want to knoe how far away you can get from the solution on a Rubik's Cube?

A Simple Lower Bound

As everybody knows, the number of discrete configurations of the 3x3x3
Rubik's Cube is:

(8! * 12! * 3^8 * 2^12) / 12 = 4x10^19 = 43,252,003,274,489,856,000

One approach to a lower bound is to calculate the maximum possible number
of configurations you can reach with a particular number of moves and then
see how many moves you would have to make to reach the number above.

With no moves at all you get 1, the starting position. The first move gets
you 18, (any one of six faces turned one of three ways). The next move
gets you 18*15, (no point in turning the same face twice in a row), for a
total of 1+18+270 configurations reached after two moves. A table of these
values looks like:

	      ---------possible configurations---------
moves                 new   % max                 total
 0                      1   0.0%                      1
 1                     18   0.0%                     19
 2                    270   0.0%                    289
 3                   4050   0.0%                   4339
 4                  60750   0.0%                  65089
 5                 911250   0.0%                 976339
 6               13668750   0.0%               14645089
 7              205031250   0.0%              219676339
 8             3075468750   0.0%             3295145089
 9            46132031250   0.0%            49427176339
10           691980468750   0.0%           741407645089 Notice that
11         10379707031250   0.0%         11121114676339 not until 17
12        155695605468750   0.0%        166816720145089 moves has the
13       2335434082031250   0.0%       2502250802176339 total number
14      35031511230468750   0.1%      37533762032645089 of possible
15     525472668457031250   1.2%     563006430489676339 configurations
16    7882090026855468750  18.2%    8445096457345145089 exceeded the
17  118231350402832031250 273.4%  126676446860177176339 maximum.

So there is no possible way to reach some configurations in fewer than
17 moves. However, this analysis has assumed that each configuration
generated was a NEW one, but there are MANY cases where this will not
be so. A simple example is turning one face 180 degrees, the opposite
face 180 degrees, and then repeating those two moves -- four moves that
get us to an old, familiar configuration. If we factor out the sequences
that involve these opposite face identities the minimum number of moves
becomes 18. Needless to say there are still lots of useless move sequences,
but detecting them becomes a lot trickier.

A Rumored Upper Bound

Rumor has it that a computer program exists, (attributed to Thistlethwaite),
that provably will solve any Cube configuration in at most 41 moves.

Narrowing it Down

So the answer is somewhere between 18 and 41. How do you get further? One
way is to write a computer program that tries every sequence of moves until
it has generated every possible configuration at least once. That sounds
easy, and it is, but such a program would take a \\\L O N G/// time to run.
However, if we limit the problem a little by considering a Cube that is two
squares on a side (2x2x2), we have a chance of learning something.

2x2x2 Cube

By the same considerations stated above we can get a lower bound for the
2x2x2 Cube. There are 7! * 3^6 = 3,674,160 configurations and, since we
can limit ourselves to moving only three "orthogonal" sides of the 2x2x2
cube, on the n-th move you could reach 9 * 6^(n-1) new configurations thus
we find that with 8 moves you could reach at most 3,023,307 and with 9 you
could reach at most 18,139,851. (Note that this doesn't have the problem with
opposite side moves that the 3x3x3 cube has.)

Because the 2x2x2 cube is relatively simple we can actually run a program
to try all the possible move sequences and compare our bound with fact.
Listed below are the findings

	 ------new configurations-------    total configurations
moves    -----possible----  ---actual---    ---possible --actual
	   number      %    number   %          number    number
 0              1     0.0%       1  0.0%             1         1
 1              9     0.0%       9  0.0%             9        10
 2             54     0.0%      54  0.0%            63        64
 3            324     0.0%     321  0.0%           387       385
 4           1944     0.0%    1847  0.0%          2331      2232
 5          11664     0.3%    9992  0.3%         13995     12224
 6          69984     1.9%   50136  1.4%         83979     62360
 7         419904    11.4%  227536  6.2%        503883    289896
 8        2519424    68.6%  870072 23.7%       3023307   1159968
 9       15116544   411.4% 1887748 51.4%      18139851   3047716
10       90699264  2468.6%  623800 17.0%     108839115   3671516
11      544195584 14811.4%    2644  0.071%   653034699   3674160

Interestingly enough there are 2,644 configurations that require eleven
moves to reach a solution; this is less than one tenth of one percent of
the total configurations!

It's also interesting that it's better than a 50-50 bet that a randomly
ordered 2x2x2 cube can be solved in exactly nine moves, (it's not clear
how to turn this into a profitable bar bet, however).

Noticing that there are only 321 new configurations after three moves
instead of 324 leads us to guess that there are six non-trivial sequences
of six moves that end with the original configuration, (why?).

These results came from a C program running on a VAX 11/780 and even
though the 2x2x2 cube is simple compared to the 3x3x3 it took a lot of
time. The figures for 11 moves took over 51 hours of cpu time.

If you'd like to make a 2x2x2 cube with which to experiment you can simply
take all the little labels off a 3x3x3 cube except the ones on the corners
and then ignore the unlabeled cubes.

Here's one sequence that gets you to one of the 2,644 configurations:
    f r f r f d2 f d- f d2 r2    f = rotate front face 90 degrees
				 r = rotate right face 90 degrees
				d2 = rotate "down" face 180 degrees
				d- = rotate "down" face 270 degrees

So Where's That Leave Us?

I just thought of a dandy way to get the answer for the 3x3x3 cube, but
the margins on this news item are a little too small for me to include it ...

-------