3-face subgroup of the 3x3x3 cube

Somewhat surprisingly I was unable to find any tables for the number of positions of various lengths in ascending order for this order 170659735142400 group w.r.t. three mutually orthogonal face generators such as U,F and R, i.e. This is seemingly beyond the reach of conventional software tools to solve, so I am appealing to the seemingly large number of contributors who have developed their own bespoke utilities. I'd be grateful if a table could be posted here. In particular is the diameter of the Cayley graph for this known?

Comment viewing options

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

Three face group

Here are the counts out to depth 9:

C3v Three Face States at Depth

Depth    States
0             1
1             6 
2            27
3           120
4           534 
5          2376
6         10560
7         46920
8        208296
9        923586

As far as I know the diameter of the Cayley graph is unknown. It is a least 26. The two states (and their symmetry conjugates) which are as close as one can get to superflip in this group both are depth 26 in the q-turn metric.

F U R' F R U' R' U R' F R' U' U' R' F' R F' R U F' R F U' U' R' R'

F' U' R U' R' F' U' U' R' R' F' U' R' U R' F' U' U' R' U' U' R' R' U' R' R'

Possible errata

Are you sure this is right? Unless I have missed out on an obvious relation of small length I think the table posted below is the correct one up to length 9. Admittedly I am using a presentation for an infinite supergroup of the group generated by {U,F,R} to derive the counts for low lengths which is potentially fraught with danger.
Length Positions
0      1
1      6
2      27
3      120
4      534
5      2376
6      10572
7      47040
8      209304
9      931296

Three Face Tree Expansion

The results are solid. To check I rewrote the code without symmetry reduction and other tricks and got the same results. The code is pretty straightforward:


// States at depth for the C3v Three Face Group

-(void)test: (id)argument
{
	NSMutableSet	*allStates, *current, *next,*swap;
	RM_Turn			gen[6] = { Rr, Rs, Ur, Us, Fr, Fs };
	unsigned		depth, n;
	NSData			*state, *product;
	NSAutoreleasePool	*threadPool;
	
	threadPool = [[NSAutoreleasePool alloc] init];
	
	for( depth = 0 ; depth < 11 ; depth++ )
	{
		if( depth == 0 ) //Seed the generator with the identity state
		{
			allStates = [NSMutableSet setWithObject: [self identityState]];
			current = [NSMutableSet setWithCapacity: 1024];
			next = [NSMutableSet setWithSet: allStates];
		}
		else 
		{
			for(state in current) //Generate the states at depth + 1
			{
				for( n = 0 ; n < 6 ; n++ ) //apply the six turns to the parent state
				{
					product = [self productStateOfOperatorState: [faceTurns objectAtIndex: gen[n]] andState: state];
					
					if( [allStates member: product] == nil ) //test for duplicates
					{
						[next addObject: product];
						[allStates addObject: product];
					}
				}
			}
		}
		swap = current;
		current = next;
		next = swap;
		[next removeAllObjects];
		[self report: [NSString stringWithFormat: @"\n%2d%10d%10d", depth, [current count], [allStates count]]];

	}
    
    [[NSNotificationCenter defaultCenter] postNotificationName: RM_PROCESS_COMPLETE object: nil];
    [threadPool release];
}

Output:

Depth States     Total
 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

Job complete: time: 00:00:26.8
Ready

You're right - my table is wrong!

Even with an overnight run with many more irredundant relations (>30) I could not get the length 6 one down to the value 10560.
Even the length 9 one did not come down by any. I suspect the transition from infinite to finite will be exact (i.e. it will be unlikely to come up with a finite proper supergroup based on the random but symmetric relations that I used).

As an exercise I also did similar investigations into presentations of infinite supergroups of two orthogonal faces, e.g. {U,F}. The divergence seems to occur at length 10 where the number of position is 11478 (30 more than in the finite 2-generator case).

BTW what are the antipodes specifically in terms of U and F in the 2-face case if I may ask? In a previous thread I see this was discussed but no mention of how many at the diameter 25q? Although I am more intersted in the 3-generator case...

C2v Two Face Group Antipodes

As it turns out at one time I played around with the C2v two face group and happened to have saved the antipodal positions (reduced by symmetry ). Here are solutions for representative members of the twenty-seven depth 25 equivalence classes for the RU group.

Solving Cube State 1
Configuration:  DR UR UF BR DF UL DB DL UB FL FR BL RBU FUL UBL RDB DRF DFL DLB FRU
Symmetries:
 1   x, y, z  E
