Home »

All the Syllables, Corners Group, Quarter Turn Metric

Submitted by Jerry Bryan on Thu, 04/22/2010 - 22:03.

My recent posting on |EndsWith| values for the corners of the 3x3x3 in the quarter turn metric was really secondary to another project I was working on.  Namely, I was working on determining all the syllables for the corners of the 3x3x3 in the quarter turn metric.  I discovered many more syllables than I was expecting.  As a part of determining why there were so many syllables, I discovered that the |EndsWith| values were much higher than I was expecting.  To a certain extent, one can think of the higher |EndsWith| values as being the "cause" of there being a larger number of syllables than expected.

As Tom Rokicki has pointed out, my expectations were incorrect about |EndsWith|.  Tom presented a very simple and elegant argument to explain why the average |EndsWith| value in the quarter turn metric was 6.  Tom's argument was for the whole cube, not just for the corners.  But the exact same argument applies equally well to either case.

Without further ado, here are my syllable results for the corners of the 3x3x3 in the quarter turn metric.  The results will be followed by some narrative about how the results were obtained and what they mean. 

 Corners, Quarter Turn Metric

Distance     All    Syllables
         Positions   

 0             1           0
 1            12          12
 2           114          18
 3           924         156
 4          6539        1643
 5         39528       15432
 6        199926      107862
 7        806136      631272
 8       2761740     2715084
 9       8656152     8656152
10      22334112    22334112
11      32420448    32420448
12      18780864    18780864
13       2166720     2166720
14          6624        6624

It is interesting to compare and contrast some of the numbers for the corners to the numbers for the whole cube. 

              Corners                        Whole Cube

Distance     All                         All     
         Positions   Syllables       Positions   Syllables

 0             1           0               1         0
 1            12          12              12        12
 2           114          18             114        18
 3           924         156            1068        12
 .             .           .               .         .

The numbers for the corners deviate from the numbers for the whole cube at a distance of 3q from Start and above.  At 3q from Start, the corners have more syllables and less positions than the whole cube.  We may interpret syllables roughly speaking as positions where different move sequences produce duplicate positions.  There are sequences of 3 quarter turns that produce the same position for the corners and a different position for the edges.  In the whole cube, such sequences produce different positions, and in the corners such sequences produce duplicate positions.  Therefore, at a given distance from Start the corners will tend to have fewer positions and more syllables than will the whole cube.

