Message #1849

From: David Vanderschel <DvdS@Austin.RR.com>
Subject: Re: [MC4D] State graph of MC2D
Date: Fri, 05 Aug 2011 23:06:34 -0500

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.