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

What are the known bounds for the diameter of this subgroup? This thread gives a lower bound of 26 QTM but doesn't discuss HTM. I seem to recall a lower bound of 20 HTM from somewhere, but no upper bound. However, I recently found a position that requires 21 HTM:
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      2
and in QTM:
Depth   Positions
0       1
12      30
14      282
16      1161
18      4989
20      24778
22      94018
24      61353
26      12
I'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      28808
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

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

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.
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

Sequential coset iteration
Face Turn Metric
Enumeration to depth: 28

Snapshot: Monday, September 17, 2018 at 10:43:17 AM Central Daylight Time

 Depth             Reduced             Elements
   0                     1                    1 
   1                     0                    0 
   2                     0                    0 
   3                     1                    6 
   4                     2                   12 
   5                     5                   30 
   6                     5                   42 
   7                    65                  516 
   8                   244                2,133 
   9                 1,023                8,979 
  10                 5,342               47,018 
  11                25,218              237,891 
  12               127,241            1,238,979 
  13               667,924            6,709,751 
  14             3,580,490           36,848,651 
  15            19,449,118          203,943,687 
  16           103,775,192        1,106,234,376 
  17           497,171,517        5,384,315,460 
  18         1,557,710,189       17,135,129,310 
  19         1,291,751,720       14,308,751,802 
  20            45,579,769          494,412,239 
  21                   214                1,437 
  22                     0                    0 
 Sum         3,519,845,280       38,677,882,320 

21,054 of 92,897,280 cosets solved

Here is a partial listing of the results with the symmetry of the position. C1 is 
the group having only the identity element. Cs has one mirror plane and + indicates

  50 R U' F' R2 U R2 F2 R U2 R' U R2 F2 U2 R F' U2 F R2 F2 R      Cs+
  51 R U R2 F R2 U R U R' U2 R2 U2 R' F U' R' U2 F2 U2 R F2       C1+
  52 R U R F2 U2 F U2 R' U R F2 R' U2 R2 F' R' U F2 U F' R2         C1+
  53 R U R2 F' R U2 R F' U2 R U' R2 F U2 F2 R2 U' F2 R' F2 R2     C1+
  54 R U R2 U F2 R U' F2 R2 F U R2 F R' U2 R2 U2 F2 R U2 R       C1+
  55 R U R F' R' F U2 R U F2 U2 F2 R' U' F' R' F' R' F' U2 R'            C1+
  56 R U' F2 U2 F' U F2 R2 U2 F2 U R U' F R' U2 F R2 U2 R' U2     C1+
  57 R U R' F R' U F R' U F' U R U F2 U R' U F' U2 R U'                   C1+
  58 R U R U R F' R' F2 U' F U' F U' F R2 F2 U F' R2 F2 U'              C1+
  59 R U R' U2 F2 U F' U2 R F2 U F U2 R F' U F' R' U R2 U'            C1

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

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*

Thanks for the work! That's a great job. I think 10M is a good estimate; there probably isn't too many more than that otherwise our solves of millions of random positions would have likely found at least one 21f* and they did not. I think I optimally solved about 8M positions.

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

You've done so much great work; I am honored that I am even part of this discussion.

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

So, I'd have to do a rewrite of my search engine to use a subgroup such as |R2 F2 U|. Figure out indexing schemes, move tables, pruning tables and all that. Offhand I wouldn't know how to characterize the cosets. And this before I could begin to figure out how to apply the pre-pass algorithm. It sounds like more work than I'm up to right now.


I get it. I'm trying to figure out (among other things) how to generalize this so a ksolve-like program can do somewhat arbitrary cosets. Maybe this is worth a topic on the board so folks can contribute. The code I have so far is twsearch on github, but it's still just experimental and it doesn't even think about cosets yet.

RUF three face group

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


I haven't explored this subgroup yet; nice result to find a 21*! My program confirms the distance:
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
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

I've found over 556,000 more distance-21 positions in UFR. I've checked all of the neighbors of these and have not yet found any distance-22 positions. I would be surprised if any distance-22 positions exist. Similarly, in the quarter-turn metric, I've found 381 total distance-26 positions in UFR, and checked their neighbors without finding any distance-27 positions. Likely the diameter is 26. Here are some distance counts in the half-turn metric.
 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 3871961673
In 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

Nice! But how did you find so many so quickly?? :o

With twsearch

So twsearch is supposed to be a ksolve replacement.

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!

BTW How can you be sure it does not require any less moves to attain in both the QTM and HTM? Have you your own solver?
I note this is a position with the UFR corner and all its adjacent edges (UF, UR, FR) in the solved state.