Message #1839
From: Andrew Gould <agould@uwm.edu>
Subject: RE: [MC4D] Re: State graph of MC2D
Date: Wed, 03 Aug 2011 12:54:24 -0500
Hi David,
Herbert Kociemba (part of the cube20.org group) used this ‘reducing by
symmetries’ to solve god’s number is 20. It cut the number of states they
had to solve by a factor of about 39.7. So it’s quite practical. He didn’t
call it ‘recoloring’ though….
He defined a ‘symmetry’: a combination of rotations or a combination of
rotations with a reflection. Each symmetry, S has a unique inverse S’, and
the double inverse, S’’ = S. Two states, j and k are then said to be
equivalent if there exists a symmetry such that j = SkS’. I look at it as
conjugating by symmetries only.
For details, go to http://kociemba.org/cube.htm, then on the left side under
‘The Mathematics behind Cube Explorer’, click ‘Equivalent Cubes and
Symmetry’.
–
Andy
From: 4D_Cubing@yahoogroups.com [mailto:4D_Cubing@yahoogroups.com] On Behalf
Of Melinda Green
Sent: Wednesday, August 03, 2011 3:58
To: 4D_Cubing@yahoogroups.com
Subject: Re: [MC4D] Re: State graph of MC2D
Hello David,
I haven’t given your message a careful read yet, and the meat of it seems to
introduce some interesting ideas, but since you claim to be confused by my
diagram, I thought I would reply briefly and see whether I can’t make it
clear. First off, maybe I shouldn’t call it a state graph as Nan suggests.
He suggests the word "type" instead but that feels too general a term for
this purpose but is probably better than "state". What the diagram really
represents is a "map" in the ordinary geographic sense. (Not the
graph-theoretic one). Given a scrambled state and this map you would start
by finding the node who’s pattern exactly matches the scrambled state. There
will be exactly one such node though you may need to rotate the map to match
the scramble pattern, and/or swap some colors, but you will find it. For
example, Next you select a path from that node to the solved "pattern".
God’s algorithm simply selects one of the shortest such path. Finally, you
look at each transition from your current pattern to the next one in your
chosen path which will correspond to exactly one twist. Just follow the path
and you’re done. I called node 5 a bottleneck because any solution path from
the maximally distant nodes 6 and 7 must funnel through that node. I
certainly meant it no disrespect and trust it does not feel maligned. :-)
So you see, the map has a definite and useful purpose, just maybe not the
one that you were expecting.
Now I see that Nan beat me by a minute, so it should be clear that his
explanation is correct.
-Melinda
On 8/3/2011 12:54 AM, David Vanderschel wrote:
I think maybe a little too much is being made of this state
graph business for the 2D puzzle. I am going to start by
being somewhat critical of what has been said so far. Then
I am going to switch gears and discuss a different, but
closely related, way of partitioning cubie arrangements -
one which I have found to have very general applicability in
solving any type of cubie in any of the generalizations of
the puzzle.
What we are dealing with in MC2D is S4, the symmetric group
on 4 elements. See
http://en.wikiversity.org/wiki/Symmetric_group_S4
This is a rather well understood subject. It is all there
really is to the 2D puzzle, since there is no issue of
orientation for the cubies. (The orientation of a 2D cubie
is determined by its position.)
In the case of MC2D, we are given 4 2-cycles (the twists)
with which to generate the group. (3 would have sufficed.)
As I (fail to) recall, Melinda never made it very clear
about what were her criteria for the particular partitioning
of the 24 permutations she chose for her "states". I never
understood what technical meaning she was ascribing to
"complete" or why she used the definite article on "the
complete graph". There are many ways to partition the 24
elements of S4. Nan’s graphs certainly would seem to me to
be closer to what I would call "complete" in this context.
There are ways to be precise about such things: E.g., one
could say, "Two permutations are related if they are
conjugates of one another." This is an equivalence relation
which partitions the permutations into the 5 equivalence
classes. Melinda’s state 5 is an equivalence class by this
relation. It consists of the 12 permutations that are
3-cycles.
However, by the conjugacy relation, Melinda’s states 1 (2
permutations) and 2 (1 permutation) should be merged. All 3
consist of 2 2-cycles. These, along with the identity, form
a subgroup of S4 isomorphic to the Klein Four Group. See
http://en.wikipedia.org/wiki/Klein_four_group
Kamack and Keane called such permuters "crosses", and I will
stick with that.
The crosses, the 3-cycles, and the identity (i.e., states 1,
2, 5, and 0) exhaust the 12 even permuters of S4.
What about the odd ones? Again, by conjugacy, Melinda’s
states 3 and 6 should be merged, as these are the 1-cycles,
of which there are 6. What remain are 6 4-cycles. These
are in Melinda’s states 4 and 7, and any pair of 4-cycles is
related by conjugation.
Thus the conjugacy relation partitions S4 into 5 equivalence
classes which can be seen to correspond to the identity,
crosses, 3-cycles, 1-cycles, and 4-cycles of sizes 1, 3, 8,
6, and 6 respectively.
Melinda’s graph accurately depicts the fact that you cannot
get from any member of either of the last two states to one
of the first 3 with one twist. Similarly for 0 -> 2. But I
cannot turn this observation into a clue for the
partitioning. For example, there exist permutation pairs
from states 3 and 5 which require 3 twists to get from one
to the other. Therefore an edge between two states does not
mean that any pair from the 2 states is related by a single
twist.
The best guess that I can come up with for Melinda’s
partitioning relation is the following: Two permutations
are related if they are conjugates and, if one moves a cubie
to the diagonally opposite corner, then both must do so.
That sounds fairly inelegant to me, and I am not sure what
the justification for it would be. (I imagine that Melinda
must have had something else in mind which happens to work
out this way.) Furthermore, it singles out two pairs of the
positions as being "diagonally opposite", a property of the
puzzle, not S4. (Diagonally opposite can also be defined in
terms of the 4 2-cycles we are given to generate the group:
Two positions are diagonally opposite if the transposition
for that pair is not one of the generators.)
The pejorative word "bottleneck" has been used to describe
Melinda’s node 5, which consists of the 8 3-cycles. I don’t
understand the implications of this. After all, we are
talking about 2/3 of the even permutations in S4. One of
them is bound to be close (in the twisting sense) to any odd
permutation. I don’t see anything particularly bad or good
about this fact.
>From the practical point of view, there is no practical
point of view! By this I mean that the state graph does not
really give me any useful insight into solving the puzzle.
It was trivial to start with. I did not need any help.
There is a sense in which a lot of the above is addressed by
the concept of "cycle structure". See
http://en.wikipedia.org/wiki/Symmetric_group#Conjugacy_classes
So let me switch gears into an area where some help would be
beneficial. As it turns out, I had already discovered some
significance of cycle structure even before I ran across a
reference to it here:
http://www.scribd.com/doc/55445481/37/De%EF%AC%81nition-of-a-group#page=88
Proposition 3.31 there is easy to prove; but it is not the
sort of thing that would have occurred to me, even though
cycle structure was already something I was thinking about.
I refer to cycle structure in terms of "Cycle Length
Signature" or "CLS" for the current permutation of a set of
cubies which can all occupy the same set of positions. I
indicate a CLS by writing "S" (for signature) followed by
digits, in non-increasing order, representing the lengths of
all the cycles for all the unplaced cubies of the set. (In
the rare case that such a cycle is of length greater than 9,
you have to delimit it with a comma.) It includes 1-cycles
for cubies which are in their home positions with incorrect
orientation. I refer to such a cubie as being "stuck at
home", as it needs to be removed from its home position
before it can be placed with correct orientation. The fact
that a CLS corresponds to a conjugacy class for the
permutation group, though interesting from the academic
point of view, is not what interests me from the practical
point of view.
A useful number can be derived from the CLS. I call it the
Cycle Length Signature Count or CLSC. The CLSC is derived
from the CLS by adding the lengths of the cycles and then
adding the number of cycles. The significance of CLSC is as
follows:
Most of my solving is by means of moves (or twist
sequences) which accomplish 3-cycles. If 3 cubies are
already permuted in a 3-cycle relative to their home
positions, then doing a move which accomplishes the
reverse 3-cycle can place two of them with correct
orientation. If the third one comes out with correct
orientation, that is just a matter of luck. You cannot
normally count on it unless the 3 cubies are the last
unplaced cubies in the set.
So, unless you get the good luck, we can see that the
best a 3-cycle can do is to reduce the CLSC by 2: If
the 3 cubies we permute are in a cycle of length greater
than 2, then the unplaced cubies of the original cycle
will be in a cycle of length 2 less than we started
with, and the number of cycles in the CLS will remain
the same. (The preceding assumes that the 2 cubies
which are placed are placed with correct orientation,
and this is possible in general.) If the 3 cubies we
permute come from 2 different cycles and one of them is
a cycle of length 2 or more, then we can only place one
of them. However, the cycles are merged. So we reduce
the sum of the cycle lengths by 1 and the number of
cycles by 1. If the 3 cubies we permute come from 3
different cycles, then we can place none of them, but
the number of cycles is reduced by 2.
Thus each move will typically decrease CLSC by 2.
I first used this insight when solving a regular 3D puzzle.
I don’t have to start doing 3-cycle type moves until I get
down to the last 5 or fewer unplaced corners. The CLSes
possible in that situation are as follows:
S5, S221, S311, S11111,
S22, S31, S1111,
S3, S111,
S11
Those are in decreasing order of the number of unplaced
cubies and increasing order of the number of cubies stuck at
home. (You can do it for a number of unplaced cubies larger
than 5, but this is enough to make the relevant points.)
The transitions which can be achieved (not counting good
luck) by doing a 3-cycle are as follows:
CLS CLSC
S11111 -> S311 10 -> 8
S221 -> S22 or S31 8 -> 6
S311 -> S111 or S31 8 -> 6
S1111 -> S31 8 -> 6
S5 -> S3 6 -> 4
S22 -> S3 6 -> 4
S31 -> S11 or S3 6 -> 4
S111 -> S3 6 -> 4
S11 -> S3 4 -> 4
S3 -> S 4 -> 0
The last one beats the "decrease CLSC by 2" behaviour
because, assuming it places 2 with correct orientation, the
last 3-cycle must place all 3 correctly, no luck required.
We see that S11 should be avoided, since it cannot be
reduced by a 3-cycle at all. (Now, though it works, I don’t
actually do two 3-cycles to fix S11. However, the move that
I use to fix the orientation on 2 corners is 14 twists,
which is very close to the 16 twists required to do two
3-cycles, so it really is almost the same.)
The important lesson that one can learn from the above is
the following: When faced with S31 (which is pretty obvious
once you get there), do not place 2 of the cubies in the
3-cycle (as tempting as that may be), as you are guaranteed
to wind up in S11 in this case. (No good luck is possible
in this situation.) It is far better to place just one
cubie and move the one that’s stuck at home.
The above logic is not just for corner cubies in a 3D
puzzle. It applies to any type of cubie in any
generalization of the puzzle. However, in higher dimensions
there are cubie positions which have enough symmetries that
it is possible to change the orientation of just one cubie
without otherwise affecting the arrangement of the pile.
E.g., corners in 4D. Thus S1 is possible in those cases.
The number of 3-cycle solving moves required to finish is
typically (CLSC-2)/2, unless you make the S31->S11 mistake.
Aside from avoiding the mistake, the 3-cycle solving moves
you choose don’t affect the number of moves required to
finish. This last fact was somewhat surprising to me, as I
had developed a lot ‘theories’ in my mind about which sizes
of cycles should be tackled first. As it turns out, it
makes no difference. Except for S31, if you can place 2,
that’s good. If you can place 1 and merge 2 cycles, that is
also good.
We can see that the worst case for 5 unplaced cubies is
S11111. Oddly, this is a state that some solving methods
actually seek to achieve - at least S1111. As far as I am
concerned, one should avoid having any cubies be stuck at
home to whatever extent is possible.
(There are cases where I can handle S22 in a more direct
manner than 2 3-cycles. However, the improvement is not all
that impressive.)
I must admit that, until quite recently, I did not realize
how closely related were my CLS approach and Melinda’s state
graph. That’s because I did not realize that a signature
corresponded to a conjugacy class, and I did not realize how
close to conjugacy classes were Melinda’s states. However,
there remains a big difference in that my approach treats
cubies which are stuck at home, a situation that cannot even
arise in the 2D case. Furthermore, my approach generalizes
to all generalizations of the puzzle and to all cubie types
in an obvious manner that can be applied with useful effect.
Regards,
David V.