# Message #1836

From: David Vanderschel <DvdS@Austin.RR.com>

Subject: Re: State graph of MC2D

Date: Wed, 03 Aug 2011 02:54:30 -0500

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<br>
sequences) which accomplish 3-cycles. If 3 cubies are<br>
already permuted in a 3-cycle relative to their home<br>
positions, then doing a move which accomplishes the<br>
reverse 3-cycle can place two of them with correct<br>
orientation. If the third one comes out with correct<br>
orientation, that is just a matter of luck. You cannot<br>
normally count on it unless the 3 cubies are the last<br>
unplaced cubies in the set.
So, unless you get the good luck, we can see that the<br>
best a 3-cycle can do is to reduce the CLSC by 2: If<br>
the 3 cubies we permute are in a cycle of length greater<br>
than 2, then the unplaced cubies of the original cycle<br>
will be in a cycle of length 2 less than we started<br>
with, and the number of cycles in the CLS will remain<br>
the same. (The preceding assumes that the 2 cubies<br>
which are placed are placed with correct orientation,<br>
and this is possible in general.) If the 3 cubies we<br>
permute come from 2 different cycles and one of them is<br>
a cycle of length 2 or more, then we can only place one<br>
of them. However, the cycles are merged. So we reduce<br>
the sum of the cycle lengths by 1 and the number of<br>
cycles by 1. If the 3 cubies we permute come from 3<br>
different cycles, then we can place none of them, but<br>
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,<br>
S22, S31, S1111,<br>
S3, S111,<br>
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<br>
S221 -> S22 or S31 8 -> 6<br>
S311 -> S111 or S31 8 -> 6<br>
S1111 -> S31 8 -> 6<br>
S5 -> S3 6 -> 4<br>
S22 -> S3 6 -> 4<br>
S31 -> S11 or S3 6 -> 4<br>
S111 -> S3 6 -> 4<br>
S11 -> S3 4 -> 4<br>
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.