# Subgroups using basic 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 ------ 1The subgroup 2) generated only by the move U, has the following table:

Moves Deep arrangements (q only) 0 1 1 2 2 1 ------ 4The 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 ------ 16The 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,200My question is, do we have similar numbers for the remaining subgroups? even partial numbers, or total arrangements for each group?

## Comment viewing options

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

### 29q!

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.

### About the Solver

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

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 10^{13} 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

0 1 1 6 2 59 3 482 4 3232 5 18961 6 79719 7 137571 8 30241 9 64 -------------- 270336If 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

## RUF subgroup

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