# God's numbers for partial solves



## irontwig (Jun 6, 2011)

We all know that (by now) that God's number for the entire 3x3x3 is 20. Also God's number is known for LL (16) and tripod finish (15). What about e.g. LS+LL or "2x2x3 finish"? Also does there exist a position with all the edges solved that still requires 20 moves?


----------



## Kirjava (Jun 6, 2011)

irontwig said:


> "2x2x3 finish"


 
wat


----------



## Jaysammey777 (Jun 6, 2011)

I thought it was 18 not 20


----------



## irontwig (Jun 6, 2011)

Kirjava said:


> wat


 
Petrus steps 3+4+5+6+7.


----------



## Kirjava (Jun 6, 2011)

irontwig said:


> Petrus steps 3+4+5+6+7.


 
I thought you meant a 2x2x3 finish, not 2x2x3 then finish.

I was like O_O


----------



## cuBerBruce (Jun 6, 2011)

Silviu Radu proved that all the configurations with all edges solved require at most 22 quarter turns (http://cubezzz.duckdns.org/drupal/?q=node/view/33). I'll try to take a look at the cases that might require 20 face turns. (I suspect it may still be a big task to prove all of these cases to be < 20f*).


----------



## qqwref (Jun 6, 2011)

Hm, if there are about 44 million cases for the corners, it should actually be doable to get the optimal quarter and half turn distribution for the entire set... A lot of work, but doable.


----------



## cuBerBruce (Jun 6, 2011)

qqwref said:


> Hm, if there are about 44 million cases for the corners, it should actually be doable to get the optimal quarter and half turn distribution for the entire set... A lot of work, but doable.


 
From Radu's data, I counted 438101 cases not trivially less than 20f*.


----------



## uberCuber (Jun 6, 2011)

God's number for the cross is commonly known. Are any of these known?

2x2x2
XCross
2x2x3
1x2x3
EOLine


----------



## rokicki (Jun 6, 2011)

qqwref said:


> Hm, if there are about 44 million cases for the corners, it should actually be doable to get the optimal quarter and half turn distribution for the entire set... A lot of work, but doable.


 
Actually very little work. I have a coset solver for this subgroup (and all of its cosets) and it runs very fast; this was the first coset solver I wrote.

There are some results already on the cubelovers list; I'll dig out pointers this evening. The trivial coset was one of the first I ran.


----------



## rokicki (Jun 6, 2011)

Actually, didn't take long at all; here's the results from 2006:

http://cubezzz.dyndns.org/drupal/?q=node/view/41

When all edges are solved the worst case is 19 moves remaining. There are 216 such positions (out of the 44 million).


----------



## cuBerBruce (Jun 6, 2011)

Building a specific 2x2x3 can require 12 moves. That's the worst case.

For color neutral 2x2x3, the worst case is 11 moves.

EDIT 1: For a specific 2x2x2 block, the worst case is 8 moves. It's also known to be 8 for the color neutral case.

EDIT 2: Building a specific Xcross can require up to 10 moves (face turns). See [post]110398[/post]. I have independently confirmed this.

Building Xcross from the superflip position requires 9 moves, so God's number for the color neutral case is either 9 or 10.

EDIT 3: I see this post ( [post]185213[/post] ) contains all the answers (face turn metric) to all the cases uberCuber asked about.

EDIT 4: God's number for Petrus steps 3-7 is at least 18.

Example: B' R2 B2 R2 U' L2 R' F R' B F2 D2 L2 B2 U F R' U' (18f*)

If anyone cares, God's number for "2x2x3 finish" is 17.
U' R U' F U' B2 U' F2 L2 D B F L2 B U R' U' (17f*) 
R2 U B F2 D' U' L' F' L' U2 L2 U2 F' D B' R' U' (17f*)


----------



## cuBerBruce (Jun 9, 2011)

I thought I would list a few more God's numbers for partial solves.

ZBLL, without AUF: 15
ZBLL, with AUF: 16
ELL (following CLL), without AUF: 13
ELL (following CLL), with AUF: 14
CLL (following ELL), without AUF: 15
CLL (following ELL), with AUF: 16
LL with a 1x2x2 block formed, without AUF: 14
LL with a 1x2x2 block formed, with AUF: 14

(For LL with a 1x2x2 block formed, the only position where all four AUF cases are 14f* is V-Perm.)

Roux Step 4 (L6E and last 4 centers - 46080 positions): 16
<M, U> group (but solved optimally in terms of face turns, 184320 positions): 16


----------



## irontwig (Jun 10, 2011)

If I'm not mistaken LL with a solved pair also requires at most 14 htm.

Any lower bounds for S3-S7 with 0, 2 or 4 bad edges?


----------



## cubernya (Jun 10, 2011)

2x2 is also well known, 14q 11f


----------



## Cubenovice (Jun 10, 2011)

To check my (in)efficiency at FMC I would like to know God’s number for the following sub steps:
-	F2L- slot with no edges oriented, to “leaving 3 corners”
-	F2L- slot with two edges oriented, to “leaving 3 corners”
-	F2L- slot with all edges oriented, to “leaving 3 corners”

Same for “leaving 5 corners”

To keep things “simple” let’s assume the remaining corners should not be twisted in place.


----------



## cuBerBruce (Jun 10, 2011)

Cubenovice said:


> To check my (in)efficiency at FMC I would like to know God’s number for the following sub steps:
> -	F2L- slot with no edges oriented, to “leaving 3 corners”
> -	F2L- slot with two edges oriented, to “leaving 3 corners”
> -	F2L- slot with all edges oriented, to “leaving 3 corners”


 
You need to define what you mean by edge orientation. If a last layer edge is in the slot, do you *define* that edge to be oriented?


----------



## Cubenovice (Jun 10, 2011)

I guess calling it "neutral" as per Heise's definition doesn't really help ;-)

