From BRYAN@wvnvm.wvnet.edu Sat Aug 13 17:17:43 1994
Return-Path:
Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA00262; Sat, 13 Aug 94 17:17:43 EDT
Message-Id: <9408132117.AA00262@life.ai.mit.edu>
Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2)
with BSMTP id 0294; Sat, 13 Aug 94 17:14:54 EDT
Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU
(LMail V1.2a/1.8a) with BSMTP id 2921; Sat, 13 Aug 1994 17:14:54 -0400
X-Acknowledge-To:
Date: Sat, 13 Aug 1994 17:14:53 EDT
From: "Jerry Bryan"
To: "Cube Lovers List"
Subject: GC Local Maxima, Additional Information
In all my God's algorithm searches, I have never calculated local
maxima. My search technique and data representation do not lend
themselves very well to calculating local maxima. However, I thought
I would give it a try anyway. I decided to start by calculating local
maxima for GC, the corners only group, since local maxima for this group
have been calculated before and I could check my answers. I have
come up with some surprising results.
For a given cube X, there are twelve (not necessarily distinct)
neighbors of the form Xq, where q is in Q, the set of twelve
quarter turns. Each Xq is either one move closer to Start or one
move further from Start than X. I decided to determine for each cube
X, how many of the Xq were closer to Start and how many were further
from Start. This is a superset of the local maxima problem. Those
X for which I determine that all twelve of the Xq are closer to Start
are the local maxima, but I also determine for how many of the X
there are eleven neighbors Xq closer to Start, for how many of the X
there are ten neighbors Xq closer to Start, etc. This is where the
surprising results come in.
The following table summarizes the results. The table is a little hard
to read. The rows (from 0 to 14) are the distances from Start. The
columns (from 0 to 12) are the number of qturns which take you closer
to Start. For example, row 4 column 3 contains 480. This means that
there 480 cubes that are 4 moves from Start and for which 3 of the 12
qturns will take you closer to Start. The table is too wide for a
computer screen, so I split it. Columns 0 through 6 appear first, and
then columns 7 through 12 are below.
Column 12 represents the local maxima. The "Total" column is simply
the total number of cubes at each level. The "Total" column and the
local maxima column appear several times in the archives, and my
numbers match the archives. The first occurrence I have found is
Dan Hoey's note of 20 August 1984.
Number of Twists which Go Towards Start
Level Total 0 1 2 3 4 5 6
Cubes
0 1 1 0 0 0 0 0 0
1 12 0 12 0 0 0 0 0
2 114 0 96 18 0 0 0 0
3 924 0 672 192 60 0 0 0
4 6539 0 4032 1920 480 51 0 56
5 39528 0 19104 14904 3792 984 216 384
6 199926 0 71184 90984 16656 13212 1872 3936
7 806136 0 123360 478008 42768 117576 7824 16656
8 2761740 0 23328 1911312 9024 643536 2736 121872
9 8656152 0 0 5573376 0 2327616 0 558336
10 22334112 0 0 11167488 0 7057440 0 2818176
11 32420448 0 0 4661568 0 8314272 0 8893248
12 18780864 0 0 19008 0 123840 0 591744
13 2166720 0 0 0 0 0 0 0
14 6624 0 0 0 0 0 0 0
Total 88179840 1 241788 23918778 72780 18598527 12648 13004408
7 8 9 10 11 12
0 0 0 0 0 0 0
1 0 0 0 0 0 0
2 0 0 0 0 0 0
3 0 0 0 0 0 0
4 0 0 0 0 0 0
5 144 0 0 0 0 0
6 528 1344 0 96 0 114
7 1680 9096 1536 6552 480 600
8 384 23232 96 7584 720 17916
9 0 167616 0 19008 0 10200
10 0 1020384 0 235584 0 35040
11 0 6746688 0 2986560 0 818112
12 0 2202912 0 6189120 0 9654240
13 0 288 0 39168 0 2127264
14 0 0 0 0 0 6624
2736 10171560 1632 9483672 1200 12670110
The first surprising thing I noticed is the diagonals, especially
close to Start. I am not quite sure why there should be diagonals.
I would describe the diagonals as a weak feature of the chart, but
they are surely there. I think the diagonals mean something as follows.
Pick a cube X which is N moves from Start, and for which M qturns
will take you closer to Start. Move to a cube Xq which is N+1 moves
from Start. Then there is a *tendency* (not a certainty!) for there
to be M+1 moves which will take Xq closer to Start. I can't think
of any reason for this to be so, but the chart has diagonals.
The second surprising thing is that the chart contains a preponderance
of even numbers. There are only
two odd numbers in the whole chart. Row 0 column 0
contains a 1, and row 4 column 4 contains a 51. All the other cells
in the chart contain an even number. Furthermore, by comparison to
each other, the even columns are densely populated and the odd columns
are sparsely populated. Finally, below level 8, the
odd columns are completely empty.
It is often the case that when there are an even number of objects, there
is some natural pairing that can be performed on the objects. In this
case, I think the pairing that can be performed to explain the even numbers
is twists of opposite faces. R can be paired with L, R' can be paired
with L', U can be paired with D, etc.
The corners-only group GC is "almost" the same as the corners-only-
without-centers group GC/C. (GC/C is also called a 2x2x2 cube or a
pocket cube). In GC/C, the pairing between moves of opposite faces
is absolute. You can always choose either of two opposite faces with
equivalent results. In GC, the pairing is relative. You can "almost"
solve GC the same way as GC/C, but sometimes you have to be sensitive
to which of two opposite faces you twist in order to rotate the
corners properly. Dan's 20 August 1984 note explains this phenomenon
much better than I can:
>The alert reader will notice that rows 10 through 14 contain values
>exactly 24 times as large as those for the pocket cube. This is not
>surprising, given that the groups are identical except for the position
>of the entire assembly in space, and each generator of the corner cube
>is identical to the inverse of the corresponding generator for the
>opposite face except for the whole-cube position. Thus when solving a
>corner-cube position at 10 qtw or more from solved, it can be solved as
>a pocket cube, making the choice between opposite faces in such a way
>that the whole-cube position comes out right with no extra moves.
I can't fully explain why Dan's results are for rows 10 through 14,
whereas in my chart the odd columns are empty for rows 9 through 14.
Also, any rotation of the corners can be accomplished in no more than
6 qturns (see my note of 4 December 1993 concerning the corners of
the 3x3x3). I think that the explanation is something to the effect
that for rows 10 through 14, if (for example) R will take you closer
to Start, then so too will L, and vice versa. I don't think you have
to start choosing between (for example) R and L to accomplish the proper
rotation until you get below level 10.
Perhaps Dan can fully explain the mystery: why is it
that a rotation of the corners only requires 6 qturns, full pairing
of opposite face turns kicks in at level 9, and GC becomes
exactly 24 times GC/C at level 10? What is happening between level 6
and level 10? Why don't all three phenomena kick in at the same level?
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
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
If you don't have time to do it right today, what makes you think you are
going to have time to do it over again tomorrow?