The first algorithm I used to calculate all the syllables for the corners operated as follows:

  1. Calculate and store the distance from Start and the EndsWith value for every corner position x.  The EndsWith value is a list of the quarter turns with which a minimal maneuver for a position can end.  The EndsWith value is therefore stored as a bit string of 12 bits, one bit per quarter turn.  |EndsWith| can easily be calculated as the number of bits in the string that are turned on.  This process requires about 10 to 15 minutes, depending on the speed of the machine I'm using.  The time can be reduced well under a minute by taking symmetry and anti-symmetry into account, but the current version of this particular program does not do that yet.
  2. If |x|=0, then x is not a syllable.  This is the Start position.
  3. If |x|=1, then x is a syllable.  These positions are the 12 quarter turns.
  4. If |x|≥2, perform a depth first search from x back to Start.  The EndsWith values provide a perfect set of breadcrumbs to follow to return unerringly back to Start.  For example, if EndsWith(x)={F,B',U}, then the moves F', B, and U' move one node closer to Start in the Cayley graph of cube space.  We call sets such as {F',B,U'} etc. the inverse of EndsWith, denoted as EndsWith'(x).
  5. Let n = |x| and let Px(k) be the number of positions that are exactly k moves from Start and exactly n-k moves from x.  It is known a priori that Px(0)=1 and Px(n)=1.
  6. As the breadth first search progresses from x back to Start, calculate in turn Px(n-1), Px(n-2), etc. through Px(1).  If for any Px(k) for 0<k<n we have Px(k)=1, stop the search and report that x is not a syllable.  Otherwise, x is a syllable.  Another way to say they same thing is that if Px(k)≥2 for 0<k<n, then x is a syllable.  Because the search is being done in a breadth first fashion, the condition Px(k)=1 can be used the first time it occurs to terminate the search early and declare x not to be a syllable.

The first time I ran algorithm #1, it produced correct answers but it ran about 45 hours.  I was expecting it to run no more than an hour or so.  So why did the full algorithm to determine all the syllables and non-syllables for the corners take so long?

The answer turns out to be that the average |EndsWith| values are much higher than I expected, and positions with large |EndsWith| values tend to be syllables.  I was conditioned to think in terms of small |EndsWith| values and a preponderance of non-syllables because of my experience with the whole group.  Indeed, Tom has shown that the average |EndsWith| value for the whole cube in the quarter turn metric is only about 1.3 all the way out to 15q from Start.  And Tom's elegant little proof about a larger average for the whole group never occurred to me.  With the higher than expected values for |EndsWith|, the solution graphs for some of the worst case positions included close to a half million positions.  I therefore came up with Algorithm #2.

  1. As before, enumerate the entire corners group, storing the distance from Start and the EndsWith value for each position.
  2. For each position x, determine one minimal path from x back to Start.  Given that all the EndsWith values are available, this is a trivial and almost instantaneous process.
  3. For each position x, perform a depth first search from x back to Start, looking for a minimal path from x to Start that is disjoint from the one already found.  If such a second path can be found, the position x is a syllable; otherwise, it is not a syllable.

Algorithm #2 is extremely fast.  Applying it to every position x in the corners group takes about 20 or 30 minutes, depending on the speed of the machine on which I'm working.  This is vastly superior to algorithm #1 which might take about 45 hours for the same problem.  However, Algorithm #2 is not correct.  On rare occasions, it identifies a position not to be a syllable when in fact the position is a syllable.

The following graph is not intended to be a Cayley graph, and it does not correspond to any particular position in cube space.  But it does exemplify the problem with algorithm #3. 

      b---d
    /  \ / \
   a    \    f
     \ / \ /
      c   e

Think of node a as being Start, nodes b and c as being 1 move from Start, nodes d and e as being 2 moves from Start, and node f as being position x which is 3 moves from Start.  Suppose step #2 of algorithm #2 finds the path f-d-b-a from x back to Start.  Then, there is no other path from x back to Start that doesn't go through either node d or node b.  But x is clearly a syllable because there are two positions, b and c, that are 1 move from Start, and there are two positions, d and e, that are 2 moves from Start.  Indeed, paths f-d-c-a and f-e-b-a are disjoint with respect to their intermediate nodes between f and a.  But such a graph structure causes algorithm #2 to fail if the first path back to Start that is found is f-d-b-a.

So I came up with algorithm #3.

  1. As before, enumerate the entire corners group, storing the distance from Start and the EndsWith value for each position.
  2. For each position x, perform a depth first search from x back to Start.  The depth first search from x back to Start will quickly and unerringly find a minimal path from x to Start, just as does algorithm #2.  The intermediate nodes between x and Start in this path will be stored for reference, just like in algorithm #2.  But unlike algorithm #2, the nodes in first path that is found do not serve as cutoff points for additional searching.
  3. Each new node found in the depth first search is compared to the first node found at the same depth in depth first search.  If a new node is found that is distinct from the first node that was found at that depth, we know that Px(k)≥2 for depth k.  The depth first search is proceeding from k=n-1 back to k=1.  When it has been determined that Px(1)≥2, bound the search from k=n-1 back to k=2.  When it has been determined that Px(1)≥2 and Px(2)≥2, bound the search from k=n-1 back to k=3.  Etc. If Px(k)≥2 for 0<k<n, then x is a syllable.  Otherwise, k is not a syllable.

Algorithm #3 produces the same results as algorithm #1.  Algorithm #3 is much faster than algorithm #1, but it is still much slower than algorithm #2.  We observe that algorithm #2 will occasionally produce false negatives, declaring a position not to be a syllable even when it really is.  But algorithm #2 will never produce a false positive.  If algorithm #2 says a position x is a syllable, then position x is a syllable.  This leads to algorithm #4, which is the one I finally settled on.

  1. As before, enumerate the entire corners group, storing the distance from Start and the EndsWith value for each position.
  2. For each position x, test x with algorithm #2.  If algorithm #2 says x is a syllable, then x is a syllable. This step handles the vast majority of cases.
  3. Otherwise, test x with algorithm #3. 

So the bottom line is an algorithm that is quite fast and that produces correct results.  On the average, it takes about 4 times as long to test whether each position is a syllable or not as it does to enumerate the entirety of cube space in the first place.

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

Comment viewing options

Select your preferred way to display the comments and click 'Save settings' to activate your changes.

Errata and Addenda

Submitted by Jerry Bryan on Fri, 04/23/2010 - 07:17.
The sentence that says "But it does exemplify the problem with algorithm #3." should say "But it does exemplify the problem with algorithm #2."

I got a little sloppy with including all the steps for algorithms #2, #3, and #4. For all of them, we include the steps that if |x|=0 then x is not a syllable and if |x|=1 then x is a syllable.

For all the algorithms, the actual computer code includes testing for the case of |EndsWith(x)|=1. If so, then x is not a syllable. Failing to include this test would not make the algorithms incorrect. But including this test makes the algorithms a little faster.

If I had StartsWith(x) available, then |StartsWith(x)|=1 is also sufficient to show that x is not a syllable. This would make the algorithm a little faster, but I didn't have have StartsWith(x) available in this particular program. Another approach for StartsWith would be to test the size of EndsWith(x-1), which is the same size as the size of StartsWith(x). But I didn't include this little bit of optimization in this particular program.
» login or register to post comments

Updated response

Submitted by secondmouse on Fri, 04/23/2010 - 08:42.
My first reaction to this is that you are making the problem 24 times bigger than it really should be. If the edges are not in consideration why not re-formulate in terms of the seven corners of the 2x2x2 keeping one corner fixed?

It may very well be that I've missed the point though.

It would be nice if a basic definiton of "syllable", |StartsWith| & |EndsWith| could be provided with an example.
» login or register to post comments

Your Question about Syllables

Submitted by Jerry Bryan on Sat, 04/24/2010 - 11:08.

The concept of syllables was introduced many, many years ago by Dan Hoey.  Under Dan's original formulation of the concept, a syllable was a position that could be effected by a sequence of moves all of which were from the same or opposite faces.  For example, the positions effected by the maneuvers FB' and FF are syllables, but the position effected by the maneuver FD is not.  Under this definition, a syllable may be of length 1, 2, 3, or 4 in the quarter turn metric, and a syllable may be of length 1 or 2 in the face turn metric.  The terms parallel moves and orthogonal moves are sometimes used to describe moves which are from the same or opposite faces and those which are not, respectively.  For example, F, F', B, and B' are mutually parallel.  But F is orthogonal to each of U, U', D, D', R, R', L, and L'.

Dan used the syllable concept as a part of a formula that provides an upper bound on the number of positions that are n moves from Start.  Call this upper bound P[n].  Dan's formula for P[n] does not in general provide the exact number of positions that are n moves from Start, but it does provide a fairly tight upper bound for quite a large distance from Start.

Enumerations of cube space are typically accomplished with a breadth first search, proceeding from those positions that are n-1 moves from Start to those positions that are n moves from Start, basically moving 1 move at a time.  Dan's formula is based on an enumeration by syllables rather than upon an enumeration by quarter turns or face turns.  For example, positions that are 3 moves from Start would normally be reached from positions that are 2 moves from Start.  Dan's formula reaches positions that are 3 moves from Start by combining positions that are k moves from Start with syllables that of length 3-k for 0≤k≤2.  So the formula for P[3] has terms that are based on combining positions of length 2 with syllables of length 1, combining positions of length 1 with syllables of length 2, and combining positions of length 0 with syllables of length 3.  So positions of length 3 are not reached just from positions of length 2.  Positions of length 3 are reached from positions of length 2 in some cases, they are reached from positions of length 1 in some cases, and they are reached from positions of length 0 in some cases.

A Cayley graph for cube space has a node for each position, and the nodes are connected by arcs that are usually called edges.  The arcs connect nodes that are 1 move apart.  Each node is connected to 12 other nodes in the quarter turn metric, and to 18 other nodes in the face turn metric.

Here's a little whimsical imagery to describe how syllables fit in with a Cayley graph.  Imagine that the nodes are bird nests, and that each bird nest is a 1 hour flight from 12 other bird nests in the quarter turn metric or a 1 hour flight from 18 other bird nests in the face turn metric.  Standard birds can only fly for 1 hour before having to stop to rest.  But we develop a set of super birds that can fly longer without resting.  Some of them can fly 2 hours, some of them can fly 3 hours, etc.  But even our super birds are able to fly longer than 1 hour at a time only for particular routes.  Namely, they are able to fly longer than 1 hour at a time only to nodes that can be reached by more than one route.  For example, our super birds can fly from Start to FF in one flight of 2 hours.  That is, there are two routes from Start to FF because FF and F'F' are different routes to the same nest.  But we don't think of our super bird flying from Start to F to FF or from Start to F' to F'F'.  Rather, we think of our super bird flying directly from Start to FF=F'F' as a new and direct route.

Our super birds do not get anywhere any faster than regular birds.  Even though the super birds might be able to make a multiple hour trip in one flight, a regular bird could make the same trip in the same number of hours.  It's just that the regular birds would have to make multiple flights.  But even our super birds still have to make two separate 1 hour flights to go from Start to FD because there is only one route from Start to FD.

Here are some numbers close to Start from Dan's formula for the whole cube in the quarter turn metric. 

Distance    Length    Length      Number of
 from        of         of         resulting  Total
 Start      position  syllable     positions

 0           0          N/A           1               this is Start itself
                                                 1

 1           0            1          12               syllables.  these are the quarter turns
                                                12

 2           1            1          96               non-syllables
             0            2          18               syllables
                                               114

 3           2            1         912               non-syllables
             1            2         144               non-syllables
             0            3          12               syllables
                                              1068

My discussions about syllables on this forum have been an attempt to generalize syllables beyond the original concept of parallel and orthogonal moves.  The original syllables had more than one path through the Cayley graph that reached the same location.  The multiple routes were attributed either to the fact that certain moves commute (e.g., FB'=B'F) or to the fact that certain sequences of moves are halfway through a non-trivial identity (e.g., FFFF=I, so that FF=F'F').  My generalization is simply to focus on positions that can be reached with multiple paths, irrespective of the underlying cause of why there are multiple paths.

We are very careful how we define multiple paths.  For example, FF=F'F' and DFF=DF'F'.  FF=F'F' is a syllable.  But once FF=F'F' has been identified as a syllable, not only can our super birds fly from Start to FF=F'F' as a single 2 hour flight, they are required to fly from Start to FF=F'F' as single 2 hour flight.  They are no longer allowed to fly from Start to FF or from Start to F'F' as two 1 hour flights.  So there is only one path from Start to DFF=DF'F', namely (D)(FF), and DFF=DF'F' is not a syllable.

» login or register to post comments

StartsWith and EndsWith Definitions and Examples

Submitted by Jerry Bryan on Fri, 04/23/2010 - 20:59.
StartsWith and EndsWith are attributes of positions (or of permutations, if you prefer). They are not attributes of a maneuver. StartsWith(x) is the set of all possible first moves in the set of all minimal maneuvers for x. EndsWith(x) is the set of all possible last moves in the set of all minimal maneuvers for x. Examples: 
    position x effected       StartsWith(x)    EndsWith(x)
      by maneuver

       FD                     {F}              {D}
       FB'                    {F,B'}           {F,B'}
       FF                     {F,F'}           {F,F'}
       DFF                    {D}              {F,F'}
       FFD                    {F,F'}           {D}
       DFB'                   {D}              {F,B'}
       FB'D                   {F,B'}           {D}
       FFB'                   {F,F',B'}        {F,F',B'}
|StartsWith(x)| and |EndsWith(x)| are the sizes of StartsWith(x) and EndsWith(x), respectively.
» login or register to post comments

Size of the Corners Problem

Submitted by Jerry Bryan on Fri, 04/23/2010 - 20:45.
With respect to the corners, there are two distinct groups, one of which is 24 times bigger than the other. The two groups are closely related, but they do not represent the same problem. The corners of the 3x3x3 are the larger problem, and the 2x2x2 is the smaller problem. Fixing one of the corners of the 3x3x3 is one of the standard ways to model the 2x2x2.

To see the difference, consider the corners of the 3x3x3 and the 2x2x2 both to be in the Start position, and consider the effects of performing the maneuver RL'. In the corners of the 3x3x3, the maneuver RL' produces a position that is 2 moves from Start. In the 2x2x2, the maneuver RL' produces the Start position itself.
» login or register to post comments

Thanks for this and the other comments

Submitted by secondmouse on Sat, 04/24/2010 - 15:10.
This makes it clearer. I was just curious as had not heard of these before. I think I would need to study Cayley graphs quite a bit more though before I could weigh in with anything like a decent contribution.
» login or register to post comments