Home »

Syllables and Graphs

Submitted by Jerry Bryan on Sat, 11/14/2009 - 14:27.

I've been reading a little bit about graph theory, and I wish I knew more about it.  So pardon what may perhaps be a bit of naiveté about graphs on my part.

I suspect that everyone who reads this forum is familiar with Cayley graphs and how they relate to Rubik's cube space.  One of the best references in this regard may be found at http://www.jaapsch.net/puzzles/cayley.htm  I also suspect who everyone reads this forum is familiar with the concept of doing a breadth first search while storing all the results as a way of investigating a space such as the Cayley graph for Rubik's cube.

For example, one can begin a depth first search at the Start position and thereby identify all positions that are 1 move from Start, 2 moves from Start, 3 moves from Start, etc.  It would be extremely inefficient, but eventually such a search would identify the distance from Start for any particular position x.

Let's turn that breadth search on its head for a second.  Instead of beginning at the Start position, let's begin at x and thereby identify all the positions that are 1 move from x, 2 moves from x, 3 moves from x, etc.  Eventually such a search would encounter the Start position and would thereby identify the distance of x from Start by searching in the other direction.  This search would be just as inefficient as the previously described procedure of searching from Start to x.

We can make the search from x to Start more efficient as follows.  Instead of storing all the moves that are 1 move from x, 2 moves from x, etc., we store only those moves that are actually getting closer to Start.  So we store only those positions that are 1 move from x and n-1 moves from Start, positions that are 2 moves from x and n-2 moves from Start, positions that are 3 moves from x and n-3 moves from Start, etc.

This is scarcely a new idea.  I'm borrowing copiously from the ideas of others.  Also, the search I'm describing can obviously be very technically challenging because in general it's not very easy to know that x is n moves from Start, and it's not very easy to know which moves are k moves from x and also are n-k moves from Start.  But in a finite search space, the search is conceptually possible.

The search from x to Start that I'm describing may be diagrammed with a graph that is a subset of the Cayley graph for cube space.  Let's call such a graph for x the solution graph for x.  Here are a few examples.  I'll be working in the quarter turn metric. 

    Position         Solution Graph

1.     F                I--F

2.     FR               I--F--FR

                          F
                         / \
3.     FB=BF            I   FB
                         \ /
                          B

                          F
                         / \
4.     FBU=BFU          I   FB--FBU
                         \ /
                          B

                          F    FBU
                         / \  /    \
5.     FBUU=BFUU=       I   FB      FBUU
       FBU'U'=BFU'U'     \ /  \    /
                          B    FBU'

Let's look the following five positions in terms of syllables.  I will be using my newer, more general definition of a syllable rather than Dan Hoey's original definition of a syllable.

  • Position #1 is a syllable because it is a position of length 1.  Positions of length 1 are a special case in the definition of syllables.
  • Position #2 is a non-syllable.  It is a non-syllable roughly speaking because there is only one sequence of quarter turns that produces the position.  More precisely, position #2 is a position of length 2.  When it is written in terms of syllables that are of length less then 2, there is only one sequence of fully joined syllables that will produce the position.  That's because the only syllables that are of length less than 2 are of length 1, and we would write position #2 uniquely in terms of shorter syllables as (F)(R).
  • Position #3 is a syllable.  It is a syllable because the position may be written in terms of syllables that are of length less than 2 in two or more ways: (F)(B) and (B)(F).  These different ways of writing the position manifest themselves as two different paths through the solution graph: I--F--FB and I--B--FB.  However, by the time we get around to testing positions of length 3 or more, we would no longer write position #3 in two different ways.  We would write it as a syllable simply as (FB), and we would write it as a path simply as I----FB.  So we would write it as two different compositions into shorter syllables only to test it, and we would write it as two different paths only to test it.  After testing it and determining that it is a syllable, we would write it as a single syllable that is not decomposed, and we would write it as a single and unique path through a solution graph.
  • Position #4 is a non-syllable.  It has two different maneuvers in terms of quarter turns: FBU and BFU.  However, the definition of syllables is not in terms of quarter turns.  The definition is in terms of fully joined syllables that are shorter than the position.  Position #4 is of length 3 and we therefore are allowed to construct position #4 using syllables of length 1 or 2.  The two obvious possibilities are (FB)(U) and (BF)(U).  But (FB) and (BF) are two different names for the same syllable.  Hence, there is only one sequence for FBU=BFU in terms of fully joined syllables of length 1 and 2, and FBU=BFU is a non-syllable.
    • If we write the path through the solution graph for position #4 in terms of fully joined syllables, we might write it as something like I----FB--FBU, so the path is unique.  We are thinking of FB=BF as if it were a single move that's of length 2.  But it's not like in the face turn metric where FF becomes written as F2 or F2 and is of length 1.  The unique path I----FB--FBU is still of length 3 - a syllable of length 2 followed by a syllable of length 1.
    • We may also write position #4 in terms of syllables as either (F)(B)(U) or as (B)(F)(U).  But neither of these decompositions of position #4 into syllables is fully joined because (F)(B) may be joined to form the syllable (FB), and (B)(F) may also be joined to form the syllable (FB).
  • Position #5 is a non-syllable.  It has four different maneuvers in terms of quarter turns: FBUU, BFUU, FBU'U', BFU'U'.  But when written in terms of fully joined syllables of length 3 or less, there is only one way to write position #5: (FB)(UU).  The unique path through the solution graph for position #4 is I----FB----FBUU - a syllable of length 2 followed by another syllable of length 2. 
    Position         Solution Graph

                              FF--FFB-----\
                             /   / / | \   \
                            F--FB /  |  |  |
                           /     /   /  /  /
                          /   F'F'  /  /  /
