All the Syllables, Corners Group, Quarter Turn Metric
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:
- 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.
- If |x|=0, then x is not a syllable. This is the Start position.
- If |x|=1, then x is a syllable. These positions are the 12 quarter turns.
- 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).
- Let n = |x| and let P_{x}(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 P_{x}(0)=1 and P_{x}(n)=1.
- As the breadth first search progresses from x back to Start, calculate in turn P_{x}(n-1), P_{x}(n-2), etc. through P_{x}(1). If for any P_{x}(k) for 0<k<n we have P_{x}(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 P_{x}(k)≥2 for 0<k<n, then x is a syllable. Because the search is being done in a breadth first fashion, the condition P_{x}(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.
- As before, enumerate the entire corners group, storing the distance from Start and the EndsWith value for each position.
- 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.
- 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.
- As before, enumerate the entire corners group, storing the distance from Start and the EndsWith value for each position.
- 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.
- 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 P_{x}(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 P_{x}(1)≥2, bound the search from k=n-1 back to k=2. When it has been determined that P_{x}(1)≥2 and P_{x}(2)≥2, bound the search from k=n-1 back to k=3. Etc. If P_{x}(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.
- As before, enumerate the entire corners group, storing the distance from Start and the EndsWith value for each position.
- 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.
- 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.