Message #1829

From: schuma <mananself@gmail.com>
Subject: State graph of MC2D
Date: Sat, 30 Jul 2011 20:13:54 -0000

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."

Nan