This is about the simple 2D puzzle here:
In that page there is a state graph with eight states. A curious fact is th=
at the graph is irregular: state #5 is a bottleneck, which separates the gr=
aph into two parts. Each state in this graph may actually represent several=
"states". For example, if I start with the solved state and make a twist, =
there are four possible outcomes (flipping the up, down, left or right face=
. Middle slice moves are not allowed). These four outcomes are equivalent i=
n the sense that if I redefine the colors and rotate the whole puzzle, one =
outcome becomes the other. Because of the equivalency, all the four outcome=
s are represented by state #3 in this graph. For clarity, from now on I cal=
l a state in that graph a "type", and call the specific states like the fou=
r outcomes "states". Several states can be grouped into a type.=20
Using this terminology, the graph in
n?
Not allowing middle slice moves, there are 4!=3D24 states. The graph with 2=
4 nodes for the 24 states should be a regular graph:=20
>
The 24 vertices of the truncated octahedron represent the 24 states. The ye=
llow, green, red, blue lines connecting the states mean that turning the ye=
llow (left) face, green (right) face, red (up) face or blue (down) face swi=
tches the puzzle between the two states that the edge connects. There are a=
lso thin black edges in the illustration. They don't mean anything. I added=
them simply to complete the shape of truncated octahedron.=20
The nodes are colored according to their types. The black node is type-0 de=
fined in
re type-1. In general the RGB color of the nodes is the binary expansion of=
the type. For example, since 5(dec)=3D101(bin), type-5 is RGB=3D101=3Dmage=
nta. An exception is that type-7 (111) is gray instead of white, because gr=
ay is more visible than white.
I have another illustration where the 24 states are fully described by numb=
ers.=20
f>
The four 2C pieces (corners) of the puzzle are numbered by 1,2,3,4. The sid=
e-centers are omitted because they never move. The solved state is
(1 2)
(3 4)
Any 2x2 matrix is a possible state. This graph is messier, especially becau=
se Mathematica is not correctly showing the occlusion of the nodes.
In the colorful illustration, we can find that Type-5 is special. It includ=
es all the states that can be obtained by a 3-cycle of the corners. There a=
re 8 such states. They isolated the gray and yellow nodes from the others. =
So in the graph of MC2D type-5
appears to be the bottleneck.
Comparing the graph for types (Melinda's version) in
Melinda said that,
"About state graphs, I can see good arguments either way. Your version does=
not allow recoloring, and the good thing is that the count agrees with Dav=
id's (or whoever created the Wikipedia pages for these puzzles), and your g=
raph has higher symmetry. I particularly like your elegant coloring scheme.=
My version may be more helpful for solving because it is more compact. Wit=
h it you get from any state to any other state. You just choose your shorte=
st path between them and then just find each next state according to its pa=
ttern. I don't see any reason why this shouldn't work for any twisty puzzle=
. Yours may still be better because you don't need to match patterns; you j=
ust solve by twisting the appropriately colored grip.
"The "best" or more "correct" choice of model may depend upon one's needs. =
If your approach gives consistantly high symmetries, then it may be conside=
red to be "best". OTOH, mine is more compact and maybe illustrates the true=
number of different situations you can encounter. Maybe math folks don't c=
are about utility, and only care about the ease of modelling. I don't reall=
y know."
Nan
Thank you Nan for posting this to the group. For context, Nan, Brandon
and I all met for a marathon discussion and brainstorming session a
little while ago and had a fabulous time. The topic of MC2D came up in
the context of state graphs for twisty puzzles in which Nan described
the two types of graphs, their connections and differences. I felt that
his analysis was extremely helpful in showing us how to better think
about this topic. What makes the seemingly trivial MC2D puzzle
interesting is that it is about as simple a twisty puzzle as possible
that still has a non-trivial state graph. What makes this feature useful
is that it allows us to theorize about the general cases. In general, I
suspect that the state graphs for most of our favorite puzzles can never
be mapped out. (I'm looking at you, mister 120 Cell!) , so this sort of
exercise may help us to theorize about the essential similarities and
differences between all twisty puzzles.
The "bottleneck" feature is clearly the most interesting feature that
falls out of the examination of MC2D. The question that immediately
presents itself is whether it has analogs in any other puzzles. This
approach is similar to how biologists have selected what they call
"model organisms" such as the gut bacteria, flatworm, fruit fly, mouse,
rat, dog, pig, and Rhesus monkey. Getting many labs to standardize on
studying those animals and their similarities and differences lets them
more confidently extrapolate towards human biology and all biology in
general.
Before we can say much about the bottleneck state or states in general
twisty puzzles, we probably need to select a few more "model puzzles" to
map out and compare their graph features. I don't know what puzzle is
the next one that we should attempt to map out, but I highly encourage
any interested group member to suggest some or to even attempt to map
them out and try to find a presentation that displays the most symmetry
or most similarities to that of MC2D. In that way we may learn more
about these state and type spaces. In many ways, the essence of all of
our favorite puzzles live in these spaces, and I believe that we
currently know very little about the nature of their maps compared with
what we know about their practical algorithms and group-theoretic features.
With the proof of God's algorithm for the 3^3 now in hand, we now know
the diameter of its state graph. This is a wonderful thing, but what
other features of its graph do we know about? I'm sure that some people
know more than just this one fact, and I suspect that there are many
other equally interesting features to be discovered that we currently
know nothing about. I expect that studying model puzzles may be one of
the best ways to approach the problem.
-Melinda
On 7/30/2011 1:13 PM, schuma wrote:
> This is about the simple 2D puzzle here:
>
> In that page there is a state graph with eight states. A curious fact is that the graph is irregular: state #5 is a bottleneck, which separates the graph into two parts. Each state in this graph may actually represent several "states". For example, if I start with the solved state and make a twist, there are four possible outcomes (flipping the up, down, left or right face. Middle slice moves are not allowed). These four outcomes are equivalent in the sense that if I redefine the colors and rotate the whole puzzle, one outcome becomes the other. Because of the equivalency, all the four outcomes are represented by state #3 in this graph. For clarity, from now on I call a state in that graph a "type", and call the specific states like the four outcomes "states". Several states can be grouped into a type.
>
> Using this terminology, the graph in
>
> Not allowing middle slice moves, there are 4!=24 states. The graph with 24 nodes for the 24 states should be a regular graph:
>
>
>
> The 24 vertices of the truncated octahedron represent the 24 states. The yellow, green, red, blue lines connecting the states mean that turning the yellow (left) face, green (right) face, red (up) face or blue (down) face switches the puzzle between the two states that the edge connects. There are also thin black edges in the illustration. They don't mean anything. I added them simply to complete the shape of truncated octahedron.
>
> The nodes are colored according to their types. The black node is type-0 defined in
>
> I have another illustration where the 24 states are fully described by numbers.
>
>
>
> The four 2C pieces (corners) of the puzzle are numbered by 1,2,3,4. The side-centers are omitted because they never move. The solved state is
> (1 2)
> (3 4)
> Any 2x2 matrix is a possible state. This graph is messier, especially because Mathematica is not correctly showing the occlusion of the nodes.
>
> In the colorful illustration, we can find that Type-5 is special. It includes all the states that can be obtained by a 3-cycle of the corners. There are 8 such states. They isolated the gray and yellow nodes from the others. So in the graph of MC2D type-5
> appears to be the bottleneck.
>
> Comparing the graph for types (Melinda's version) in
>
> "About state graphs, I can see good arguments either way. Your version does not allow recoloring, and the good thing is that the count agrees with David's (or whoever created the Wikipedia pages for these puzzles), and your graph has higher symmetry. I particularly like your elegant coloring scheme. My version may be more helpful for solving because it is more compact. With it you get from any state to any other state. You just choose your shortest path between them and then just find each next state according to its pattern. I don't see any reason why this shouldn't work for any twisty puzzle. Yours may still be better because you don't need to match patterns; you just solve by twisting the appropriately colored grip.
>
> "The "best" or more "correct" choice of model may depend upon one's needs. If your approach gives consistantly high symmetries, then it may be considered to be "best". OTOH, mine is more compact and maybe illustrates the true number of different situations you can encounter. Maybe math folks don't care about utility, and only care about the ease of modelling. I don't really know."
Melinda, thank you for providing the context about our meeting, and the con=
text about why the MC2D could be interesting.=20
Out of curiousity, I analyzed another simple puzzle and drew its state grap=
h in a geometrically symmetric manner. The simple puzzle is:=20
*** 2x2x2 with only 180-degree turns ***
I assume the LBD corner is always solved. Only U2, R2, F2 are the valid mov=
es. Just like MC2D, there are also 24 states. When I asked Mathematica to d=
raw the graph, it didn't provide a symmetric arrangement for the 24 nodes. =
Then I manually drew the graph and found a symmetric arrangement:
x2_180.PNG>
Here is how to look at the above graph. Inside of the large hexagon, there =
are 24 nodes where thin black lines meet. These 24 nodes represent the 24 s=
tates of the 180-degree-turning 2x2x2 puzzle. Every node has three edges, r=
epresenting U2, R2, F2. The opposite sides of the large hexagon are identif=
ied. So topologically it's a torus. It's good to think of it as a torus bec=
ause it's easy to see why all the nodes are equivalent.
One can also make copies of the large hexagon and tile them on a plane like=
a honeycomb:=20
2x2x2_180.PNG>
In that way every state (out of 24 states) can find a representitive in eac=
h hexagon cell of the honeycomb.=20
Why are there so many small hexagons? It's because a 6-move algorithm [U2,R=
2]x3 always bring you back to the original state. So do [U2,F2]x3 and [F2,R=
2]x3. Therefore from each starting point there are three hexagonal loops. N=
ote that [R2,U2]x3 is another such algorithm. But it's simply the inverse o=
f [U2,R2]x3. So these two algorithms are nothing but going along the same l=
oop in different directions. Using this property, one can easily label the =
thin lines by U2, R2, and F2.=20
I'm not good at identifying which states belongs to a type (an equivalency =
class with respect to recoloring and reorientation). It would be interestin=
g to find out whether there's a bottleneck in the graph of types.
Nan
--- In 4D_Cubing@yahoogroups.com, Melinda Green
>
> Thank you Nan for posting this to the group. For context, Nan, Brandon=20
> and I all met for a marathon discussion and brainstorming session a=20
> little while ago and had a fabulous time. The topic of MC2D came up in=20
--------------010801070509010104060703
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Nan,
I only get 404 errors for most of the image links you gave. The one that
I *could* see is your amazing hex graph (the first one below).
Topologically it's not a simple one-holed torus, but rather a torus-like
surface with three holes
What makes this much more interesting to me is that it has a higher
genus which is perhaps the most fundamental thing about topology in
general. It's amazing to me how this topic feeds-back into MagicTile and
Roice's recent support for IRPs. I will definitely have to attempt to
sketch the type graph if someone doesn't beat me to it. This has been
one crazyamazing day for me in several ways. Thank you for your
wonderful new result, Nan!
-Melinda
On 7/30/2011 11:42 PM, schuma wrote:
> Melinda, thank you for providing the context about our meeting, and the context about why the MC2D could be interesting.
>
> Out of curiousity, I analyzed another simple puzzle and drew its state graph in a geometrically symmetric manner. The simple puzzle is:
>
> *** 2x2x2 with only 180-degree turns ***
>
> I assume the LBD corner is always solved. Only U2, R2, F2 are the valid moves. Just like MC2D, there are also 24 states. When I asked Mathematica to draw the graph, it didn't provide a symmetric arrangement for the 24 nodes. Then I manually drew the graph and found a symmetric arrangement:
>
> Here is how to look at the above graph. Inside of the large hexagon, there are 24 nodes where thin black lines meet. These 24 nodes represent the 24 states of the 180-degree-turning 2x2x2 puzzle. Every node has three edges, representing U2, R2, F2. The opposite sides of the large hexagon are identified. So topologically it's a torus. It's good to think of it as a torus because it's easy to see why all the nodes are equivalent.
>
> One can also make copies of the large hexagon and tile them on a plane like a honeycomb:
>
> In that way every state (out of 24 states) can find a representitive in each hexagon cell of the honeycomb.
>
> Why are there so many small hexagons? It's because a 6-move algorithm [U2,R2]x3 always bring you back to the original state. So do [U2,F2]x3 and [F2,R2]x3. Therefore from each starting point there are three hexagonal loops. Note that [R2,U2]x3 is another such algorithm. But it's simply the inverse of [U2,R2]x3. So these two algorithms are nothing but going along the same loop in different directions. Using this property, one can easily label the thin lines by U2, R2, and F2.
>
> I'm not good at identifying which states belongs to a type (an equivalency class with respect to recoloring and reorientation). It would be interesting to find out whether there's a bottleneck in the graph of types.
>
> Nan
>
> --- In 4D_Cubing@yahoogroups.com, Melinda Green
>> Thank you Nan for posting this to the group. For context, Nan, Brandon
>> and I all met for a marathon discussion and brainstorming session a
>> little while ago and had a fabulous time. The topic of MC2D came up in
>
>
>
> ------------------------------------
>
> Yahoo! Groups Links
>
>
>
>
--------------010801070509010104060703
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
http-equiv="Content-Type">
Nan,
I only get 404 errors for most of the image links you gave. The one
that I *could* see is your amazing hex graph (the first one below).
Topologically it's not a simple one-holed torus, but rather a
surface with three holes. What makes this much more
interesting to me is that it has a higher genus which is perhaps the
most fundamental thing about topology in general. It's amazing to me
how this topic feeds-back into MagicTile and Roice's recent support
for IRPs. I will definitely have to attempt to sketch the type graph
if someone doesn't beat me to it. This has been one crazyamazing day
for me in several ways. Thank you for your wonderful new result,
Nan!
-Melinda
On 7/30/2011 11:42 PM, schuma wrote:
Melinda, thank you for providing the context about our meeting, and the context about why the MC2D could be interesting.
Out of curiousity, I analyzed another simple puzzle and drew its state graph in a geometrically symmetric manner. The simple puzzle is:
*** 2x2x2 with only 180-degree turns ***
I assume the LBD corner is always solved. Only U2, R2, F2 are the valid moves. Just like MC2D, there are also 24 states. When I asked Mathematica to draw the graph, it didn't provide a symmetric arrangement for the 24 nodes. Then I manually drew the graph and found a symmetric arrangement:
<http://f1.grp.yahoofs.com/v1/YO80Trg5bQ9DOvCmghWYKmmcstvrJMrSp4ViYt7ay-DHQMPjsF2J30mKITXTSCAeqn267QfnxVO5b2mHWEytX5C56K4Kidcr/Nan%20Ma/MC2D/Torus_2x2x2_180.PNG>
Here is how to look at the above graph. Inside of the large hexagon, there are 24 nodes where thin black lines meet. These 24 nodes represent the 24 states of the 180-degree-turning 2x2x2 puzzle. Every node has three edges, representing U2, R2, F2. The opposite sides of the large hexagon are identified. So topologically it's a torus. It's good to think of it as a torus because it's easy to see why all the nodes are equivalent.
One can also make copies of the large hexagon and tile them on a plane like a honeycomb:
<http://f1.grp.yahoofs.com/v1/YO80TqpgvnVDOvCm6xMkg0_FIRE7YA-QSSfogL5QAb11Ybc9DxG7wtQLOaLhuqPC4EKKpGaDLV76pJcmQT2RdWo80bl9La2G/Nan%20Ma/MC2D/Periodic_2x2x2_180.PNG>
In that way every state (out of 24 states) can find a representitive in each hexagon cell of the honeycomb.
Why are there so many small hexagons? It's because a 6-move algorithm [U2,R2]x3 always bring you back to the original state. So do [U2,F2]x3 and [F2,R2]x3. Therefore from each starting point there are three hexagonal loops. Note that [R2,U2]x3 is another such algorithm. But it's simply the inverse of [U2,R2]x3. So these two algorithms are nothing but going along the same loop in different directions. Using this property, one can easily label the thin lines by U2, R2, and F2.
I'm not good at identifying which states belongs to a type (an equivalency class with respect to recoloring and reorientation). It would be interesting to find out whether there's a bottleneck in the graph of types.
Nan
--- In 4D_Cubing@yahoogroups.com, Melinda Green <melinda@...> wrote:
Thank you Nan for posting this to the group. For context, Nan, Brandon
and I all met for a marathon discussion and brainstorming session a
little while ago and had a fabulous time. The topic of MC2D came up in
------------------------------------
Yahoo! Groups Links
<*> To visit your group on the web, go to:
http://groups.yahoo.com/group/4D_Cubing/
<*> Your email settings:
Individual Email | Traditional
<*> To change settings online go to:
http://groups.yahoo.com/group/4D_Cubing/join
(Yahoo! ID required)
<*> To change settings via email:
4D_Cubing-digest@yahoogroups.com
4D_Cubing-fullfeatured@yahoogroups.com
<*> To unsubscribe from this group, send an email to:
4D_Cubing-unsubscribe@yahoogroups.com
<*> Your use of Yahoo! Groups is subject to:
http://docs.yahoo.com/info/terms/
--------------010801070509010104060703--
Hi Melinda,
I don't know why the links fail. I am using the Yahoo group files and
copied the URL from the files. It worked when I tested them. But now
they don't work any more. Anyway, all the four files have always been
in the Yahoo group folder:
http://games.groups.yahoo.com/group/4D_Cubing/files/Nan%20Ma/MC2D/
There are four files:
color.gif is for MC2D, where the nodes and edges are color coded. It's
a GIF animation.
labels.gif is for MC2D, where the nodes are labeled by matrices. It's
also a GIF animation.
Torus_2x2x2.png is for the 2x2x2 with 180 deg turns, where only one
large hexagon is shown and the opposite sides are identified.
Periodic_2x2x2.png is for the 2x2x2 with 180 deg turns, where several
copies of large hexagons are tiled.
About the outcome of identifying opposite sides of a hexagon, I cannot
agree with you. Topologically, it should still be a regular torus.
Please see the section "hexagonal torus" in this page:
Nan
--- In 4D_Cubing@yahoogroups.com, Melinda Green
>
> Nan,
>=20
> I only get 404 errors for most of the image links you gave. The one that=
=20
> I *could* see is your amazing hex graph (the first one below).=20
> Topologically it's not a simple one-holed torus, but rather a torus-like=
=20
> surface with three holes=20
>
> What makes this much more interesting to me is that it has a higher=20
> genus which is perhaps the most fundamental thing about topology in=20
> general. It's amazing to me how this topic feeds-back into MagicTile and=
=20
> Roice's recent support for IRPs. I will definitely have to attempt to=20
> sketch the type graph if someone doesn't beat me to it. This has been=20
> one crazyamazing day for me in several ways. Thank you for your=20
> wonderful new result, Nan!
>=20
> -Melinda
>=20
> On 7/30/2011 11:42 PM, schuma wrote:
> > Melinda, thank you for providing the context about our meeting, and the=
context about why the MC2D could be interesting.
> >
> > Out of curiousity, I analyzed another simple puzzle and drew its state =
graph in a geometrically symmetric manner. The simple puzzle is:
> >
> > *** 2x2x2 with only 180-degree turns ***
> >
> > I assume the LBD corner is always solved. Only U2, R2, F2 are the valid=
moves. Just like MC2D, there are also 24 states. When I asked Mathematica =
to draw the graph, it didn't provide a symmetric arrangement for the 24 nod=
es. Then I manually drew the graph and found a symmetric arrangement:
> >
_2x2x2_180.PNG>
> > Here is how to look at the above graph. Inside of the large hexagon, th=
ere are 24 nodes where thin black lines meet. These 24 nodes represent the =
24 states of the 180-degree-turning 2x2x2 puzzle. Every node has three edge=
s, representing U2, R2, F2. The opposite sides of the large hexagon are ide=
ntified. So topologically it's a torus. It's good to think of it as a torus=
because it's easy to see why all the nodes are equivalent.
> >
> > One can also make copies of the large hexagon and tile them on a plane =
like a honeycomb:
> >
dic_2x2x2_180.PNG>
> > In that way every state (out of 24 states) can find a representitive in=
each hexagon cell of the honeycomb.
> >
> > Why are there so many small hexagons? It's because a 6-move algorithm [=
U2,R2]x3 always bring you back to the original state. So do [U2,F2]x3 and [=
F2,R2]x3. Therefore from each starting point there are three hexagonal loop=
s. Note that [R2,U2]x3 is another such algorithm. But it's simply the inver=
se of [U2,R2]x3. So these two algorithms are nothing but going along the sa=
me loop in different directions. Using this property, one can easily label =
the thin lines by U2, R2, and F2.
> >
> > I'm not good at identifying which states belongs to a type (an equivale=
ncy class with respect to recoloring and reorientation). It would be intere=
sting to find out whether there's a bottleneck in the graph of types.
> >
> > Nan
> >
> > --- In 4D_Cubing@yahoogroups.com, Melinda Green
> >> Thank you Nan for posting this to the group. For context, Nan, Brandon
> >> and I all met for a marathon discussion and brainstorming session a
> >> little while ago and had a fabulous time. The topic of MC2D came up in
> >
> >
> >
> > ------------------------------------
> >
> > Yahoo! Groups Links
> >
> >
> >
> >
>
Nan wailed:
>I don't know why the links fail.
Actually, the URL that appears in your
browser's Address field when viewing one of
those pages often fails as a link to the
page, and this has frustrated me over
the past few years.
OTOH, the link that appears in the message
announcing the uploading of the file does
work.
So, after uploading a file, one can follow up
with a post to indicate the significance of
the uploaded material. Then we can refer back
to upload-announcement message to actually
link to the item. It is too bad that the
person who did the uploading cannot add text
to the announcement message.
A link to an upload folder, which you can get
from the browser's URL when on the page, does
work. E.g.:
http://games.groups.yahoo.com/group/4D_Cubing/files/Nan%20Ma/MC2D/
Regards,
David V.
Hi David,
I found that I can append the filename after the folder's name, like this
http://games.groups.yahoo.com/group/4D_Cubing/files/Nan%20Ma/MC2D/color.gif
to make it work. I think this method is decent. This URL is case sensitive.=
=20
Nan
--- In 4D_Cubing@yahoogroups.com, "David Vanderschel"
>
> Nan wailed:
> >I don't know why the links fail.
>=20
> Actually, the URL that appears in your
> browser's Address field when viewing one of
> those pages often fails as a link to the
> page, and this has frustrated me over
> the past few years.
>=20
> OTOH, the link that appears in the message
> announcing the uploading of the file does
> work.
>=20
> So, after uploading a file, one can follow up
> with a post to indicate the significance of
> the uploaded material. Then we can refer back
> to upload-announcement message to actually
> link to the item. It is too bad that the
> person who did the uploading cannot add text
> to the announcement message.
>=20
> A link to an upload folder, which you can get
> from the browser's URL when on the page, does
> work. E.g.:
> http://games.groups.yahoo.com/group/4D_Cubing/files/Nan%20Ma/MC2D/
>=20
> Regards,
> David V.
>
--------------010108000408080304040902
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
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.
--------------010108000408080304040902
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Hi David,
I haven't read your CLS stuff yet. But about Melinda's classification of th=
e 24 states, here is my understanding:
Her definition of equivalency is not the conjugate class. It's about global=
rotation and re-coloring.=20
Definition: Starting from state A, if there exists a global rotation of 90*=
n degrees affecting all the corners and the centers, and then exists a reco=
loring (a permutation of the four colors), resulting in state B, then we sa=
y state A and state B are equivalent.
Melinda's "states" or I called "types" are the equivalence classes under th=
is equivalency relation.
Melinda, please correct me if my understanding is incorrect or my statement=
is unclear.
Your discussion about CLS looks interesting and I will read it when I wake =
up. :)
Nan
--- In 4D_Cubing@yahoogroups.com, David Vanderschel
>
> 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.
>=20
>=20
> What we are dealing with in MC2D is S4, the symmetric group
> on 4 elements. See
> http://en.wikiversity.org/wiki/Symmetric_group_S4
>=20
> 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.)
>=20
> In the case of MC2D, we are given 4 2-cycles (the twists)
> with which to generate the group. (3 would have sufficed.)
>=20
> 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.
>=20
> 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.=20=20
>=20
> 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.
>=20
> The crosses, the 3-cycles, and the identity (i.e., states 1,
> 2, 5, and 0) exhaust the 12 even permuters of S4.
>=20
> 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.
>=20
> 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.
>=20
> 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.
>=20
> 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.)
>=20
> 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.
>=20
> 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.
>=20
> 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
>=20
>=20
>=20
> 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=
=3D88
> 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.
>=20
> 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.
>=20
> 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:
>=20
> 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.
>=20
> 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.
>=20
> Thus each move will typically decrease CLSC by 2.
>=20
> 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:
>=20
> S5, S221, S311, S11111,
> S22, S31, S1111,
> S3, S111,
> S11
>=20
> 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.)
>=20
> The transitions which can be achieved (not counting good
> luck) by doing a 3-cycle are as follows:
>=20
>=20
> CLS CLSC
>=20
> 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
>=20
>=20
> 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.)
>=20
> 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.
>=20
> 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.
>=20
> 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.
>=20
> 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.
>=20
> (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.)
>=20
>=20
> 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.
>=20
> Regards,
> David V.
>
--------------040505030007050109070703
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
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.
>
>
>
>
--------------040505030007050109070703
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
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
href="http://en.wikiversity.org/wiki/Symmetric_group_S4">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
href="http://en.wikipedia.org/wiki/Klein_four_group">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
href="http://en.wikipedia.org/wiki/Symmetric_group#Conjugacy_classes">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:
href="http://www.scribd.com/doc/55445481/37/De%EF%AC%81nition-of-a-group#page=88">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.
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'' =3D S. Two states, j and k are then said to be
equivalent if there exists a symmetry such that j =3D SkS'. I look at it a=
s
conjugating by symmetries only.=20=20
For details, go to http://kociemba.org/cube.htm, then on the left side unde=
r
'The Mathematics behind Cube Explorer', click 'Equivalent Cubes and
Symmetry'.=20=20
--
Andy
From: 4D_Cubing@yahoogroups.com [mailto:4D_Cubing@yahoogroups.com] On Behal=
f
Of Melinda Green
Sent: Wednesday, August 03, 2011 3:58
To: 4D_Cubing@yahoogroups.com
Subject: Re: [MC4D] Re: State graph of MC2D
=A0=20
Hello David,
I haven't given your message a careful read yet, and the meat of it seems t=
o
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. Ther=
e
will be exactly one such node though you may need to rotate the map to matc=
h
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 pat=
h
and you're done. I called node 5 a bottleneck because any solution path fro=
m
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. :-)=
=A0
So you see, the map has a definite and useful purpose, just maybe not the
one that you were expecting.=20
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:=20
I think maybe a little too much is being made of this state
graph business for the 2D puzzle.=A0 I am going to start by
being somewhat critical of what has been said so far.=A0 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.=A0 See
http://en.wikiversity.org/wiki/Symmetric_group_S4
This is a rather well understood subject.=A0 It is all there
really is to the 2D puzzle, since there is no issue of
orientation for the cubies.=A0 (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.=A0 (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".=A0 I never
understood what technical meaning she was ascribing to
"complete" or why she used the definite article on "the
complete graph".=A0 There are many ways to partition the 24
elements of S4.=A0 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:=A0 E.g., one
could say, "Two permutations are related if they are
conjugates of one another."=A0 This is an equivalence relation
which partitions the permutations into the 5 equivalence
classes.=A0 Melinda's state 5 is an equivalence class by this
relation.=A0 It consists of the 12 permutations that are
3-cycles. =A0
However, by the conjugacy relation, Melinda's states 1 (2
permutations) and 2 (1 permutation) should be merged.=A0 All 3
consist of 2 2-cycles.=A0 These, along with the identity, form
a subgroup of S4 isomorphic to the Klein Four Group.=A0 See
http://en.wikipedia.org/wiki/Klein_four_group=20
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?=A0 Again, by conjugacy, Melinda's
states 3 and 6 should be merged, as these are the 1-cycles,
of which there are 6.=A0 What remain are 6 4-cycles.=A0 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.=A0 Similarly for 0 -> 2.=A0 But I
cannot turn this observation into a clue for the
partitioning.=A0 For example, there exist permutation pairs
from states 3 and 5 which require 3 twists to get from one
to the other.=A0 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:=A0 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.=A0 (I imagine that Melinda
must have had something else in mind which happens to work
out this way.)=A0 Furthermore, it singles out two pairs of the
positions as being "diagonally opposite", a property of the
puzzle, not S4.=A0 (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.=A0 I don't
understand the implications of this.=A0 After all, we are
talking about 2/3 of the even permutations in S4.=A0 One of
them is bound to be close (in the twisting sense) to any odd
permutation.=A0 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!=A0 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.=A0 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".=A0 See=20
http://en.wikipedia.org/wiki/Symmetric_group#Conjugacy_classes
So let me switch gears into an area where some help would be
beneficial.=A0 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=3D8=
8
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.=A0 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.=A0 (In
the rare case that such a cycle is of length greater than 9,
you have to delimit it with a comma.)=A0 It includes 1-cycles
for cubies which are in their home positions with incorrect
orientation.=A0 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.=A0 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.=A0 I call it the
Cycle Length Signature Count or CLSC.=A0 The CLSC is derived
from the CLS by adding the lengths of the cycles and then
adding the number of cycles.=A0 The significance of CLSC is as
follows:
=A0=A0=A0 Most of my solving is by means of moves (or twist
=A0=A0=A0 sequences) which accomplish 3-cycles.=A0 If 3 cubies are
=A0=A0=A0 already permuted in a 3-cycle relative to their home
=A0=A0=A0 positions, then doing a move which accomplishes the
=A0=A0=A0 reverse 3-cycle can place two of them with correct
=A0=A0=A0 orientation.=A0 If the third one comes out with correct
=A0=A0=A0 orientation, that is just a matter of luck.=A0 You cannot
=A0=A0=A0 normally count on it unless the 3 cubies are the last
=A0=A0=A0 unplaced cubies in the set.
=A0=A0=A0 So, unless you get the good luck, we can see that the
=A0=A0=A0 best a 3-cycle can do is to reduce the CLSC by 2:=A0 If
=A0=A0=A0 the 3 cubies we permute are in a cycle of length greater
=A0=A0=A0 than 2, then the unplaced cubies of the original cycle
=A0=A0=A0 will be in a cycle of length 2 less than we started
=A0=A0=A0 with, and the number of cycles in the CLS will remain
=A0=A0=A0 the same.=A0 (The preceding assumes that the 2 cubies
=A0=A0=A0 which are placed are placed with correct orientation,
=A0=A0=A0 and this is possible in general.)=A0 If the 3 cubies we
=A0=A0=A0 permute come from 2 different cycles and one of them is
=A0=A0=A0 a cycle of length 2 or more, then we can only place one
=A0=A0=A0 of them.=A0 However, the cycles are merged.=A0 So we reduce
=A0=A0=A0 the sum of the cycle lengths by 1 and the number of
=A0=A0=A0 cycles by 1.=A0 If the 3 cubies we permute come from 3
=A0=A0=A0 different cycles, then we can place none of them, but
=A0=A0=A0 the number of cycles is reduced by 2.
=A0=A0=A0 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.=A0 The CLSes
possible in that situation are as follows:
=A0=A0=A0 S5,=A0 S221,=A0 S311, S11111,=20
=A0=A0=A0 S22,=A0 S31, S1111,
=A0=A0=A0 S3,=A0 S111,
=A0=A0=A0 S11=20
Those are in decreasing order of the number of unplaced
cubies and increasing order of the number of cubies stuck at
home.=A0 (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:
=A0=A0=A0=A0=A0=A0=A0=A0=A0 CLS=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=
=A0=A0=A0=A0=A0 CLSC
=A0=A0=A0 S11111 -> S311=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 10 -> 8=20
=A0=A0=A0 S221=A0=A0 -> S22=A0 or S31=A0=A0=A0=A0=A0=A0 8 -> 6
=A0=A0=A0 S311=A0=A0 -> S111 or S31=A0=A0=A0=A0=A0=A0 8 -> 6
=A0=A0=A0 S1111=A0 -> S31=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 8 -> 6
=A0=A0=A0 S5=A0=A0=A0=A0 -> S3=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=
6 -> 4
=A0=A0=A0 S22=A0=A0=A0 -> S3=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 6=
-> 4=20
=A0=A0=A0 S31=A0=A0=A0 -> S11=A0 or S3=A0=A0=A0=A0=A0=A0=A0 6 -> 4
=A0=A0=A0 S111=A0=A0 -> S3=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 6 -=
> 4
=A0=A0=A0 S11=A0=A0=A0 -> S3=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 4=
-> 4=20
=A0=A0=A0 S3=A0=A0=A0=A0 -> S=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=
=A0 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.=A0 (Now, though it works, I don't
actually do two 3-cycles to fix S11.=A0 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:=A0 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.=A0 (No good luck is possible
in this situation.)=A0 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.=A0 It applies to any type of cubie in any
generalization of the puzzle.=A0 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.=A0 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.=A0 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.=A0 As it turns out, it
makes no difference.=A0 Except for S31, if you can place 2,
that's good.=A0 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.=A0 Oddly, this is a state that some solving methods
actually seek to achieve - at least S1111.=A0 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.=A0 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.=A0 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.=A0 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.=A0 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,
=A0 David V.
oops, speaking of link problems, if you click the link, it doesn't give you
a left side. Copy & paste http://kociemba.org/cube.htm. Also, by
'rotations' and 'reflections' I mean applying them to the whole puzzle. =
=20
--
Andy
From: 4D_Cubing@yahoogroups.com [mailto:4D_Cubing@yahoogroups.com] On Behal=
f
Of Andrew Gould
Sent: Wednesday, August 03, 2011 12:54
To: 4D_Cubing@yahoogroups.com
Subject: RE: [MC4D] Re: State graph of MC2D
=A0=20
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'' =3D S. Two states, j and k are then said to be
equivalent if there exists a symmetry such that j =3D SkS'. I look at it as
conjugating by symmetries only.=20
For details, go to http://kociemba.org/cube.htm, then on the left side unde=
r
'The Mathematics behind Cube Explorer', click 'Equivalent Cubes and
Symmetry'.=20
--
Andy
Andy,
I think this is the direct link to the page you were talking about:
http://kociemba.org/math/symmetries.htm
I think Kociemba's definition is aligned with Melinda's classification. In =
that webpage he explained the concept by two ways.
(1) In the first paragraph (box/example/whatever) he did use the word recol=
or. So it's recolor + whole cube rotation/reflection.=20
(2) Then he gave his preferred definition in the form of B=3DS'*A*S. In the=
process of S'*A*S, the first step S' is a whole-cube rotation/reflection o=
f a solved cube. This step is nothing but recoloring with some constraints =
(like, white and yellow cannot be on adjacent faces etc). So the two interp=
retations are the same thing. The latter one is just more analytical.=20
I think Melinda's equivalency for MC2D can also be defined in the analytica=
l way like S'AS:=20
Let's say state A can be obtained from the solved state by applying permuta=
tion A (with a little abuse of notation), and state B can be obtained by pe=
rmutation B. As David said, A and B belong to S_4. Then A and B are equival=
ent if there exists S in {whole-puzzle rotation and/or reflection, i.e., di=
hedral group D_4} such that B=3DS'AS.=20
In my email last night I forgot to include reflection. Now I remember Melin=
da's definition does need reflection for S.=20
Anyway this equivalency is weaker than conjugacy because S can only be a wh=
ole cube operation rather than a general twist. That's why David found Meli=
nda's classes should be merged to get the conjugacy classes.
Nan
--- In 4D_Cubing@yahoogroups.com, "Andrew Gould"
>
> oops, speaking of link problems, if you click the link, it doesn't give y=
ou
> a left side. Copy & paste http://kociemba.org/cube.htm. Also, by
> 'rotations' and 'reflections' I mean applying them to the whole puzzle. =
=20
>=20
> --
> Andy
>=20
>=20
> From: 4D_Cubing@yahoogroups.com [mailto:4D_Cubing@yahoogroups.com] On Beh=
alf
> Of Andrew Gould
> Sent: Wednesday, August 03, 2011 12:54
> To: 4D_Cubing@yahoogroups.com
> Subject: RE: [MC4D] Re: State graph of MC2D
>=20
> =EF=BF=BD=20
> Hi David,
>=20
> 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....
>=20
> He defined a 'symmetry': a combination of rotations or a combination of
> rotations with a reflection. Each symmetry, S has a unique inverse S', an=
d
> the double inverse, S'' =3D S. Two states, j and k are then said to be
> equivalent if there exists a symmetry such that j =3D SkS'. I look at it =
as
> conjugating by symmetries only.=20
>=20
> For details, go to http://kociemba.org/cube.htm, then on the left side un=
der
> 'The Mathematics behind Cube Explorer', click 'Equivalent Cubes and
> Symmetry'.=20
>=20
> --
> Andy
>
Nan wrote:
>I haven't read your CLS stuff yet. But about Melinda's
>classification of the 24 states, here is my understanding:
>Her definition of equivalency is not the conjugate
>class. It's about global rotation and re-coloring.
>Definition: Starting from state A, if there exists a global
>rotation of 90*n degrees affecting all the corners and the
>centers, and then exists a recoloring (a permutation of the
>four colors), resulting in state B, then we say state A and
>state B are equivalent.
OK. The above can be rephrased in terms of conjugation, and
I should have seen the way earlier. You are saying that 2
pemutations are related if one is a conjugate of the other
by 4-cycle that may be perceived as a rotation relative to
the corner positions in the puzzle. That does rule out the
4-cycles for which a cubie is crossing to the diagonally
opposite position. However, this would split node 5 into 2
subsets depending the direction of the rotation. I.e., I
see 3-cycle patterns that cannot match up with the canonical
pattern for state 5 without also mirroring them. If
4-cycles with diagonal crossings were admitted, then state 5
would remain intact. However, the regular conjugacy classes
would then merge. So I think something is still missing
from the explanation.
When I speak of "mirroring", I am not talking about moving
the face pieces. I actually ignore them. I am just talking
about a permutation of the cubies. Reflecting about a
diagonal axis would correspond to a 2-cycle for the two
cubies not on the axis. Reflecting about a coordinate axis
corresponds to two 2-cycles one for each pair of cubies with
the same coordinate on the axis about which we are
reflecting.
Melinda wrote:
>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".
Clearly, each node in the diagram does correspond to one of
the sets in a partition of the permutations of S4.
Furthermore, we can say that there is an edge between two
such nodes if, given a permutation in one set, there exists
a permutation in the other set which differs by a single
twist relative to the position indexing implied by the
puzzle and the allowed 2-cycles. That much should have been
clear all along.
What I am trying to get hold of is the relation which
determines the partitioning. I suggested, "Two permutations
are related if they are conjugates and, if one moves a cubie
to the diagonally opposite corner, then both must do so." I
believe that relation does correctly determine your
partitioning. Since conjugacy is so easy to check (based on
cycle structure), interpreting the above relation (strange
as it may seem) is much easier than interpreting your or
Nan's attempts to describe the rule for the partitioning.
If it is not clear what I am concerned with, check out
http://en.wikipedia.org/wiki/Partition_of_a_set#Partitions_and_equivalence_relations
or http://preview.tinyurl.com/3u6tzeh
Partitions of a set and equivalence relations on the set
are equivalent concepts. I see the partitioning. I am
trying to figure out a nice way to state the corresponding
equivalence relation. I am also biased to try to find
such a description in terms of the permutations themselves
and not in terms of manipulating an abstract physical
model in 2-space or 3-space. (As we have already
experienced, the latter type of description is difficult to
make precise in a mathematical sense.)
>What the diagram really represents is a "map" in the
>ordinary geographic sense. (Not the graph-theoretic
>one).
I am sorry, but I just don't get this analogy. There is no
way I can see that this mapping of permutations to nodes in
2-space admits geographic interpretation. It is still a
graph in the sense that there are nodes connected by edges.
The nodes of this graph correspond to sets in a partition of
S4.
>Given a scrambled state and this map you would start by
>finding the node who's pattern exactly matches the
>scrambled state.
"exactly matches" is not well defined. Nan suggested
rotations, but I saw that mirroring was required to keep
state 5 intact. If reflection about a diagonal axis were
admitted, you'd be back to conjugacy classes. Thus any such
mirroring must be restricted to reflections in the
coordinate axes, which are even permutations (crosses).
>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.
But it's not that hard in the first place:
Whenever any cubie is diagonally displaced, then, to get
a shortest solution, you must immediately do a twist
that moves at least one such diagonally displaced cubie.
For such a diagonally displaced cubie, there are two
slices you can twist. If twisting one of them will
place the other cubie in it, twist that slice. If
twisting one of them will displace the other cubie from
its home position and twisting the other slice won't do
that, twist the other. When no cubie is diagonally
displaced, the solution is obvious.
The preceding rule is much easier to understand and act upon
than trying to find your place in the diagram and thinking
about which member of the next node in the path is one that
you can get to with a single twist. (The last part is
referring to the fact that it is not true that _any_ pair of
permutations from adjacent nodes differ by a single twist.)
>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. :-)
Calling it anything would seem to imply that there is some
associated signficance. I am at a loss to discern any such
significance. To get, with a single twist, from either of
states 6 or 7, both of which are odd, you have no choice but
to go to an even permutation, and it won't be a cross. The
3-cycles are all that's left among the even permutations.
So what? If there is any point to be made, I think it is
that, since partition set 5 is so large (including 2/3 of
the even permutations), it is bound to be central in the
sense that you can reach it with a single twist from any odd
permutation; but I still don't see actionable information
here.
>So you see, the map has a definite and useful purpose, just
>maybe not the one that you were expecting.
I am not sure that it is appropriate to call it "useful"
when the problem it solves admits a solution that is so much
simpler to describe and implement. To make a utility
argument, I think you would have to move the considerations
into a purely academic domain. However, for that to be
interesting, I think the approach would have to generalize
to more complex puzzles. Using pure conjugacy classes, I
have already shown a way to do that. So let's talk about that
approach.
Regards,
David V.
--- In 4D_Cubing@yahoogroups.com, "David Vanderschel"
However, this would split node 5 into 2
> subsets depending the direction of the rotation. I.e., I
> see 3-cycle patterns that cannot match up with the canonical
> pattern for state 5 without also mirroring them. If
> 4-cycles with diagonal crossings were admitted, then state 5
> would remain intact. However, the regular conjugacy classes
> would then merge. So I think something is still missing
> from the explanation.
>=20
David, you are right. I forgot to include mirroring/reflection last night. =
Please check my post today for the latest correction and Kociemba's notatio=
n according to Andy's suggestion. Thanks.
Nan
Andrew Gould wrote:
>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.
But the context in which it is "practical" is an exhaustive
analysis of all positions. It is practical in the sense
that it pares down the number of arrangements that have to
be analyzed. That is not what is going on in the MC2D case.
The argument there involves a graph relating particular
equivalence classes of permutations, apparently with the
claim that this graph helps you solve the puzzle from a
particular state. Different problem.
>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.
I agree absolutely, and it makes perfectly good sense. As
Nan has commented, he had failed to mention that, in
addition to the rotational symmetry, reflections were also
admitted. I erred when I claimed that allowing
conjugating with [the symmetry corresponding to a reflection
about a diagonal axis] would produce the larger full
conjugacy classes. It does not. (Had I not made that
mistake, I might have made it all the way to realizing that
the equivalence relation for Melinda's partition is
"conjugates by a symmetry".)
Now I am trying to figure out why my weird way of stating
the equivalence relation works relative to this much more
sane symmetries approach.
Regards,
David V.
On 8/3/2011 5:20 PM, David Vanderschel wrote:
> Andrew Gould wrote:
>> 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.
> But the context in which it is "practical" is an exhaustive
> analysis of all positions. It is practical in the sense
> that it pares down the number of arrangements that have to
> be analyzed. That is not what is going on in the MC2D case.
> The argument there involves a graph relating particular
> equivalence classes of permutations, apparently with the
> claim that this graph helps you solve the puzzle from a
> particular state. Different problem.
I think that we are in some ways talking past each other, and I suspect
that where we split is in our overall goals in which the word
"practical" means very different things to each of us. Where I started
was in trying to understand the whole puzzle, which to me clearly meant
getting very familiar with all the possible states and how best to find
my way to the solved state. When I see a state that is one twist from
being solved, I don't particularly care if the twisted face is on the
top, left, bottom or right. Also, I don't particularly care about the
color of the face that needs to be twisted. I simply began to get to
know a bunch of the recurring patterns and wanted to enumerate them all
and see how they relate to each other.
You looked at my diagram and thought that what I was attempting had
something to do with cycles and conjugates but was just doing it wrong.
Different problems indeed. I don't know the precise mathematical
language to express my diagram in your terms but it looks like you and
Nan are doing a good job of that.
I find it fascinating that the 3^3 can be reduced to a graph with a only
a million such nodes, if I understood Nan correctly. That says to me
that it should be possible to print the whole thing out on a single
wall-sized diagram! Maybe "practical" is too loaded a term. Certainly it
is a very compact form and turned out to be practical in that it lead to
a tractable computer proof of God's algorithm. I understand that that as
applied math, this is a sort of practicality is of little interest to a
pure mathematician.
> [...] (Had I not made that mistake, I might have made it all the way
> to realizing that the equivalence relation for Melinda's partition is
> "conjugates by a symmetry".) Now I am trying to figure out why my
> weird way of stating the equivalence relation works relative to this
> much more sane symmetries approach.
Maybe this is fruitful because we are both interested in symmetries.
Where we part ways maybe has to do with our differing goals. I don't
expect you to be interested in the same symmetries that I am. It's
exciting to me to have a proof of God's number but that doesn't
necessarily give you a deeper understanding of the puzzle. I am happy
with the result but still a bit unsatisfied. I want to know on a deep
level why the number is what it is and how the internal states
interrelate. MC2D is a kind of work-up towards that. I never had much
trouble solving it, but I didn't feel that I understood it. Since I
mapped it I feel that I completely grok God's algorithm in this model
puzzle. With my diagram it is trivial to see that God's number must be 3
whereas before then I wasn't quite sure. I can now also see exactly how
the puzzle changes if we allow middle slice twists. Now I want to learn
about the equivalences and differences between the corresponding graphs
of all such puzzles. All I'm really asking is to know the mind of God.
Is that too much to ask?
-Melinda
Melinda wrote:
> You looked at my diagram and thought that what I was
> attempting had something to do with cycles and conjugates
> but was just doing it wrong.
Melinda, you are making assumptions about what I was
thinking that are not only false, but are contrary to what I
actually wrote. I hope that, after reading this, you will
apologize for the above inappropriate accusation. I hope
you will read this post carefully, because it appears that
you have failed to do so with my previous posts.
One of the first things I wrote was:
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.
As you can see, I made it clear that I was trying to
understand how you arrived at your particular partitioning.
I raised the issue of conjugacy classes because I understand
them and they seemed close to your partition. I never said
that what you were doing was "wrong" - just that I did not
understand it. And I wanted to understand it. I finally
did after Andrew Gould's post.
I was not ignoring the value of your graph either. In that
first post, I had mentioned:
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.
So I was acknowledging the fact that your graph puts limits
on the minimum number of twists required to solve. I did
understand that, and I would not discount its interest as an
academic issue. And note, in the above, that I was still
harping on the fact that I did not understand the rule for
your partition.
More recently I wrote:
What I am trying to get hold of is the relation which
determines the partitioning. I suggested, "...
If it is not clear what I am concerned with, check out
http://en.wikipedia.org/wiki/Partition_of_a_set#Partitions_and_equivalence_relations
or http://preview.tinyurl.com/3u6tzeh
Partitions of a set and equivalence relations on the set
are equivalent concepts. I see the partitioning. I am
trying to figure out a nice way to state the
corresponding equivalence relation. I am also biased to
try to find such a description in terms of the
permutations themselves and not in terms of manipulating
an abstract physical model in 2-space or 3-space. (As
we have already experienced, the latter type of
description is difficult to make precise in a
mathematical sense.)
I was concerned that maybe you were still confused about
what I was actually concerned with, so I went into even more
detail. Alas, that apparently still did not help. It
should be very clear that, at no point, did I ever claim
that what you had done was "wrong".
> Different problems indeed. I don't know the precise
> mathematical language to express my diagram in your terms
> but it looks like you and Nan are doing a good job of
> that.
Actually, no. It was Andrew Gould who straightened this
out, providing a way to specify the equivalence relation
that gives rise to your partition. It is mathematically
sound and elegantly simple. And, as it turns out,
conjugating is the way it's done. It's just that you cannot
conjugate with _any_ permutation of S4 - only those that
arise from symmetries. Thus the fact that I started talking
about conjugation early on was not irrelevant, as you seem
to imply. Nan had left me confused by omitting the
possibility of conjugating with a reflection.
Now there certainly is a sense in which I have expressed a
negative attitude about the graph. Indeed, my very first
comment in this thread was:
I think maybe a little too much is being made of this
state graph business for the 2D puzzle.
There were a couple things I had in mind when I made that
remark:
One was that Nan's elaboration of it was not
accomplishing anything that you had not already
accomplished. His treatment struck me as being more an
exploration of S4 than as offering insight into the
puzzle. That is why I went on to make the point that S4
is a rather well understood subject.
The other thing I had in mind is that your graph is not
an effective aid for solving the puzzle. I acknowledge
that it has relevance in an academic sense; but, from
the practical point of view, it is most definitely not
practical. I will stand by that. The puzzle is so very
easy to solve directly, that one can solve it in far
less time than it takes to figure out which node of the
graph a given permutation corresponds to, let alone
figuring out which permutation in the next node on the
solution path is one you can reach from your current
state.
For the purpose of actually solving the puzzle, I offered:
Whenever any cubie is diagonally displaced, then, to get
a shortest solution, you must immediately do a twist
that moves at least one such diagonally displaced cubie.
For such a diagonally displaced cubie, there are two
slices you can twist. If twisting one of them will
place the other cubie in it, twist that slice. If
twisting one of them will displace the other cubie from
its home position and twisting the other slice won't do
that, twist the other. When no cubie is diagonally
displaced, the solution is obvious.
Not only is that much easier to grok than your graph, a few
more lines of reasoning will prove that it always leads to a
solution in 4 or fewer twists. (In constructing that
argument, I see that I failed to mention one (fairly
obvious) rule: If there is a slice in which both cubies are
diagonally displaced, twist that one. That rule comes
before the other which-slice-to-twist rules.) Actually, I
was somewhat embarrassed to be belaboring what seems rather
obvious to me. (My friends and I mastered tic-tac-toe when
we were in the first grade, and that problem strikes me as
being more difficult than solving MC2D.)
But, again, my criticism was not that anything was "wrong".
I was just criticizing the graph's value from a practical
point of view when it comes to actually working the puzzle.
Now there is one rather odd thing you stated in your last
post that is indeed profoundly wrong:
"With my diagram it is trivial to see that God's number
must be 3 ..."
What I see is that it takes 4 twists to get from node 2 to
node 0.
One thing that is frustrating me about this diversion is
that I thought I had made a real contribution with the Cycle
Length Signature approach to a succinct but useful way to
classify the permutation state for any sort of cubie in any
generalization these puzzles. That approach is closely
related, as the CLS characterizes the conjugacy class of an
arrangement. The difference is that these conjugates are
not limited to conjugation by a symmetry. As it turns out,
that makes it much easier to identify the CLS class of an
arrangement; and it leads to a state graph with far fewer
nodes, which could be viewed as an advantage. Furthermore,
the insights from the CLS do have real practical
significance which can be readily applied when solving. I
thought folks would be excited about this.
Regards,
David V.
On 8/4/2011 3:02 PM, David Vanderschel wrote:
> Melinda wrote:
>> You looked at my diagram and thought that what I was
>> attempting had something to do with cycles and conjugates
>> but was just doing it wrong.
> Melinda, you are making assumptions about what I was
> thinking that are not only false, but are contrary to what I
> actually wrote. I hope that, after reading this, you will
> apologize for the above inappropriate accusation. I hope
> you will read this post carefully, because it appears that
> you have failed to do so with my previous posts.
I most deeply apologize. I should definitely said "I'm guessing that you
looked at my diagram..." That seems like a small qualification, but it
is not at all. You are right to call me on it and I appreciate the risk
you took in doing that. My pennance will be to try to read this message
all the more carefully as you suggest.
>
> One of the first things I wrote was:
>
> 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.
>
> As you can see, I made it clear that I was trying to
> understand how you arrived at your particular partitioning.
>
> I raised the issue of conjugacy classes because I understand
> them and they seemed close to your partition. I never said
> that what you were doing was "wrong" - just that I did not
> understand it. And I wanted to understand it. I finally
> did after Andrew Gould's post.
>
> I was not ignoring the value of your graph either. In that
> first post, I had mentioned:
>
> 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.
>
> So I was acknowledging the fact that your graph puts limits
> on the minimum number of twists required to solve. I did
> understand that, and I would not discount its interest as an
> academic issue. And note, in the above, that I was still
> harping on the fact that I did not understand the rule for
> your partition.
>
> More recently I wrote:
>
> What I am trying to get hold of is the relation which
> determines the partitioning. I suggested, "...
>
> If it is not clear what I am concerned with, check out
> http://en.wikipedia.org/wiki/Partition_of_a_set#Partitions_and_equivalence_relations
> or http://preview.tinyurl.com/3u6tzeh
> Partitions of a set and equivalence relations on the set
> are equivalent concepts. I see the partitioning. I am
> trying to figure out a nice way to state the
> corresponding equivalence relation. I am also biased to
> try to find such a description in terms of the
> permutations themselves and not in terms of manipulating
> an abstract physical model in 2-space or 3-space. (As
> we have already experienced, the latter type of
> description is difficult to make precise in a
> mathematical sense.)
>
> I was concerned that maybe you were still confused about
> what I was actually concerned with, so I went into even more
> detail. Alas, that apparently still did not help. It
> should be very clear that, at no point, did I ever claim
> that what you had done was "wrong".
I understand and believe you. When I said that I felt we were talking
past each other, I meant that I felt that we had each found something
interesting that we wanted to explain but were not succeeding very well,
and to nobody's fault.
>
>> Different problems indeed. I don't know the precise
>> mathematical language to express my diagram in your terms
>> but it looks like you and Nan are doing a good job of
>> that.
> Actually, no. It was Andrew Gould who straightened this
> out, providing a way to specify the equivalence relation
> that gives rise to your partition.
I stand corrected.
> It is mathematically
> sound and elegantly simple. And, as it turns out,
> conjugating is the way it's done.
I don't know if it is correct to say it is THE way it's done. It
certainly is A way, and possibly even the BEST way. This point was one
of the things that I was trying to get across. I'm sure that from your
point of view it is definitely the right way. I'm just pointing out that
there are other ways of looking at it. That was why I harped on the
question of purpose or utility.
> It's just that you cannot
> conjugate with _any_ permutation of S4 - only those that
> arise from symmetries. Thus the fact that I started talking
> about conjugation early on was not irrelevant, as you seem
> to imply.
Nope. I never thought that anything you have ever said was irrelevant. I
was just not convinced that you had accurately translated my thoughts
into more formal language.
> Nan had left me confused by omitting the
> possibility of conjugating with a reflection.
>
>
> Now there certainly is a sense in which I have expressed a
> negative attitude about the graph. Indeed, my very first
> comment in this thread was:
>
> I think maybe a little too much is being made of this
> state graph business for the 2D puzzle.
>
> There were a couple things I had in mind when I made that
> remark:
>
> One was that Nan's elaboration of it was not
> accomplishing anything that you had not already
> accomplished. His treatment struck me as being more an
> exploration of S4 than as offering insight into the
> puzzle. That is why I went on to make the point that S4
> is a rather well understood subject.
>
> The other thing I had in mind is that your graph is not
> an effective aid for solving the puzzle. I acknowledge
> that it has relevance in an academic sense; but, from
> the practical point of view, it is most definitely not
> practical. I will stand by that. The puzzle is so very
> easy to solve directly, that one can solve it in far
> less time than it takes to figure out which node of the
> graph a given permutation corresponds to, let alone
> figuring out which permutation in the next node on the
> solution path is one you can reach from your current
> state.
>
> For the purpose of actually solving the puzzle, I offered:
>
> Whenever any cubie is diagonally displaced, then, to get
> a shortest solution, you must immediately do a twist
> that moves at least one such diagonally displaced cubie.
> For such a diagonally displaced cubie, there are two
> slices you can twist. If twisting one of them will
> place the other cubie in it, twist that slice. If
> twisting one of them will displace the other cubie from
> its home position and twisting the other slice won't do
> that, twist the other. When no cubie is diagonally
> displaced, the solution is obvious.
>
> Not only is that much easier to grok than your graph, a few
> more lines of reasoning will prove that it always leads to a
> solution in 4 or fewer twists.
That statement is not at all convincing to me. I'm sure that it works
for you, and possibly for mathematicians who think symbolically, but
half of the world consists of visual thinkers like me for whom a diagram
is often more convincing.
Further, the subject of diagonals seems to only apply to a small class
of puzzles whereas I am looking for the unifying graph-theoretic
features that may apply to all twisty puzzles.
> (In constructing that
> argument, I see that I failed to mention one (fairly
> obvious) rule: If there is a slice in which both cubies are
> diagonally displaced, twist that one. That rule comes
> before the other which-slice-to-twist rules.) Actually, I
> was somewhat embarrassed to be belaboring what seems rather
> obvious to me. (My friends and I mastered tic-tac-toe when
> we were in the first grade, and that problem strikes me as
> being more difficult than solving MC2D.)
They feel roughly similar in complexity to me. It is actually a pretty
good comparison because when I mapped out the complete game at a
similarly young age I considered all starting corner moves to be
identical in the same way that I enumerate the 8 types of states of MC2D.
My friends and I used to like to play tic-tac-toe in our heads by
mapping squares to the corresponding telephone number pad positions, and
I could only do that by thinking visually. I can't even imagine how to
do that otherwise.
>
> But, again, my criticism was not that anything was "wrong".
> I was just criticizing the graph's value from a practical
> point of view when it comes to actually working the puzzle.
I knew that. I was just saying that I felt you thought that there was a
better practical choice that I could have made. The word "wrong" sums
that up but carries too much negative baggage for that purpose.
> Now there is one rather odd thing you stated in your last
> post that is indeed profoundly wrong:
>
> "With my diagram it is trivial to see that God's number
> must be 3 ..."
>
> What I see is that it takes 4 twists to get from node 2 to
> node 0.
Do'h!
It's true and clear when you allow middle slices, but clearly I
disproved myself about as completely as possible. Thanks for the correction.
> One thing that is frustrating me about this diversion is
> that I thought I had made a real contribution with the Cycle
> Length Signature approach to a succinct but useful way to
> classify the permutation state for any sort of cubie in any
> generalization these puzzles. That approach is closely
> related, as the CLS characterizes the conjugacy class of an
> arrangement. The difference is that these conjugates are
> not limited to conjugation by a symmetry. As it turns out,
> that makes it much easier to identify the CLS class of an
> arrangement; and it leads to a state graph with far fewer
> nodes, which could be viewed as an advantage. Furthermore,
> the insights from the CLS do have real practical
> significance which can be readily applied when solving. I
> thought folks would be excited about this.
Yes, well I suggest that you not take a lack of discussion on your main
point for a lack of interest. I know that there are a lot of very
interested people reading this list who have no intention of ever
posting. Maybe you can generate interest eventually, but you may need to
continue to find ways of clarifying your thoughts even further. That
along with some pretty diagrams may just do the trick! :-)
-Melinda
--------------040103030301030407080404
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Melinda wrote:
> On 8/4/2011 3:02 PM, David Vanderschel wrote:
>> Melinda wrote:
>>> You looked at my diagram and thought that what I was
>>> attempting had something to do with cycles and conjugates
>>> but was just doing it wrong.
>> Melinda, you are making assumptions about what I was
>> thinking that are not only false, but are contrary to what I
>> actually wrote. I hope that, after reading this, you will
>> apologize for the above inappropriate accusation. I hope
>> you will read this post carefully, because it appears that
>> you have failed to do so with my previous posts.
> I most deeply apologize. I should definitely said "I'm
> guessing that you looked at my diagram..." That seems like
> a small qualification, but it is not at all. You are right
> to call me on it and I appreciate the risk you took in
> doing that. My pennance will be to try to read this
> message all the more carefully as you suggest.
I am relieved. I did not want to turn this into a fight,
but I did not want to ignore it either. I accept the apology.
>> It was Andrew Gould who straightened this out, providing
>> a way to specify the equivalence relation that gives rise
>> to your partition. It is mathematically sound and
>> elegantly simple. And, as it turns out, conjugating is
>> the way it's done.
> I don't know if it is correct to say it is THE way it's
> done. It certainly is A way, and possibly even the BEST
> way. This point was one of the things that I was trying to
> get across. I'm sure that from your point of view it is
> definitely the right way. I'm just pointing out that there
> are other ways of looking at it. That was why I harped on
> the question of purpose or utility.
Actually, I believe that conjugation is quite validly
another way of describing my present interpretation of how
Nan was trying to describe your partitioning 'algorithm'. I
can rephrase what he was saying as "Two permutations are
related if there is a way to pick up the whole puzzle and
put it back down turned and/or flipped in such a way that
the permutations can be seen to be the same." That does not
require worrying about colors. All you need to see is that,
relative to positions in fixed space (independent of the
orientation of the puzzle), the actual permutation movements
of the cubies are the same. (If they do match up, then
there would be an appropriate recoloring. It is just that
you don't actually have to think about that aspect of it.)
But note that, again relative to fixed space positions,
picking up the puzzle and putting it back down does achieve
a particular permutation of the cubies. That permutation is
one which arises from a symmetry. If it does make the
permutations match up, then they are conjugates of each
other by that symmetry.
To look at it the other way around: Consider a particular
twist sequence relative to fixed space positions. Do it
with the initialized puzzle in standard orientation, and you
get permutation #1. Now initialize the puzzle, reorient it,
do the same sequence, and put the puzzle back in standard
orientation to get permutation #2. As a permuter, the
put-back is the inverse of the reorient. So permutation
#2 is a conjugate of #1 by the permutation (in fixed space)
that the reorientation induces.
My point is that conjugation is _not_ an orthogonal issue when
we are talking about making things match up by reorienting
the whole puzzle in space. In fact, I immediately moved
from Nan's description, in rotation terms only, to talking
about conjugating with a rotation, as I perceive the
concepts as being equivalent - as they are in fact.
>> Now there is one rather odd thing you stated in your last
>> post that is indeed profoundly wrong:
>>
>> "With my diagram it is trivial to see that God's number
>> must be 3 ..."
>>
>> What I see is that it takes 4 twists to get from node 2 to
>> node 0.
>
> Do'h!
> It's true and clear when you allow middle slices, but clearly I
> disproved myself about as completely as possible. Thanks
> for the correction.
I would argue that it still takes 4 twists even if you allow
center slice twists. If you take the 2->4->3->0 path, the
puzzle winds up upside down or mirror imaged, something that
should not be able to happen in 2-space. If you take the
2->1->0 path, the puzzle winds up rotated by 180 degrees.
You can't fix either situation in 2 twists.
I never paid much attention to the center slice twists
precisely because they reorient the whole puzzle by a
reflection. If you fix that by picking up the puzzle and
putting it back down in standard orientation, then you see
that what you have accomplished is actually 2 2-cycle type
twists. So if you count a center slice twist as 2 twists
and don't worry about disoriented puzzles, it still takes 4
twists to get from 2 to 0. I think it is entirely appropriate
that the implementation of MC2D does not permit
center slice twists.
>> One thing that is frustrating me about this diversion is
>> that I thought I had made a real contribution with the Cycle
>> Length Signature approach to a succinct but useful way to
>> classify the permutation state for any sort of cubie in any
>> generalization these puzzles. That approach is closely
>> related, as the CLS characterizes the conjugacy class of an
>> arrangement. The difference is that these conjugates are
>> not limited to conjugation by a symmetry. As it turns out,
>> that makes it much easier to identify the CLS class of an
>> arrangement; and it leads to a state graph with far fewer
>> nodes, which could be viewed as an advantage. Furthermore,
>> the insights from the CLS do have real practical
>> significance which can be readily applied when solving. I
>> thought folks would be excited about this.
> Yes, well I suggest that you not take a lack of discussion
> on your main point for a lack of interest. I know that
> there are a lot of very interested people reading this
> list who have no intention of ever posting. Maybe you can
> generate interest eventually, but you may need to continue
> to find ways of clarifying your thoughts even
> further. That along with some pretty diagrams may just do
> the trick! :-)
OK. Diagram (though not so pretty):
S11111
|
S1111 |
| |
S221 | S311
/ \ | / \
S22 S31~ S111
\ | ~ /
\ | ~/
\ | S5 /~
\ |/ / ~
[ S3 ]----S11
|
S
The nodes correspond to conjugacy classes as identified by
my CLSes. These are the transitions that can be achieved by
using solving moves that result in 3-cycles. It applies
when only 5 or fewer cubies (of any set that can occupy the
same positions) remain unplaced. It assumes that, when 1
cubie is moved to its home location, it arrives with correct
orientation; and, when 2 cubies are moved to their home
positions, at least 2 cubies wind up with correct
orientation. Any edge with a downward component corresponds
to a reduction of CLSC by 2 (excepting the bottom finishing
transition, for which the reduction is 4). I indicated the
S31->S11 transition in the strange manner with "~"s, as it
should be avoided. (That also addressed the problem that I
did not find a way to draw the graph without an
edge-crossing.)
The conjugacy classes are defined purely in terms of the
permutations of the cubies. They are independent of the
orientations, except that wrongly oriented cubies in their
home positions (i.e., stuck cubies) are counted as 1-cycles.
Though this graph could easily be extended to allow for more
than 5 unplaced cubies, I am not sure that has any practical
significance. The more cubies there are that are unplaced,
the harder it is to 'see' the CLS. However, the practical
significance really only comes into play in the end game.
The theory behind it assures that you are not wasting moves
prior to getting down to 5 unplaced as long as you are
always placing 2 cubies, placing 1 cubie and merging 2
cycles, or merging 3 cycles. (What I personally tend to do
in practice is that I try to deal with cubies stuck at home
first. If I merge such a stuck cubie into another cycle (of
length 2 or more), I can place one cubie. The setup is
easier if you only have to get the orientation right on 1
cubie; so the stuck cubies, as obnoxious as they may be, can
at least be exploited in this sense. In particular, from S221,
I always go to S22; and, from S311, to S31.)
One interesting point, which I failed to make earlier, is
that, when you are down to 4 unplaced cubies, you should not
even _look_ for a way to place 2. If the CLS is S22 or
S1111, it cannot be done. If the CLS is S31, it _should_
not be done. What is important is to see if any of the four
is stuck at home, in which case it must be moved.
Another interesting point is that, with 5 unplaced cubies,
you can finish in only 2 steps whenever there are no stuck
cubies. In a random permutation of n things, the expected
number of unmoved things is 1 and the probability that all
are moved is 1/n; so it is fairly common to wind up with a
5-cycle when 5 cubies are unplaced. In my experience with
the puzzles, it seems to be more common than one time out of
five. (If that's true, I think there may be an explanation
of it in terms of the fact that an unmoved cubie may well be
oriented correctly, but I have not figured out how to make the
argument precise.) Except for S1111 (rare), when 4 cubies
are unplaced, you can always finish in 2 steps.
To make sure that the plain text graph looks right, I am
going to force Lucida Console again. I hope it does not
turn out as ugly as last time.
Regards,
David V.
--------------040103030301030407080404
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
There was another response I wanted to make to Melinda; but
it somehow slipped past me last time around.
A revised (according to what I already wrote in my second to
last post) version of what I had written (even earlier):
>> For the purpose of actually solving the puzzle, I offer:
>> Whenever any cubie is diagonally displaced, then, to
>> get a shortest solution, you must immediately do a
>> twist that moves at least one such diagonally
>> displaced cubie. If there is a slice in which both
>> cubies are diagonally displaced, twist that one. If
>> a diagonally displaced cubie is not in a slice with
>> another diagonally displaced one, there are two
>> slices you can twist. If twisting one of them will
>> place the other cubie in it, twist that slice. If
>> twisting one of them will displace the other cubie
>> from its home position and twisting the other slice
>> won't do that, twist the other. When no cubie is
>> diagonally displaced, the solution is obvious.
>> Not only is that much easier to grok than your graph, a
>> few more lines of reasoning will prove that it always
>> leads to a solution in 4 or fewer twists.
Melinda wrote:
> That statement is not at all convincing to me. I'm sure
> that it works for you, and possibly for mathematicians who
> think symbolically, but half of the world consists of
> visual thinkers like me for whom a diagram is often more
> convincing.
I was trying to avoid belaboring the obvious again; but here
goes: If, after the first 1 or 2 twists according to the
above rules, you have not already solved the puzzle, then,
after 2 twists, there are no more diagonally displaced
cubies. Furthermore, you must then have just one 2-cycle on
an edge (odd, 1 twist) or 2 2-cycles on opposite edges
(even, 2 twists).
Node 7, corresponding to a rotational 4-cycle, is a bit odd
in that the rules give no preference for which slice to
twist first. It makes no difference. But after that first
twist, there will be one diagonally displaced cubie which
must be dealt with on the second twist. Anyway, the node 7
case does contradict the final 'rule': "When no cubie is
diagonally displaced, the solution is obvious." That's
guaranteed to be true only when there had been a diagonally
displaced cubie at an earlier stage. However, the symmetry
of the situation for node 7 is such that all initial twists
are effectively the same, so there is no way to do the first
twist wrong. So, in that sense, the first step of the
solution is still "obvious". After that, the rules will
lead you from a permutation in node 5 to one in node 3, from
which "even a cave man can do it".
> Further, the subject of diagonals seems to only apply to a
> small class of puzzles whereas I am looking for the
> unifying graph-theoretic features that may apply to all
> twisty puzzles.
I am not sure what the significance of this remark is. I
never claimed to be offering a way to solve anything but
MC2D. The diagonally displaced cubies are the ones that
cause the biggest 'problems', so you have to concentrate on
addressing them as early as possible.
As far as what you are looking for goes and judging by what
we have seen so far, I expect that it will be primarily of
academic interest; and we have not seen the fullness of it
yet. In any case, the point here was that the use of the
graph for MC2D is a very cumbersome way for a human to go
about achieving an actual solution of the puzzle. I have
offered a bit of detail on the no-more-than-4-moves-required
proof based on my very simple method for MC2D because you
claimed that the statement, "A few more lines of reasoning
will prove that it always leads to a solution in 4 or fewer
twists.", was "not at all convincing" to you. There are a
few more details to consider if you also want to prove that
the rules always lead to a shortest solution, which they do.
You should be able to convince yourself easily enough by
applying the rules to the representative permutations for
nodes 2, 4, 5, 6, and 7 of your diagram. (1 and 3 are the
already-obvious ones.) The rules will always send you to
the next node on the solution path.
If the "not at all convincing" 'statement' for you was was
the introductory "Not only is that much easier to grok than
your graph, ...", I do not know what to say aside from
pointing out that many folks have failed initially to
understand where the graph comes from or how to use it. I
believe my rules admit easy interpretation and application,
especially since the rules will all seem quite reasonable to
anyone who already understands the puzzle.
I am not sure I understand the relevance of your reference
to symbolic vs. visual thinking. The rules I specified
easily admit visual interpretation. Indeed, that is how I
think of them. Even checking the proof involves little but
visual thinking. (I could make it analytical, but that
would make it less easy to understand for a problem that is
this simple to start with.) From my point of view, your
graph reeks of much greater abstraction and analyticity,
especially since it is not so easy to explain exactly what
an edge means. (And the solution to that problem is not so
visual.) Note that I do not mind the analyticity, but you
seem now to be making an argument against it.
The CLS-based graph I have suggested is rather different in
the sense that an edge of the graph does not correspond to a
twist, but to the result of a move sequence whose effect is
a 3-cycle. However, I think that approach may well
generalize to non-cubical twisty puzzles (with which I have
relatively little direct experience). However, I am not so
sure about whether correct orientation can always be
achieved (in one 3-cycle step) on 2 pieces from the same
cycle of the puzzle's permutation state. I know I can do
that for cubical generalizations.
Regards,
David V.