Solution found: 25 q-turns
R' U R U2 R U' R' U R' U' R' U R U' R2 U2 R U' R U' R U'

Solving Cube State 2
Configuration:  UF UR UB UL DF DR DB DL BR FL FR BL FDR BRD LFU LUB FRU DFL DLB BUR
Symmetries:
 1   x, y, z  E
 2   x, y,-z  Sigma_h
Solution found: 25 q-turns
R U2 R U R' U' R' U' R2 U R U2 R2 U R U' R' U2 R' U'

Solving Cube State 3
Configuration:  UF DR UL FR DF UB DB DL BR FL UR BL URB RUF DRF BRD BLU DFL DLB FUL
Symmetries:
 1   x, y, z  E
Solution found: 25 q-turns
U R U2 R' U R' U R U2 R U R' U' R U2 R' U R' U R' U' R

Solving Cube State 4
Configuration:  DR UR FR BR DF UL DB DL UF FL UB BL BLU FUL URB RDB RUF DFL DLB FDR
Symmetries:
 1   x, y, z  E
Solution found: 25 q-turns
U2 R2 U2 R' U' R' U R' U R' U R U' R U R' U2 R' U' R U'

Solving Cube State 5
Configuration:  BR UR FR DR DF UL DB DL UB FL UF BL BUR FRU FUL BLU DBR DFL DLB DRF
Symmetries:
 1   x, y, z  E
 2   x, y,-z  Sigma_h
Solution found: 25 q-turns
R' U2 R U R2 U R U' R U2 R U R' U R2 U' R U2 R2

Solving Cube State 6
Configuration:  UB DR UF UL DF UR DB DL BR FL FR BL RBU RUF LFU LUB DBR DFL DLB DRF
Symmetries:
 1   x, y, z  E
 2   x, y,-z  Sigma_h
Solution found: 25 q-turns
U R U R' U' R U2 R' U2 R' U R2 U2 R' U R' U R' U R U'

Solving Cube State 7
Configuration:  UF BR DR UB DF UR DB DL UL FL FR BL RBU UFR FDR BRD UBL DFL DLB FUL
Symmetries:
 1   x, y, z  E
Solution found: 25 q-turns
U2 R' U2 R' U' R' U R' U R U' R' U R U' R U R' U R U' R2

Solving Cube State 8
Configuration:  UL UR FR DR DF BR DB DL UF FL UB BL RBU DRF UFR ULF LUB DFL DLB DBR
Symmetries:
 1   x, y, z  E
Solution found: 25 q-turns
R U2 R2 U R' U R U2 R U' R U2 R2 U' R2 U' R U R

Solving Cube State 9
Configuration:  UF BR DR FR DF UB DB DL UL FL UR BL LFU LUB RBU RUF DBR DFL DLB DRF
Symmetries:
 1   x, y, z  E
Solution found: 25 q-turns
U' R U2 R' U' R' U R U R' U' R U2 R' U' R U' R2 U2 R U

Solving Cube State 10
Configuration:  FR UR BR DR DF UL DB DL UF FL UB BL RBU RUF ULF UBL BRD DFL DLB FDR
Symmetries:
 1   x, y, z  E
 2   y, x,-z  C2
 3   y, x, z  Sigma_d
 4   x, y,-z  Sigma_h
Solution found: 25 q-turns
U R U R U2 R2 U' R U' R U' R2 U2 R U R U2 R U' R'

Solving Cube State 11
Configuration:  DR UR FR BR DF UB DB DL UL FL UF BL RBU RUF DRF RDB LUB DFL DLB FUL
Symmetries:
 1   x, y, z  E
 2   y, x, z  Sigma_d
Solution found: 25 q-turns
U R U R U R2 U R U' R U' R U R U' R U' R U R' U R' U R

Solving Cube State 12
Configuration:  UF FR DR UR DF UL DB DL BR FL UB BL RFD BRD ULF UBL FRU DFL DLB URB
Symmetries:
 1   x, y, z  E
Solution found: 25 q-turns
R U2 R U' R' U R' U' R' U R2 U R' U R U' R U R U' R' U R'

Solving Cube State 13
Configuration:  UB DR UF UL DF UR DB DL BR FL FR BL FUL BLU BUR FRU BRD DFL DLB FDR
Symmetries:
 1   x, y, z  E
 2   x, y,-z  Sigma_h
