# Lower bound for the diameter of the 3-gen subgroup <U,F,R>

U R F2 R U2 F2 U' F' R U F U R' F R2 U F R U2 R F'Is this the first one known? Out of all 186624 positions with all pieces correctly permuted, this position and the inverse are the only ones requiring 21. Here's the full distribution:

Depth Positions 0 1 9 18 10 36 11 36 12 186 13 246 14 894 15 1737 16 7568 17 22001 18 60874 19 77513 20 15512 21 2and in QTM:

Depth Positions 0 1 12 30 14 282 16 1161 18 4989 20 24778 22 94018 24 61353 26 12I've also solved over 1 million random positions in each metric. HTM:

Depth Positions 10 2 11 6 12 34 13 191 14 1074 15 6343 16 36802 17 193742 18 683378 19 651748 20 28808QTM:

Depth Positions 13 2 14 5 15 44 16 201 17 884 18 3829 19 16465 20 65208 21 212644 22 413583 23 343939 24 89054 25 1124(keywords for easier searching: three-face subgroup, 170659735142400)

## Comment viewing options

### A better data set

I performed another 12 hr. overnight run, this time solving the cosets in random order. I found 243 depth 21 C3v+ symmetry equivalence classes representing 2,826 group elements. None of these has any geometric symmetry. Eleven show anti-symmetry of which one is self-inverse. The high proportion of anti-symmetric elements found in the first run would be an artifact of solving the cosets in sequential order. All of the cosets solved in the first run have similar edge cubie configurations.

Since the cosets were sampled randomly the distribution shown below is more confidently indicative of the distribution of the whole group. Thus, for the whole group:

2,826 * 92,897,280 / 23,994 = ~10,941,390 depth 21 elements in the whole group.

Three Face Coset Solver Fixed cubies in subgroup: UF, UR, UB, UL, DF, DR, FR, FL, BR. 92,897,280 cosets of size 1,837,080 iMac Cosets solved since launch: 769 Average time per coset: 0:05:31.829 Mac Pro Cosets solved since launch: 1,241 Average time per coset: 0:05:42.899 Three Face Group Enumerator Random coset iteration Face Turn Metric Enumeration to depth: 28 Snapshot: Tuesday, September 18, 2018 at 7:02:05 AM Central Daylight Time Depth Reduced Elements 0 0 0 1 0 0 2 0 0 3 0 0 4 1 12 5 0 0 6 2 24 7 8 96 8 48 570 9 312 3,696 10 1,939 23,010 11 11,813 140,382 12 70,757 841,896 13 423,805 5,047,152 14 2,522,209 30,056,166 15 14,922,591 177,914,298 16 86,233,462 1,028,548,512 17 451,244,982 5,384,221,344 18 1,581,688,624 18,881,436,612 19 1,492,068,411 17,815,246,752 20 63,341,593 755,414,172 21 243 2,826 22 0 0 Sum 3,692,530,800 44,078,897,520 23,994 of 92,897,280 cosets solved

### Coset solvers *rule*

I highly doubt there's a 22f*; I searched all positions with nontrivial symmetry as well as a bunch of deep cosets. If there was a 22f* it would (based on other searches) likely have found one in that search. Plus, I think I've found a fair fraction of the 21f*'s (500K of 10M) and checked all their neighbors; if there was a 22f*, it has nine neighbors that are at least 21f* (and if the 22f* is not symmetrical then the 9 neighbors are distinct).

Can you modify your coset solver to work with a subgroup that has moves, like U,R so that we can use the prepass trick so we don't have to do search that deep, and this way we can get the time per coset way down and finish off this puzzle?

### RUF 26f Positions

Thanks, from you that is high praise.

It's a big group: 1.7 x 10^14. If there are just a few depth 22f positions one would have to effectively search half of that space to have an even chance of finding one. I think the possibility of depth 22 positions is still very much in play.

I don't know what you mean by "the prepass trick". Could you explain more fully what you are refering to?

For a search for 22f positions rather than a full enumeration of the group I could mark off nearest neighbor cosets of cosets of max depth < 21 and give priority to nearest neighbors of cosets at max depth 21. I already have a move table for the coset index so it would be simple to do. I'm not sure that would improve the odds enough though.

### You've done so much great wor

