Subgroups using basic moves

In QTM, the whole cube is generated using U,D,R,L,F,B moves.
If we drop some moves we end up with some subgroups. The subgroups are:
1) I [the identity]
2) U
3) U,D
4) U,F
5) U,D,F
6) U,F,R
7) U,D,F,B
8) U,D,F,R
9) U,D,F,B,R

I know the depth table for subgroups 1) 2) 3) and 4):
The subgroup 1) generated by "no move", has the following obvious table:
Moves Deep       arrangements (q only)

0                    1
------
1
The subgroup 2) generated only by the move U, has the following table:
Moves Deep       arrangements (q only)

0                    1
1                    2
2                    1
------
4
The subgroup 3) generated by U,D has the following table:
Moves Deep       arrangements (q only)

0                    1
1                    4
2                    6
3                    4
4                    1
------
16
The subgroup 4) generated by U,F has the following table:
Moves Deep       arrangements (q only)

0                    1
1                    4
2                   10
3                   24
4                   58
5                  140
6                  338
7                  816
8                1,970
9                4,756
10               11,448
11               27,448
12               65,260
13              154,192
14              360,692
15              827,540
16            1,851,345
17            3,968,840
18            7,891,990
19           13,659,821
20           18,471,682
21           16,586,822
22            8,039,455
23            1,511,110
24               47,351
25                   87
----------
73,483,200
My question is, do we have similar numbers for the remaining subgroups? even partial numbers, or total arrangements for each group?

Comment viewing options

RUF subgroup

Thanks B MacKenzie and Bruce Norskog.

The RUF enumeration done by B MacKenzie is very interesting because the total reached 12,943,737,711,485 is only 10 magnitudes away from the size of this group 170,659,735,142,400

Questions to B MacKenzie:

Why did you stop your calculations? Not enough memory or too much time to complete the next depth?

Do you have estimations of the time/memory requirements for your program to calculate the numbers for all depths? I will be very happy to see God's number for this RUF subgroup.

In addition to RUF, do you have similar numbers for RUL?

Thanks

RUL C2v Three Face Group

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 C2v three face group is smaller than the C3v group, the C2v three face diameter is deeper than the C3v three face diameter. This follows from turns of opposite faces commuting, e.g. R L = L R. The branching factor for C2v group is lower than for the C3v group: ~3.7 as opposed to ~4.4.

29q!

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.

RUL 30q Element

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.

Cosets of the RUL subgroup

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

Rubik Group Coset Solvers

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

RUL cosets distribution

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.

Time constraints

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.

Subgroups

Jaap Scherphuis has an extensive list of the sizes of various Rubik's cube subgroups on his site. Those you list are the only ones that I know of that have had the states at depth enumerated fully. Group 9 in your list is the full Rubik's cube group—all group members are accessible with turns of just five of the six faces. Of course a five face metric would give a different depth distribution from a six face metric.

Some partial distributions

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

UDF again, and some FTM numbers

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