Solution found: 25 q-turns
R' U' R U R U2 R2 U' R U R' U' R' U' R U R U R U R' U R'

Solving Cube State 14
Configuration:  BR UL FR DR DF UR DB DL UF FL UB BL RBU UBL BRD FDR FRU DFL DLB LFU
Symmetries:
 1   x, y, z  E
Solution found: 25 q-turns
R U2 R' U' R2 U R' U R U R' U' R2 U2 R' U' R' U2 R2

Solving Cube State 15
Configuration:  UF UL BR DR DF UB DB DL UR FL FR BL FDR DBR ULF UBL RUF DFL DLB BUR
Symmetries:
 1   x, y, z  E
Solution found: 25 q-turns
U2 R U R' U2 R' U' R U' R2 U R' U' R2 U2 R' U R' U' R

Solving Cube State 16
Configuration:  BR UR UF UL DF DR DB DL UB FL FR BL FRU RBU FUL RDB LUB DFL DLB RFD
Symmetries:
 1   x, y, z  E
Solution found: 25 q-turns
R U R U2 R' U R U' R U2 R2 U R U R2 U' R U R' U R

Solving Cube State 17
Configuration:  BR FR UR DR DF UL DB DL UF FL UB BL ULF FRU BUR UBL DRF DFL DLB DBR
Symmetries:
 1   x, y, z  E
Solution found: 25 q-turns
R' U2 R' U R U2 R' U R U' R U' R U' R' U2 R' U' R' U R U

Solving Cube State 18
Configuration:  DR UL FR BR DF UR DB DL UB FL UF BL FDR RUF URB RDB FUL DFL DLB BLU
Symmetries:
 1   x, y, z  E
Solution found: 25 q-turns
U R U2 R' U R U' R U R' U' R U' R U R' U R' U2 R' U R U

Solving Cube State 19
Configuration:  UF UR DR BR DF UL DB DL FR FL UB BL BRD RUF ULF FDR URB DFL DLB BLU
Symmetries:
 1   x, y, z  E
Solution found: 25 q-turns
U R U R U R2 U R' U R' U' R U' R U2 R' U R U' R' U' R' U'

Solving Cube State 20
Configuration:  UF UR DR BR DF UL DB DL FR FL UB BL RBU ULF FRU FDR BRD DFL DLB BLU
Symmetries:
 1   x, y, z  E
Solution found: 25 q-turns
R U R' U2 R' U2 R' U' R' U' R U' R U R' U' R2 U2 R U' R

Solving Cube State 21
Configuration:  BR UR FR DR DF UL DB DL UB FL UF BL RBU RUF FDR DBR BLU DFL DLB ULF
Symmetries:
 1   x, y, z  E
 2   y, x, z  Sigma_d
Solution found: 25 q-turns
U R U R U2 R U2 R' U R' U R U' R U' R' U R' U' R U2 R

Solving Cube State 22
Configuration:  BR FR UR DR DF UL DB DL UF FL UB BL DRF UFR UBL ULF BRD DFL DLB BUR
Symmetries:
 1   x, y, z  E
Solution found: 25 q-turns
U2 R' U' R2 U' R U2 R' U' R U' R U2 R2 U' R U' R' U' R

Solving Cube State 23
Configuration:  DR UR FR BR DF UB DB DL UL FL UF BL RBU RUF FDR RDB LUB DFL DLB ULF
Symmetries:
 1   x, y, z  E
 2   y, x, z  Sigma_d
Solution found: 25 q-turns
U R U R U2 R' U R' U' R U R' U' R' U2 R' U R2 U' R' U' R

Solving Cube State 24
Configuration:  DR FR UR BR DF UL DB DL UB FL UF BL RUF RBU RFD BLU DBR DFL DLB LFU
Symmetries:
 1   x, y, z  E
Solution found: 25 q-turns
R U2 R' U' R2 U' R2 U R' U' R' U R U R' U' R2 U2 R2

Solving Cube State 25
Configuration:  UB DR UF UL DF UR DB DL BR FL FR BL RFD RDB ULF UBL RUF DFL DLB RBU
Symmetries:
 1   x, y, z  E
 2   x, y,-z  Sigma_h
Solution found: 25 q-turns
U2 R2 U R' U2 R' U R' U R' U R2 U' R U R' U' R U' R' U

Solving Cube State 26
Configuration:  BR DR FR UL DF UR DB DL UB FL UF BL URB UFR FUL BLU DBR DFL DLB DRF
Symmetries:
 1   x, y, z  E
 2   x, y,-z  Sigma_h
