From:

~~~ Subject:

[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 ...

-------