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