So the prepass trick is fairly simple; the SIAM paper on "The Diameter of the Rubik's Cube Group..." covers it. The idea is, if your subgroup contains actual moves, then rather than search all canonical sequences to the maximum depth (this is what iterated depth-first search does), you instead search all canonical sequences to a smaller depth (perhaps two less than the maximum, or three less), and then just take that bitmap of seen positions and extend it by the moves in the subgroup some number of times. If there are remaining positions, you enumerate them and solve them by some other means (usually there are very few). It's like a combination of iterated depth-first search (for the higher parts of the tree) and breadth-first search (for the last few levels). You don't get exact position counts, but it does let you prove an entire coset to be <= 21f* (or find the elusive 22f*'s) much more quickly.

As a further optimization, once you have the prepass working (and you can use bit tricks to make it very fast if you lay your bitmap out carefully), you can use the prepass for the IDFS searches and just ensure the last move in your searching always is *not* in the subgroup, since prepass takes care of those. This further reduces the work the search has to do (somewhat significantly).

If anything is not clear, please refer to the "20" paper, or ask questions and I'll do my best to answer them. You can also read the hcoset.pdf file for implementation details.

### Pre-pass trick

### Cosets

### RUF three face group

In this thread I reported taking the RUF group enumeration out to 20q: RUF Group Enumeration

### Nice!

abacus:twsearch rokicki$ ./twsearch --scramblealg "U R F2 R U2 F2 U' F' R U F U R' F R2 U F R U2 R F'" --moves U,F,R samples/3x3x3.tws This is twsearch 0.1 (C) 2018 Tomas Rokicki. - ./twsearch --scramblealg U R F2 R U2 F2 U' F' R U F U R' F R2 U F R U2 R F' --moves U,F,R samples/3x3x3.tws Created new moves F2 F' B2 B' D2 D' U2 U' L2 L' R2 R' State size is about 8.6504 x 10^19 log2 66.2294 Found 4 canonical move states. Reading tws-3x3x3-8G-o1ha8o2.dat read in 19.85667085647583 Solving Depth 12 Depth 13 Depth 14 Depth 15 Depth 16 Depth 17 Depth 18 Depth 19 Depth 20 Depth 21 F U F R' U2 F' R U2 F R' F2 R2 U' F' U' F2 R U' F2 R U2 Found 1 solution at maximum depth 21 lookups 24187531 in 1.739003896713257 rate 13908842.32388139

### Lots more 21*f's

0 1 1 1 9 10 2 54 64 3 324 388 4 1944 2332 5 11664 13996 6 69969 83965 7 419526 503491 8 2514261 3017752 9 15058551 18076303 10 90138505 108214808 11 539293253 647508061 12 3224453612 3871961673In the quarter-turn metric we see:

0 1 1 1 6 7 2 27 34 3 120 154 4 534 688 5 2376 3064 6 10560 13624 7 46920 60544 8 208296 268840 9 923586 1192426 10 4091739 5284165 11 18115506 23399671 12 80156049 103555720 13 354422371 457978091 14 1565753405 2023731496 15 6908670589 8932402085

### Nice! But how did you find so

### With twsearch

It's got a lot of stuff built-in. So for instance an optimal solver for URF is just

./twsearch --moves U,R,F -s samples/3x3x3.def

and that's reasonably efficient. You can also use it as a crude coset solver. For instance, given a position that's pretty deep with respect to edges, you can do something like

./twsearch --moves U,R,F --nocorners --scramblealg "some deep position" -c 1000000000000000000 samples/3x3x3.def

and this will generate all the canonical solutions to that deep position, which you can then run through

./twsearch -u samples/3x3x3.def

which will print only the unique ones. If you filter this stream by only including the long solutions (say with awk 'NF>20') you'll get deep positions.

And various other random tricks like that. I wrote a quick and dirty program to find all deep URF symmetrical coset representatives (ignoring corners) and ran those cosets using the tricks above, and it pretty easily finds a ton of deep positions.

### Well done if correct!

I note this is a position with the UFR corner and all its adjacent edges (UF, UR, FR) in the solved state.

## RUF three face group coset solver

I modified my old RUF group coset solver for the ftm. My full enumeration out to depth 12 duplicates the results Tom Rokicki reported earlier. A 12 hr full enumeration run found 214 depth 21f C3v+ symmetry equivalence classes representing 1,437 depth 21f positions.

The cosets were not chosen randomly so the distribution shown below may possibly be skewed by how I index the cosets. However, I would not expect it to be too far off. In any event, extrapolation of my results would afford several million depth 21f elements in the full group. It would not surprise me if there were a hand full of depth 22f positions out there.

Only one of the 214 depth 21f positions has any geometric symmetry, a mirror plane. It is interesting that of the 214 positions 131 are anti-symmetric, of which only 20 are self-inverse. How this relates to being a deep position I couldn't guess.