Subgroups using basic moves

Here are some results for the RUL group:

C2v Three Face Coset Solver

Fixed cubies in subgroup: UFR, URB, UBL, ULF, DRF, DFL, DLB, DBR.
88,179,840 cosets of size 1,814,400

Cosets solved since launch: 6,556,900
Average time per coset: 0:00:00.04

Server Status:
Three Face Group Enumerator
Sequential coset iteration
Enumeration to depth: 20

Snapshot: Saturday, March 30, 2013 11:58:29 PM Central Daylight Time

 Depth             Reduced             Elements
   0                     1                    1 
   1                     2                    6 
   2                     6                   23 
   3                    15                   84 
   4                    47                  309 
   5                   157                1,136 
   6                   553                4,176 
   7                 2,004               15,320 
   8                 7,164               56,151 
   9                26,186              205,718 
  10                95,723              752,757 
  11               348,280            2,752,128 
  12             1,268,906           10,054,045 
  13             4,626,932           36,694,844 
  14            16,836,915          133,783,778 
  15            61,270,626          487,123,350 
  16           222,547,992        1,770,760,044 
  17           806,803,068        6,421,483,102 
  18         2,913,309,411       23,196,794,401 
  19        10,451,224,250       83,234,279,556 
  20        37,036,491,243      295,020,643,126 

 Sum        51,514,859,481      410,315,404,055  

88,179,840 of 88,179,840 cosets solved

Here is the distribution found from full enumeration of a set of randomly chosen cosets:

Cosets solved since launch: 212
Average time per coset: 0:09:51.881

Server Status:
Three Face Group Enumerator
Random coset iteration
Enumeration to depth: 32

Snapshot: Sunday, March 31, 2013 8:56:36 AM Central Daylight Time

 Depth             Reduced             Elements
   0                     0                    0 
   1                     0                    0 
   2                     0                    0 
   3                     0                    0 
   4                     0                    0 
   5                     0                    0 
   6                     0                    0 
   7                     0                    0 
   8                     0                    0 
   9                     0                    0 
  10                     0                    0 
  11                    13                  104 
  12                    44                  352 
  13                   115                  920 
  14                   324                2,544 
  15                 1,434               11,464 
  16                 3,808               30,240 
  17                18,168              145,084 
  18                49,422              392,460 
  19               230,823            1,841,244 
  20               623,353            4,955,572 
  21             2,803,618           22,351,544 
  22             7,135,684           56,743,580 
  23            28,632,246          228,133,512 
  24            57,626,384          458,461,788 
  25           135,218,972        1,076,955,896 
  26           100,494,372          799,807,100 
  27            49,002,819          390,568,308 
  28             2,805,809           22,262,364 
  29                 5,392               43,124 

 Sum           384,652,800        3,062,707,200 

1,688 of 88,179,840 cosets solved

Although the C_2v three face group is smaller than the C_3v group, the C_2v three face diameter is deeper than the C_3v three face diameter. This follows from turns of opposite faces commuting, e.g. R L = L R. The branching factor for C_2v group is lower than for the C_3v group: ~3.7 as opposed to ~4.4.

I am surprised that you found positions at 29q! I was under the impression that your coset solver is using _all_ moves to find the depths of positions in the RUL group.

If this is true, how difficult is it to modify your coset solver so that it uses all moves to find the optimal depths of RUL positions?

It seems also that you have a pretty fast solver with this average time:

0:00:00.04

and that out of the 88,179,840 you have already solved 6,556,900!

If you are willing to share your coset solver I can help finish the remaining cosets... [mdlazreg gmail com]

And congratulations on the 29q positions! as far as I know this is largest known subgroup with such deep diameter! as you know the upper bound for the whole cube is 29q.

One interesting thing to do probably is to take the 5392 positions at 29q and run them against an optimal solver. You might hit a winner.

I have found a depth 30q RUL group element:

