On Tuesday, August 12, "Melinda Green"
>I arrived at the conclusion that MC2D contains
>exactly 8 states by simply recording every sticker
>pattern that I was able to produce using the puzzle,
>ignoring all duplicates due to color or positional
>symmetries. I'm pretty sure there are only 8 of them.
Melinda, I am sorry; but I am still very unsure about
what you mean by a "state". Since the 4 face 2-cubies
exist, they give the puzzle a fixable orientation that
does not admit positional symmetries. Their presence
also makes it difficult for me to see how there could
be color symmetries as well. (They also prevent
mirror symmetries.) I thought, "Maybe she's talking
about the 2x2 version of the 2D puzzle." Then you can
remove a rotational symmetry - leaving 6 possible
permutations. But that's not "8" either. In this
2x2 case, you can also remove a mirror symmetry, thus
leaving only 3 'states'.
>I gave each of them a number and then mapped out all
>the possible transitions between the those states to
>produce the complete graph for the puzzle. Perhaps
>there are 24 states if you don't mind duplicates, but
>since arriving at one state gives exactly the same
>options as arriving at symmetrical twins, it seems
>best to collapse all duplicates into the same logical
>state and leave only a graph containing all the truly
>unique states. I attempted to include an ASCII
>diagram in the post that you replied to
>(http://games.groups.yahoo.com/group/4D_Cubing/message/329)
>but unfortunately Yahoo stripped out my spacing
>characters and left a bit of a mess. I should
>probably sketch it up again in Visio or other
>diagraming tool for clarity.
I am struggling to discover your 8 'states'. I have
found a way of classifying the permutations into 8
classes with the following descriptions of a member of
each class:
0. Two disjoint adjacent corner pairs swapped. 2 such. even.
1. The identity. 1 such. even.
2. Both diagonal corner pairs swapped. 1 such. even.
3. One pair of adjacent corners swapped. 4 such. odd.
4. One pair of diagonal corners swapped. 2 such. odd.
5. One stationary corner and a 3-cycle. 8 such. even.
6. A 4-cycle with moves only to adjacent corners. 2 such. odd.
7. A 4-cycle with diagonal moves. 4 such. odd.
(For the counts: 1: horizontal or vertical swaps. 3:
which side. 4: which diagonal. 5: which corner is
stationary and the direction of the rotation for the
3-cycle. 6: which direction. 7: six total possible
4-cycles minus the 2 circular-order-preserving ones.)
The counts do add up to 24.
So I found 8 possibly relevant somethings. However, I
don't see how to talk about transitions between
classes in a very useful way. I have trouble thinking
of the classes of permutations as "states". I
certainly do not view two members of the same class as
"duplicates". In terms of the resulting new class,
the effect of a twist on a member of a class depends
on which member of the class was picked. There is no
nice equivalence that allows the classes to play as
elements of a group.
For any pair of the above classes, you can talk about
whether, given a specific first permutation from one
class, there exists a second permutation belonging to
the other class and a twist that will transform the
first into the second. Clearly no such permutation
and twist exist if both classes have permutations of
the same parity. The types of transitions for which
the possibility exists include 1-3, 0-3, 3-5, 2-7,
4-5, 5-6, and 5-7. Not possible: 2-4, 1-7, 1-8. Etc.
I think that what is described above is somewhat like
your own graph, for which I have a copy of your
original:
0 . . 1 . . 2
\ / \ /
\ / \ /
3 . . 4
\ /
\ /
5
/ \
/ \
6 . . 7
(I recommend viewing with a fixed width font.)
I think I may even have managed to make my numbering
system match whatever you were doing. However, I
don't see the "1 . . 2", "3 . . 4", "6 . . 7", or
"4 / / 2" relations. Indeed, to get from 1 to 2
without center slice twists, I have to go via 7. My
version of the graph would look like this:
0 1
\ / \
\ / \
3 4
\ /
\ /
5
/ \
/ \
6 7
\
\
2
Note that permitting center slice twists does also
enable 0-1, 0-2, 3-3, 5-5, 6-6, and 7-7. (I am
assuming that flipping two opposing slices at the same
time is equivalent to a center slice twist.) But it
also enables strange transitions like 4-6 and 3-7, so
this does not seem like a very interesting angle to
pursue. It would certainly make the graph look messy.
Assuming that I have managed to get close to what you
were talking about, I must say that I still don't "get
it". What is the important insight which results from
this way of classifying the permutations? We seem to
have derived something complicated from a relatively
simple situation. The complications will only get
worse if we try to generalize the approach to a higher
dimensional puzzle. I do not feel enlightened, so I
must still be missing something. The analysis does
prove that no two permutations are more than 4 twists
apart; but, with only 24 permutations to start from,
that would not have been difficult to prove without
doing the classifications. And, again, extending this
'diameter' argument to higher dimensions does not look
to me like it would be tractable.
Regards,
David V.
--------------010303040300070301070100
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
David,
Do attachments work in Yahoo group messages now? I don't remember but
I'm going to try to attach a version of my graph that I just made which
should clarify what I'm trying to say about states. It uses the same
layout as my ASCII graph but includes small pictures of each state. The
lines indicate the simple edge twists. The dotted lines between
horizontally adjacent states in the original version indicated states
that could be reached via a single middle slice twist if the applet
supported that. It is easy to see that in the first row. It takes a
little more work to see that in the other rows because you need to
figure out whether it requires the horizontal or vertical middle slice
and then account for positional and color symmetries. What I mean by
color symmetry is that you should be able to rename any of the colors at
any time without changing the state. It's all about the particular
patterns of each state that matter and there appear to be exactly 8
unique ones.
We can call this the graph-theoretic approach as opposed to your
group-theoretic approach. Perhaps one can arrive at some of the same
conclusions either way such as that the diameter of the graph is 4
(because it takes a minimum of 4 twists to solve the puzzle starting
from the checkerboard state #2). Both approaches are probably useful for
different purposes. The thing I like best about the graph is that it
makes you wonder which features of it should carry over to the larger
puzzles and what the implications of those features would be if they
could be proved. For example, might all such twisty puzzles contain
something like state #5 that acts like a sort of nexus? I would really
love to see equivalent state diagrams for other, slightly larger puzzles
such as the 3x4 and 4x4. In 3D, the Pyraminx and the 2^3 might be good
"medium" sized candidates but would certainly require computer-assisted
graph layout tools to diagram well.
-Melinda
David Vanderschel wrote:
> On Tuesday, August 12, "Melinda Green"
>
>> I arrived at the conclusion that MC2D contains
>> exactly 8 states by simply recording every sticker
>> pattern that I was able to produce using the puzzle,
>> ignoring all duplicates due to color or positional
>> symmetries. I'm pretty sure there are only 8 of them.
>>
>
> Melinda, I am sorry; but I am still very unsure about
> what you mean by a "state". Since the 4 face 2-cubies
> exist, they give the puzzle a fixable orientation that
> does not admit positional symmetries. Their presence
> also makes it difficult for me to see how there could
> be color symmetries as well. (They also prevent
> mirror symmetries.) I thought, "Maybe she's talking
> about the 2x2 version of the 2D puzzle." Then you can
> remove a rotational symmetry - leaving 6 possible
> permutations. But that's not "8" either. In this
> 2x2 case, you can also remove a mirror symmetry, thus
> leaving only 3 'states'.
>
>
>> I gave each of them a number and then mapped out all
>> the possible transitions between the those states to
>> produce the complete graph for the puzzle. Perhaps
>> there are 24 states if you don't mind duplicates, but
>> since arriving at one state gives exactly the same
>> options as arriving at symmetrical twins, it seems
>> best to collapse all duplicates into the same logical
>> state and leave only a graph containing all the truly
>> unique states. I attempted to include an ASCII
>> diagram in the post that you replied to
>> (http://games.groups.yahoo.com/group/4D_Cubing/message/329)
>> but unfortunately Yahoo stripped out my spacing
>> characters and left a bit of a mess. I should
>> probably sketch it up again in Visio or other
>> diagraming tool for clarity.
>>
>
> I am struggling to discover your 8 'states'. I have
> found a way of classifying the permutations into 8
> classes with the following descriptions of a member of
> each class:
>
> 0. Two disjoint adjacent corner pairs swapped. 2 such. even.
>
> 1. The identity. 1 such. even.
>
> 2. Both diagonal corner pairs swapped. 1 such. even.
>
> 3. One pair of adjacent corners swapped. 4 such. odd.
>
> 4. One pair of diagonal corners swapped. 2 such. odd.
>
> 5. One stationary corner and a 3-cycle. 8 such. even.
>
> 6. A 4-cycle with moves only to adjacent corners. 2 such. odd.
>
> 7. A 4-cycle with diagonal moves. 4 such. odd.
>
> (For the counts: 1: horizontal or vertical swaps. 3:
> which side. 4: which diagonal. 5: which corner is
> stationary and the direction of the rotation for the
> 3-cycle. 6: which direction. 7: six total possible
> 4-cycles minus the 2 circular-order-preserving ones.)
>
> The counts do add up to 24.
>
> So I found 8 possibly relevant somethings. However, I
> don't see how to talk about transitions between
> classes in a very useful way. I have trouble thinking
> of the classes of permutations as "states". I
> certainly do not view two members of the same class as
> "duplicates". In terms of the resulting new class,
> the effect of a twist on a member of a class depends
> on which member of the class was picked. There is no
> nice equivalence that allows the classes to play as
> elements of a group.
>
> For any pair of the above classes, you can talk about
> whether, given a specific first permutation from one
> class, there exists a second permutation belonging to
> the other class and a twist that will transform the
> first into the second. Clearly no such permutation
> and twist exist if both classes have permutations of
> the same parity. The types of transitions for which
> the possibility exists include 1-3, 0-3, 3-5, 2-7,
> 4-5, 5-6, and 5-7. Not possible: 2-4, 1-7, 1-8. Etc.
>
> I think that what is described above is somewhat like
> your own graph, for which I have a copy of your
> original:
>
> 0 . . 1 . . 2
> \ / \ /
> \ / \ /
> 3 . . 4
> \ /
> \ /
> 5
> / \
> / \
> 6 . . 7
>
> (I recommend viewing with a fixed width font.)
>
> I think I may even have managed to make my numbering
> system match whatever you were doing. However, I
> don't see the "1 . . 2", "3 . . 4", "6 . . 7", or
> "4 / / 2" relations. Indeed, to get from 1 to 2
> without center slice twists, I have to go via 7. My
> version of the graph would look like this:
>
> 0 1
> \ / \
> \ / \
> 3 4
> \ /
> \ /
> 5
> / \
> / \
> 6 7
> \
> \
> 2
>
> Note that permitting center slice twists does also
> enable 0-1, 0-2, 3-3, 5-5, 6-6, and 7-7. (I am
> assuming that flipping two opposing slices at the same
> time is equivalent to a center slice twist.) But it
> also enables strange transitions like 4-6 and 3-7, so
> this does not seem like a very interesting angle to
> pursue. It would certainly make the graph look messy.
>
> Assuming that I have managed to get close to what you
> were talking about, I must say that I still don't "get
> it". What is the important insight which results from
> this way of classifying the permutations? We seem to
> have derived something complicated from a relatively
> simple situation. The complications will only get
> worse if we try to generalize the approach to a higher
> dimensional puzzle. I do not feel enlightened, so I
> must still be missing something. The analysis does
> prove that no two permutations are more than 4 twists
> apart; but, with only 24 permutations to start from,
> that would not have been difficult to prove without
> doing the classifications. And, again, extending this
> 'diameter' argument to higher dimensions does not look
> to me like it would be tractable.
>
> Regards,
> David V.
--------------010303040300070301070100
Content-Type: application/x-ygp-stripped
Content-Transfer-Encoding: 7bit
Content-Type: image/png;
name="3x3-state-graph.png"
Content-Transfer-Encoding: base64
Content-Disposition: inline;
filename="3x3-state-graph.png"
--------------010303040300070301070100--
I know it's gauche to reply to your own message but I see that attached
images get forwarded properly but are scrubbed before before before
being saved in the archive. I therefore uploaded the state graph diagram
and am including the permalink here so we'll be able to find it when the
subject comes up again in another two years. :-)
http://games.ph.groups.yahoo.com/group/4D_Cubing/photos/view/7317?b=8
I'll probably also post it on the web site eventually as my solution.
Just find your state, and when you can't move any further up or to the
left, it's solved!
-Melinda