6.     FFB=FBF=          /   /     /  /  /
       BFF=F'F'B=       I--F'-- F'B  /  /
       F'BF'=BF'F'       \          /  /
                           B--BF---   /
                            \        /
                             BF'----/

  • Position #6 is a syllable that is much more complicated than the first five.  It has six different maneuvers in terms of quarter turns, but that is not the reason that it is a syllable.  It has a complicated solution graph that I had a hard time drawing just with text characters, but that is not the reason that it is a syllable.  It is a syllable because it is of length 3 and there is more than one way to write it in terms of fully joined syllables that are of length 1 or 2: (FF)(B), (F)(FB), (FB)(F), (B)(FB), (F')(F'B), and (F'B)(F').  All the other apparent possibilities such as (F'F')(B) are just alternate names for the ways that have already been listed.

    In terms of syllables of length 1 or 2, we could write the paths through the solution graph for position #6 as follows: I----FF--FFB, I--F----FFB, I----FB--FFB, I--B----FFB, I--F'----FFB, and I----F'B--FFB.  But after testing FFB and determining that it is a syllable, we would write its unique path through a solution graph simply as I------FFB. 

    Position         Solution Graph


                       U--UR--URU'--URU'B'--URU'B'R
                      /                            \
7.     URU'B'RB=     I                              URU'B'RB
       RBU'B'UR       \                            /
                       R--RB--RBU'--RBU'B'--RBU'B'U

  • Position #7 is a syllable.  It is much simpler than position #6, but it is much longer than any of the other examples.  It is included to exemplify the syllables of length 6 that can be discovered by looking at Herbert Kociemba's list of 12q identities.

The way these solution graphs have been drawn, they include a single leftmost node which is Start and a single rightmost node which is x.  We may describe Start as being 0 moves from Start and n moves from x.  We may describe x as being n moves from Start and 0 moves from x.  In between, there are intermediate nodes that we may describe as being k moves from Start and n-k moves from x for 1 < k < n.  We let h(k) be the number of intermediate nodes that are k moves from Start and n-k moves from x.  Note that h(x) is not defined for Start nor for x.

Definition: A node in the solution graph for x for which h(k) = 1 is a singular node for the solution graph for x.

Proposition.  A position x of length 1 or greater is a non-syllable if and only if its solution graph contains at least one singular node.  Otherwise, x is a syllable.  As a practical matter, this result means that syllables must either be of length 1 or else their solution graphs must not contain any singular nodes.  This is our principle result.

Proof.

It's best to treat syllables of length 1 as a special case.  They do not contain any intermediate nodes.  Therefore, they do not contain any singular nodes. 

Case 1.  Suppose a position x of length 2 or greater is a non-syllable.  That means that x has a unique decomposition into fully joined syllables each of which is shorter than the length of x.  We may write x as x=s1s2...sk.  We need to show that there is at least one singular node.  To this end, it suffices to note that the position immediately to the right of s1 is a singular node.  That is, because x is a syllable, s1 is a unique leftmost syllable when x is decomposed into fully joined syllables.  There may be multiple paths through s1, but by definition all such paths must end at the same node at the right end of s1.

Case2.  Suppose the solution graph for a position x contains a singular node.  We must show that x is a non-syllable.  We can write x as x = pipj where |x| = |pi| + |pj| and where the singular node is the position immediately to the right of pi.  Both pi and pj may be either syllables or non-syllables.  If either of pi and pj are syllables, we may write them as si and sj, respectively.  If either of pi and pj are non-syllables, we may decompose them uniquely into syllables as si_1si_2...si_k and sj_1sj_2...si_m, respectively.  So whether either of pi and pj are syllables or non-syllables, we can use the singular node to guide us to a decomposition of x into fully joined syllables, each of which is shorter than x.  The question them becomes whether this decomposition is unique.

The only way the decomposition would not be unique would be if there were another decomposition that contained a syllable that straddled the singular node.  For example, consider position #5 which is FBUU.  There a singular node after FB, and the unique decomposition into fully joined syllables of length 3 or less is (FB)(UU).  But in the more general case, we might consider the possibility that (FB)(UU) is not a unique decomposition of the position.  For example, we might try to decompose position #5 as (F)(BU)((U), with (BU) being a "potential syllable" that straddles the singular node.  Of course, (BU) is not a syllable, so (F)(BU)(U) is not a decomposition of position #5 into syllables.  There is not a syllable that straddles the singular node in this case, but we need to show that it's never possible for a syllable to straddle a singular node.

To that end, suppose that there is a syllable s that contains a singular node.  Such a syllable can't be of length 1, and therefore must be a syllable of length 2 or more that has more than one decomposition into a sequence of shorter syllables that are fully joined.  For this syllable s, the analysis is the same as for the original position x.  That is, it's easy to find one decomposition of the syllable s into shorter syllables such that none of the shorter syllables straddles the singular node.  We then need to find another decomposition of the syllable into shorter syllables such that one of the shorter syllables straddles the singular node.  But that shorter syllable must have at least two decompositions, at most one of which does not contain the singular node.  The result is an infinite regress of shorter syllables, each of which straddles the singular node.  Therefore, a syllable may not straddle a singular node.

I've been working on an algorithm to identify and count all syllables out to some distance n from Start.  A key element of the algorithm is a syllable tester.  That is, given a position x, is x a syllable or a non-syllable? I was having trouble finding a fast syllable tester using the original syllable definition.  It seems much faster computationally to determine if a position x has a singular node or not than to find all the unique decompositions of x into fully joined syllables, each of which is shorter than x.

» login or register to post comments | previous forum topic | next forum topic