R2 U R U' R2 L U2 L U' R' L U' L U2 R2 L U' R U R U' R' L U' R'

This is an unusual case having all cubies in the identity state except that all the corners are twisted. I found it because I index the corner positions as 2,187 * position_index + twist_index. This state is a member of one of the first 2,187 cosets when solved sequentially.

Extrapolating from the distribution I find from solving random cosets I would guess that the depth 30 positions number in the thousands. The diameter is either 30 or 31. Certainly not 32.

The solutions are optimal in the RUL q-turn metric, i.e. using only turns of those three faces. The solver iterates through a symmetry reduced list of the corner positions. Each of these positions defines a coset. The solver performs an iterative deepening search for solutions to the defining corner position assisted by a pruning table which lists the depths of all 88,179,840 corner positions.

Initializing the pruning table

Depth     Count
 0            1
 1            6
 2           23
 3           84
 4          309
 5         1116
 6         3962
 7        13904
 8        48309
 9       164442
10       544027
11      1730474
12      5148192
13     13451572
14     26220053
15     27777772
16     12123803
17       950546
18         1241
19            4
20            0
Found     88179840 of     88179840

As you can see the pruning table's effective depth is 14-16 turns. This means that once the search tree is expanded to within 14-16 turns of the target depth the pruning table effectively directs the solver to a solution avoiding any dead ends. Any solution to the defining corner position is a solution to the coset member having the edge position found by applying the inverse turn sequence to the identity edge position. So the solver searches ever deeper for solutions to the defining corner position. Each time a solution is found it checks that coset member against a list of previously solved coset members. If the coset member has not yet been solved the solution is an optimal solution to this coset member. The solver continues until it has found optimal solutions to all 1,814,400 coset members or until it hits a depth limit.

So the solver does not have to look through all combinations of 29 turns to find a length 29 solution. The use of a pruning table vastly reduces the number of nodes in the search tree.

0.04 sec is the average time to find the depth 20 and under members of a coset. Since the solver is threaded and was working on eight cosets in parallel for most of the run the effective time is one eighth of that. 6,556,900 is the number of cosets solved to depth 20 by that instance of the solver. The remainder of the 11 million+ symmetry reduced cosets were solved by a second computer running concurrently.

The time needed to find optimal solutions for all 1.8 million members of a coset is 9 min 51 sec. Depth 29 RUL positions are not that rare. I left the solver running all day. It has now solved 529 cosets and found 12,191 (symmetry reduced) depth 29 positions. So pick an odd turn parity coset and on average it will have 46 depth 29 elements. I'm hoping a depth 30 position will show up. My back of the envelope calculations would put the ratio of depth 29 to depth 30 positions at something on the order of ten to the fifth. If I have the patience to let the thing run for a week or so I figure I might have an even chance of finding one.

The application is written for MacOS running Lion or higher with 4GB of memory. If you have a Mac I could send you the apps or if you have XCode 4.6 I could send you the source.

Thank you for your willingness to share your code but unfortunately I do not have a Mac or XCode. If your code can be ported to UNIX I can help in solving the remaining cosets.

The RUL subgroup has 270336 cosets in the whole group. 270336 = 11*12*2^11.
Each coset can be defined by picking up two edges cubies and a specific orientations of all the edges.

Do we know the depth distribution of this subgroup that has 270336 elements?

Once this RUL subgroup is completed, I will be very much interested in the depth distribution of its coset that contains the known 26q*...

No I don't know the depth distribution for taking cosets of the RUL group to the RUL group. Although I could probably knock out some code and do the calculation, I don't find this coset space of enough interest to make it worth the effort. The cosets are too large: 1.6 x 10¹³ elements. Solving the coset containing the 26q position would be a monumental task.