So yes: an LL edge in the slot should be considered oriented.


----------



## cuBerBruce (Jun 10, 2011)

irontwig said:


> If I'm not mistaken LL with a solved pair also requires at most 14 htm.


That's only true if you're only concerned with solving the last layer with respect to itself. An additional AUF move may be required.
Examples:
B' R D B L' B L2 U2 B L' D' R B2 R2 U2 (15f*)
R U R2 F2 D' R2 B L' B' R2 D F' R F' U2 (15f*) 
B F' D U' F U F' L D' B' L U' L' F U2 (15f*) 
L2 D R F2 R F' D' F2 L D2 R2 B D2 L U' (15f*) 
L' U B2 R' B2 R' F R B2 F' R B2 U' L U' (15f*) 
R2 D' R U' R' D R' B U B' U' R2 U2 R U' (15f*) 
R' U' F' U L' U2 L F2 R2 B' R2 F' R B U' (15f*) 

LL with at least 1 oriented CE pair, without AUF: 14
LL with at least 1 oriented CE pair, with AUF: 15


----------



## Athefre (Jun 10, 2011)

A couple of things I've been interested in:

- Average for a non-matching layer (2x2x2, completely color neutral). For example do R, R', or R2. This versus the average for a matching layer.
- Average for non-matching EG. An example setup is F2RU2RUR'UR.


----------



## riffz (Jun 10, 2011)

Mmm yes. I would be interested in hearing move distributions for colour neutral first layers compared to ones using pseudoblocks, but I'm really only interested in the half turn away scenario.


----------



## cuBerBruce (Jun 10, 2011)

Cubenovice said:


