
cube files
Indexed Cube Lovers Archive
![]() |
cube archivesGAP filesBlogs
Forum topicsActive forum topics:New forum topics:User loginNavigation |
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:
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.
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.
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.
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. |
Browse archives
Pollwww.olympicube.com need cube lovers opinion on which cube to produce first olympic cube 6a 83% olympic cube 6b 17% Total votes: 23 Syndicate |