Kociemba, Rokicki , et al are the ones to look to for coset solvers in the full Rubik's cube group. I think they work mostly with cosets of the Kociemba subgroup: < U , D , R2 , F2 , L2 , B2 >. This neatly divides the group into 2,217,093,120 cosets of 19,508,428,800 elements. What I've done might best be described as plodding along in their footsteps from descriptions of their techniques I've gleaned from posts on this forum. They know a lot more about this stuff than I do.

True the cosets are too large, however they are fewer... they are only 270336 of them and here is their distribution [modulo bugs and cosmic rays]:

0            1
1            6
2           59
3          482
4         3232
5        18961
6        79719
7       137571
8        30241
9           64
--------------
        270336

If you manage to port your code to Linux in the future please let me know I am very interested in solving the coset containing the 26q position. Thanks again.

The constraining factor is the time. One big advantage of a coset solver approach is that by breaking up the group into cosets one only has to keep track of previously solved states for the elements of the current coset. In the present case that only requires 1.8MB per thread.

The time necessary to solve a coset increases geometrically with the depth. My solver takes on average about 0.9 cpu-sec to solve a coset to depth 20. To solve a coset completely takes about 4 cpu-minutes. My little three computer network solved the group to depth 20 in right at a week. To completely solve the group in a comparable time would require a network of several hundred personal computers.

The <R, U, F> group was just recently done to depth 20 by B MacKenzie. See a couple threads down. (I'm surprised he didn't mention that is in reply.)

I just ran my "RubikBandage" hash table-based program to compute the other distributions as far as it would go. See results below. Of course, these are incomplete distributions.

C:\Bruce>RubikBandage667.exe q b l r
Bandaging 0 corners to edges and 0 edges to centers.
Allowed turns: U U' D D' F F'
distance   1: count =         6, total         7
distance   2: count =        23, total        30
distance   3: count =        84, total       114
distance   4: count =       309, total       423
distance   5: count =      1136, total      1559
distance   6: count =      4176, total      5735
distance   7: count =     15320, total     21055
distance   8: count =     56151, total     77206
distance   9: count =    205718, total    282924
distance  10: count =    752757, total   1035681
distance  11: count =   2752128, total   3787809
distance  12: count =  10054045, total  13841854
distance  13: count =  36694844, total  50536698
distance  14: count = 133783778, total 184320476

C:\Bruce>RubikBandage667.exe q l r
Bandaging 0 corners to edges and 0 edges to centers.
Allowed turns: U U' D D' F F' B B'
distance   1: count =         8, total         9
distance   2: count =        44, total        53
distance   3: count =       232, total       285
distance   4: count =      1226, total      1511
distance   5: count =      6480, total      7991
distance   6: count =     34248, total     42239
distance   7: count =    180880, total    223119
distance   8: count =    953961, total   1177080
distance   9: count =   5025008, total   6202088
distance  10: count =  26450928, total  32653016
distance  11: count = 139161520, total 171814536

C:\Bruce>RubikBandage667.exe q l b
Bandaging 0 corners to edges and 0 edges to centers.
Allowed turns: U U' D D' R R' F F'
distance   1: count =         8, total         9
distance   2: count =        48, total        57
distance   3: count =       284, total       341
distance   4: count =      1683, total      2024
distance   5: count =      9972, total     11996
distance   6: count =     59008, total     71004
distance   7: count =    348604, total    419608
distance   8: count =   2057483, total   2477091
distance   9: count =  12132834, total  14609925
distance  10: count =  71500408, total  86110333
distance  11: count = 421156658, total 507266991

C:\Bruce>RubikBandage667.exe q l
Bandaging 0 corners to edges and 0 edges to centers.
Allowed turns: U U' D D' R R' F F' B B'
distance   1: count =        10, total        11
distance   2: count =        77, total        88
distance   3: count =       584, total       672
distance   4: count =      4434, total      5106
distance   5: count =     33664, total     38770
distance   6: count =    255320, total    294090
distance   7: count =   1933936, total   2228026
distance   8: count =  14635503, total  16863529
distance   9: count = 110685344, total 127548873

