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

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
	

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?

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

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.

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 many so quickly?? :o

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.