Message #1830

From: Melinda Green <melinda@superliminal.com>
Subject: Re: [MC4D] State graph of MC2D
Date: Sat, 30 Jul 2011 18:08:17 -0700

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:<http://www.superliminal.com/cube/mc2d.html>.
>
> 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<http://www.superliminal.com/cube/mc2d.html> is for types but not states. So what is the the graph for states then?
>
> Not allowing middle slice moves, there are 4!=24 states. The graph with 24 nodes for the 24 states should be a regular graph:
>
> <http://f1.grp.yahoofs.com/v1/wGI0Ti16CBMVhSw-vS1HGyxlywZzdh_YztS9EboUAeUX1H9QqCXq2MQrB_Mkjk_GrrZYyVu2sqhW2nK8wdXJnaWKM22sc9AJ/Nan%20Ma/MC2D/color.gif>
>
> 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<http://www.superliminal.com/cube/mc2d.html>. The two blue nodes are type-1. In general the RGB color of the nodes is the binary expansion of the type. For example, since 5(dec)=101(bin), type-5 is RGB=101=magenta. An exception is that type-7 (111) is gray instead of white, because gray is more visible than white.
>
> I have another illustration where the 24 states are fully described by numbers.
>
> <http://f1.grp.yahoofs.com/v1/wGI0TuNk-WEVhSw-WG2cxR30WClk8ghMblJofhY3RlRtZm_nNz86DNFwYOKOPFfSK8jt2FTGsXXpQdG9XqXmGNB0lYaQ-5xt/Nan%20Ma/MC2D/labels.gif>
>
> 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<http://www.superliminal.com/cube/mc2d.html> and the graph for states (my version) in this post, 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 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."