I increased the size of the hash table in my program by a few million entries so that I could get the <U,D,F> distribution one level deeper. This is equivalent to <R,U,L>, of course. Here are the results.

C:\Bruce>RubikBandage674.exe q b l r
Bandaging 0 corners to edges and 0 edges to centers.
Allowed turns: U U' D D' F F'
distance   1: count =         6, total         7
distance   2: count =        23, total        30
distance   3: count =        84, total       114
distance   4: count =       309, total       423
distance   5: count =      1136, total      1559
distance   6: count =      4176, total      5735
distance   7: count =     15320, total     21055
distance   8: count =     56151, total     77206
distance   9: count =    205718, total    282924
distance  10: count =    752757, total   1035681
distance  11: count =   2752128, total   3787809
distance  12: count =  10054045, total  13841854
distance  13: count =  36694844, total  50536698
distance  14: count = 133783778, total 184320476
distance  15: count = 487123350, total 671443826

I also ran the program for face turn metric for 5 of the subgroups.

C:\Bruce>RubikBandage667.exe d b l
Bandaging 0 corners to edges and 0 edges to centers.
Allowed turns: U U' U2 R R' R2 F F' F2
distance   1: count =         9, total        10
distance   2: count =        54, total        64
distance   3: count =       324, total       388
distance   4: count =      1944, total      2332
distance   5: count =     11664, total     13996
distance   6: count =     69969, total     83965
distance   7: count =    419526, total    503491
distance   8: count =   2514261, total   3017752
distance   9: count =  15058551, total  18076303
distance  10: count =  90138505, total 108214808
distance  11: count = 539293253, total 647508061

C:\Bruce>RubikBandage667.exe b l r
Bandaging 0 corners to edges and 0 edges to centers.
Allowed turns: U U' U2 D D' D2 F F' F2
distance   1: count =         9, total        10
distance   2: count =        45, total        55
distance   3: count =       216, total       271
distance   4: count =      1053, total      1324
distance   5: count =      5103, total      6427
distance   6: count =     24697, total     31124
distance   7: count =    118547, total    149671
distance   8: count =    569733, total    719404
distance   9: count =   2734114, total   3453518
distance  10: count =  13106238, total  16559756
distance  11: count =  62748283, total  79308039
distance  12: count = 300029177, total 379337216

C:\Bruce>RubikBandage667.exe l r
Bandaging 0 corners to edges and 0 edges to centers.
Allowed turns: U U' U2 D D' D2 F F' F2 B B' B2
distance   1: count =        12, total        13
distance   2: count =        90, total       103
distance   3: count =       648, total       751
distance   4: count =      4693, total      5444
distance   5: count =     33712, total     39156
distance   6: count =    239311, total    278467
distance   7: count =   1692056, total   1970523
distance   8: count =  11962195, total  13932718
distance   9: count =  84462310, total  98395028

C:\Bruce>RubikBandage667.exe l b
Bandaging 0 corners to edges and 0 edges to centers.
Allowed turns: U U' U2 D D' D2 R R' R2 F F' F2
distance   1: count =        12, total        13
distance   2: count =        99, total       112
distance   3: count =       810, total       922
distance   4: count =      6642, total      7564
distance   5: count =     54348, total     61912
distance   6: count =    443570, total    505482
distance   7: count =   3617336, total   4122818
distance   8: count =  29478708, total  33601526
distance   9: count = 240119958, total 273721484

C:\Bruce>RubikBandage667.exe l
Bandaging 0 corners to edges and 0 edges to centers.
Allowed turns: U U' U2 D D' D2 R R' R2 F F' F2 B B' B2
distance   1: count =        15, total        16
distance   2: count =       162, total       178
distance   3: count =      1728, total      1906
distance   4: count =     18463, total     20369
distance   5: count =    196642, total    217011
distance   6: count =   2087948, total   2304959
distance   7: count =  22152379, total  24457338
distance   8: count = 234857377, total 259314715