Solution found: 25 q-turns
U2 R' U2 R U' R2 U' R U2 R U2 R U2 R U' R U2 R'

Solving Cube State 27
Configuration:  DR UR FR BR DF UL DB DL UF FL UB BL FDR LUB ULF RDB BUR DFL DLB FRU
Symmetries:
 1   x, y, z  E
Solution found: 25 q-turns
R' U R U2 R' U2 R U' R U' R' U R2 U R U' R U' R' U' R U'

The second of these potential

The second of these potentially antipodal positions (3 in total) is quite interesting. I thought that perhaps it might require 28q for no particular reason.

What about the position (3 by symmetry) where the three faces are rotated clockwise with the exception of the three centre spots and one diagonally opposed corner to the 2x2x2 fixed block which stays fixed - together with the "mini-superflip" of the second type above?
I know the 4-spot+superflip case of M. Reid in the 3x3x3 is quite a different propostion.

I don't have a method for finding such sequences.

Three Face Group Distribution

Your candidate position doesn't pan out. It may be solved in 22 q-turns:

Solving state: RF FU LF DF RB UB DB DL UR DR UL BL UFR FUL FLD FDR BUR BRD DLB BLU
Target Depth: 0 2 4 6 8 10 12 14 16 18 20 22 Time: 00:00:00.6
U' F' R' F R2 F2 R U F U' F' U R F U' R U' R F' R

As an educated guess, I would say the diameter of the group is almost certainly not 26. I would say 27 or perhaps as high as 28. Solving 1000 random cubes gives the distribution:

 Depth  Count   Fraction Log(n)
   17     1      0.10%    11.23
   18     6      0.60%    12.01
   19    16      1.60%    12.44
   20    46      4.60%    12.89
   21   186     18.60%    13.50
   22   386     38.60%    13.82
   23   296     29.60%    13.70
   24    62      6.20%    13.02
   25     1      0.10%    11.23

The distribution maxes out at 22 turns with nearly 1014 states. From depth 24 to depth 25 the number of states drops by approximately two orders of magnitude. These distributions drop off in an accelerated manner on the far side of the maximum so I would expect the count at depth 26 to be four or five orders of magnitude less than the depth 25 count. This would give 106 or 107 depth 26 positions. From there I would expect a handful of positions at depth 27 perhaps then tailing off to a position or two at depth 28.

Just to clarify...

This was just idle speculation on my part as to what positions might be antipodal in the case of the 3-generator group of the 3x3x3 cube. Obviously I was off the mark in this instance.

I wonder if I may try your patience one last time? Could you minus out the 8-edge mini-superflip in the example above and use your software to derive the length of this unique position please?

Three Face (almost) three spot position

The state is solved in 20 turns:

Solving state: RU RF RD RB LU LF DB DL UF UB DF BL UFR RFD RDB RBU LFU LUB DLB LDF
Target Depth: 0 2 4 6 8 10 12 14 16 18 20 Time: 00:00:00.0
R U R' F2 R F R F' U' R' F U' R' F R' U F' U' R'

Looking for antipodal positions is worse than looking for a needle in a haystack. I am mystified that the (probably) antipodal 26 turn 6 face position was found so easily. It does show some symmetry but I believe all the symmetrical 6 face positions have now been solved without finding a comparable position.

Deeper Table

Using C3v + inverse symmetry reduction I can extend the above table out to depth 12:

C3v Three Face States at Depth

Depth Classes+    Elements
 0           1           1
 1           1           6
 2           4          27
 3          12         120
 4          51         534
 5         207        2376
 6         909       10560
 7        3950       46920
 8       17493      208296
 9       77153      923586
10      341597     4091739
11     1510525    18115506
12     6682605    80156049

I think the largest analysis

I think the largest analysis of this type that's been done for Rubik's cube is reducing an arbitrary cube state to the square's group (in other words, the first three Thistlethwaite phases in one step). This was done for the face-turn metric using a supercomputing cluster or something like that. It has |G| / 663,552 = 65,182,537,728,000 positions. These positions can be reduced by 48x symmetry to something on the order 1.36 trillion positions.

<U, R, F>, on the other hand, has over 2.5 times as many actual positions, and can only be reduced by about 12x using symmetry and antisymmetry. This comes to about 14.2 trillion positions. So this is basically about 10.5 times bigger than the other analysis I mentioned above.