> To check my (in)efficiency at FMC I would like to know God’s number for the following sub steps:
> -	F2L- slot with no edges oriented, to “leaving 3 corners”
> -	F2L- slot with two edges oriented, to “leaving 3 corners”
> -	F2L- slot with all edges oriented, to “leaving 3 corners”
> ...


 
I've previously run JAcube on all 69 non-trivial cases (mod pre-AUF, post-AUF, and reflections) of solving the edges after F2L minus one slot. I find that whether you're interested in no edges misoriented, 2 edges misoriented, or 4 edges misoriented, there exist cases that require 9 moves to solve just the edges. After counting the pre-AUF and post-AUF, possibly 11 moves might be required. I have verified, however, that for no edges misoriented, that solving the edges requires at most 10 moves. (I've used the assumption that a last layer edge in the slot is always considered oriented.)

Existing software doesn't readily permit directly calculating for situations like leaving a corner 3-cycle or leaving a corner 5-cycle. One approach may be to search for solutions for solving the edges, and check resulting corner configuration for each solution.


----------



## Cubenovice (Jun 11, 2011)

THX Bruce!


----------



## blackzabbathfan (Jun 11, 2011)

imagine knowing all of god's algorithms, that guy would be amazing at blind


----------



## AvGalen (Jun 11, 2011)

blackzabbathfan said:


> imagine knowing all of god's algorithms, that guy would be amazing at blind


 
Only if he could remember the alg quick enough and execute it quick enough.
For a computer/robot it would probably be faster to calculate and execute a non-optimal 21 move alg then to calculate and execute an optimal 19 move alg


----------



## rokicki (Jun 12, 2011)

For a set of 1000 random positions, the two-phase algorithm on a recent PC,
given 100ms to work with, can calculate on average a solution of length 19.
So a lot depends on how fast your robot is.


----------



## Athefre (Jun 17, 2011)

Does anyone know how to calculate the average for color neutral non-matching CLL (R', R, and R2 layers) versus CLL and color neutral non-matching EG (R', R, and R2 faces) versus EG?


----------



## oll+phase+sync (Jun 18, 2011)

Athefre said:


> Does anyone know how to calculate the average for color neutral non-matching CLL (R', R, and R2 layers) versus CLL and color neutral non-matching EG (R', R, and R2 faces) versus EG?


 
Isn't the average of neutral non-matching CLL equal to (average of CLL) + 1.5 (1.5 from Aufing R and then U ) ?

What's the difference for the first layer ?


----------



## David Zemdegs (Jun 18, 2011)

A recent program an a science show here in Australia: http://www.abc.net.au/catalyst/stories/3233961.htm


----------



## Cubenovice (Jun 18, 2011)

fazdad said:


> A recent program an a science show here in Australia: http://www.abc.net.au/catalyst/stories/3233961.htm


 
very nice!

Thanks for sharing


----------



## Stefan (Jun 18, 2011)

fazdad said:


> A recent program an a science show here in Australia: http://www.abc.net.au/catalyst/stories/3233961.htm


 
Great video! This should have its own thread (or maybe be in the 20-thread).

(and great for me to finally see Tom and John on video (I've known them for ~9 years from TopCoder))


----------



## Athefre (Jun 18, 2011)

oll+phase+sync said:


> Isn't the average of neutral non-matching CLL equal to (average of CLL) + 1.5 (1.5 from Aufing R and then U ) ?
> 
> What's the difference for the first layer ?


 
Yep. The only information I'm wanting is layer versus non-matching layer and face versus non-matching face.


----------



## Lucas Garron (Jun 18, 2011)

Stefan said:


> Great video! This should have its own thread (or maybe be in the 20-thread).
> 
> (and great for me to finally see Tom and John on video (I've known them for ~9 years from TopCoder))


Hmm, I randomly seeked the video and saw 43,000,000,000,000,000,000. 

But the transcript looks better. Will try to watch when I'm done coding.

EDIT: Just watched it. Apart from that single part, looks like the best cubing TV report I've ever seen; thorough and accessible. It's too bad this would never spread as fast as fake news. :-/


----------



## riffz (Jul 6, 2011)

God's number for a pure 5-cycle of edges?

God's number for a pure 5-cycle of corners?

It would be even more awesome to get the move-count distribution


----------



## cuBerBruce (Jul 7, 2011)

riffz said:


> God's number for a pure 5-cycle of edges?
> 
> God's number for a pure 5-cycle of corners?
> 
> It would be even more awesome to get the move-count distribution


 
All corner 5-cycles can be solved in 15 or less face turns.

The distribution in terms of symmetry/antisymmetry equivalence classes is given below. Note that the equivalence classes are not all the same size so you can't calculate the exact average from these numbers.

Cube Explorer was used to generate this distribution.

Cubes solved optimally: 1152

10f*: 13
11f*: 31
12f*: 229
13f*: 445
14f*: 414
15f*: 20

EDIT:
For edge 5-cycles, again up to 15 face turns may be required. The distribution (again reduced by symmetry/antisymmetry) is below.

Cubes solved optimally: 3272

6f*: 3
7f*: 5
8f*: 23
9f*: 57
10f*: 248
11f*: 579
12f*: 1212
13f*: 1011
14f*: 132
15f*: 2

Shortest maneuvers include:
L' R B L R' U' (6f*) 
B' U' B F' L F (6f*) 
L U' L' R B R' (6f*) 

Longest optimal maneuvers include:
U F R U2 F' R B F' U' B' F2 U2 R' F' U' (15f*) 
L2 D U' F2 R U2 F' U2 R2 U2 F' D2 L D U' (15f*)


----------



## riffz (Jul 7, 2011)

Awesome. Thanks, Bruce.


----------



## reThinking the Cube (Jul 8, 2011)

cuBerBruce said:


> All corner 5-cycles can be solved in 15 or less face turns.
> 
> The distribution in terms of symmetry/antisymmetry equivalence classes is given below. Note that the equivalence classes are not all the same size so you can't calculate the exact average from these numbers.
> 
> ...



For 5-corners located at (1) DFR and (4) in U-layer?
And then, not counting any equivalencies that can be achieved by AUF?


----------



## cuBerBruce (Jul 8, 2011)

reThinking the Cube said:


> For 5-corners located at (1) DFR and (4) in U-layer?
> And then, not counting any equivalencies that can be achieved by AUF?


 
The full distribution of 5-cycles for these 5 corners is given below. Since this is not a symmetry-reduced distribution, the exact average can be calculated. It is 13 + 67/486 or approximately 13.1379.

Cubes solved optimally: 1944

10f*: 24
11f*: 52
12f*: 372
13f*: 716
14f*: 744
15f*: 36

For the 2nd part, I assume you want these 5-cycles grouped in sets of 4 through conjugation by AUF moves, and only counting the shortest maneuver for each set of four configurations.

EDIT: Based upon the above assumptions, I've rerun the 1944 with the sets of 4 cases grouped together, and used a perl script to extract the best of each set of 4 configurations. The result I get is:

10f*: 16
11f*: 20
12f*: 186
13f*: 212
14f*: 52

Total cases: 486

By using conjugations without bothering to count the setup and undo setup moves, we get a "better than optimal" distance distribution.


----------



## mrCage (Jul 9, 2011)

God's number for inserting edge/corner 5-cycle into a skeleton?? Hehe ... Move cancellations is the issue here!!

Per


----------



## irontwig (Jul 9, 2011)

mrCage said:


> God's number for inserting edge/corner 5-cycle into a skeleton?? Hehe ... Move cancellations is the issue here!!
> 
> Per


 
Yeah, and the "worst" case is when you have a zero move skeleton .


----------



## Cubenovice (Jul 9, 2011)

mrCage said:


> God's number for inserting edge/corner 5-cycle into a skeleton?? Hehe ... Move cancellations is the issue here!!
> 
> Per


 
God's "insertion cancellations" are opposite proportional to the quality of the skeleton ;-)


----------



## Gaétan Guimond (Jul 9, 2011)

;-)


----------



## Escher (Jul 9, 2011)

Has anybody calculated God's number for the F in CFOP, restricted to using a set of pre-determined, pair-solving algorithms (and mirrors)?

I know extremely little about programming, but I'm assuming it shouldn't be too hard to define a list of sequences that can be used to solve each pair sequentially and independently, and then brute-force solve all non-isomorphic positions on the 3x3 that have 4 edges solved around a face, and display the 'optimal' solution for each scramble (move distributions would be cool too).

Considering the computation would have to solve hundreds of different combinations for each cube I imagine it would be a big job.

I'm not that interested in the God's number itself but it would be interesting to study a bunch of the solutions, I'm currently trying to write down some ideas about pair selection and it would be nice to do a little analysis, though I don't really want to discuss my current thoughts here (or put my foot in anything pre-emptively).

If anybody has done this or wants to give it a go I'd be very grateful and it'd be cool to see the results.

Thanks,
Rowan.


----------



## Stefan (Jul 9, 2011)

Escher said:


> brute-force solve all non-isomorphic positions on the 3x3 that have 4 edges solved around a face



I think there are 914 million (24*21*18*15 * 16*14*12*10 / 4) positions to check, right?



Escher said:


> Considering the computation would have to solve hundreds of different combinations for each cube I imagine it would be a big job.



After one slot is solved, there are only 9.5 million positions left, which could be precomputed. So for a given cube with cross solved, you could just try each of the four slots with each of its possible algs, and then look up the number of moves for the remaining three slots.


----------



## reThinking the Cube (Jul 9, 2011)

cuBerBruce said:


> ...For the 2nd part, I assume you want these 5-cycles grouped in sets of 4 through conjugation by AUF moves, and only counting the shortest maneuver for each set of four configurations.
> 
> EDIT: Based upon the above assumptions, I've rerun the 1944 with the sets of 4 cases grouped together, and used a perl script to extract the best of each set of 4 configurations. The result I get is:
> 
> ...



Thanks Bruce, that is exactly what I wanted, and much quicker than I expected too. Possible orientation patterns for those 5-cycles of corners are too many (81), so I don't want to suggest burdening you with the task of analyzing them individually. But, it would be nice to know - the shortest manuever distributions for just the 6 (can be symmetrically reduced to 2 if you like) unique permutation patterns of those 486 5-cycle corner cases. That would be rather useful to me.


----------



## Escher (Jul 10, 2011)

Stefan said:


> I think there are 914 million (24*21*18*15 * 16*14*12*10 / 4) positions to check, right?


Looks fine to me.


Stefan said:


> After one slot is solved, there are only 9.5 million positions left, which could be precomputed. So for a given cube with cross solved, you could just try each of the four slots with each of its possible algs, and then look up the number of moves for the remaining three slots.



Neat, I wasn't sure how to go about clever shortcuts, it actually sounds like quite a lot less work than I thought.

Would working 'backwards' from the shortest solution and cascading them make solving the longer cases trivial? Unless that's what you mean by 'precomputing'...

Also, if algorithms were included that changed another part of the f2l (i.e R2 U R U' R2'), would that make it much more complicated than solving them independently? I imagine you'd just have to specify for each algorithm whether it affected another slot and if so which in relation to it.

Thanks for answering, btw.


----------

