What is God's number on a 4x4 Rubik's cube?

[Christopher Mowla]

My solver does not immediately find particularly good solutions to this in OBTM although this is no real indicator of how long its optimal solution might be. Anyone else with a solver care to try?

Here is a 50 OBTM solution: Dw' B' Lw' Dw' D Bw L Dw L2 R F' Dw R B F' Uw' L' U2 B Dw2 R' U' F2 R F2 Dw2 Bw2 R F' R' Bw2 R B D' R U' F' R2 U F D L2 B2 D2 L' D2 B2 L' B L'

It has so far only found a 31 turn reduction that eliminates the parities (without the 3x3x3).

I found shorter solutions by hand (using my own "optimized" reduction method).

(Total: 47 OBTM, Reduction: 29 OBTM, 3x3x3: 18 OBTM)
Rw' F' Rw U2 F2 L F' R2 B Rw F U' R Uw F2 Uw' L R2 U B Uw R2 Uw' L' D F Uw' L2 Uw
F R' F L' U R2 D' R' F L B2 D2 R2 D2 R2 B U R

(Total: 48 OBTM, Reduction: 30 OBTM, 3x3x3: 18 OBTM)
Rw' F' Rw U2 F2 L F' R2 B Lw D' U' Fw L2 Fw' D2 R U' Fw D2 Fw' F2 D' R' B R U Bw' R2 Bw
R2 F2 D' L2 B2 U B2 U2 R B D' F' D R D' L' R F' x

I did get a 27 OBTM reduction, but it has PLL parity, just as the 4 or 5 28 OBTMs and another 29 I found did. :fp
Rw' F' Rw U2 F2 L F' R2 B Lw D' U' Fw L2 Fw' D2 F' R Fw D2 Fw' R2 U2 L' Fw R2 Fw' x

 

[IAssemble]

I know this question wasn't directed at me, but I'm curious how many moves it takes your solver to solve the following cases:
[1] Rw' U' R' U' Rw F' R' F' Rw'
[2] Lw F2 U2 l' U2 Lw U' R U l U2 l' U R' U Lw' F2 Lw'
[3] And just a "potential bad case" to check: the case generated by this set of algorithms.

My solver found:

[1] Rw F R F Lw' B R B Lw 9 turns OBTM
[2] Rw2 U2 Rw F2 U2 Lw' B2 U2 Lw2 D2 Lw' F R F U' F' R' D' F U F' D F U' 24 turns OBTM

I will try [3] later...

something like this seems like it might need a lot of moves

Not too bad?

Uw' R2 B2 Uw' B' L U' L Uw2 F2 Dw R2 Dw2 F' U2 D B2 L F D B R2 B L U F R' B2 R F' B' 31 turn OBTM

I found shorter solutions by hand (using my own "optimized" reduction method).

(Total: 47 OBTM, Reduction: 29 OBTM, 3x3x3: 18 OBTM)
Rw' F' Rw U2 F2 L F' R2 B Rw F U' R Uw F2 Uw' L R2 U B Uw R2 Uw' L' D F Uw' L2 Uw
F R' F L' U R2 D' R' F L B2 D2 R2 D2 R2 B U R

(Total: 48 OBTM, Reduction: 30 OBTM, 3x3x3: 18 OBTM)
Rw' F' Rw U2 F2 L F' R2 B Lw D' U' Fw L2 Fw' D2 R U' Fw D2 Fw' F2 D' R' B R U Bw' R2 Bw
R2 F2 D' L2 B2 U B2 U2 R B D' F' D R D' L' R F' x

I did get a 27 OBTM reduction, but it has PLL parity, just as the 4 or 5 28 OBTMs and another 29 I found did. :fp
Rw' F' Rw U2 F2 L F' R2 B Lw D' U' Fw L2 Fw' D2 F' R Fw D2 Fw' R2 U2 L' Fw R2 Fw' x

Interesting - I am impressed that you can find such good solutions by hand.

But I'm confused...

Did you use my sequence as a generator rather than a solver? I hadn't thought of this before, but depending on the permutation of the centre pieces of the same color, I think there may be many sequences that appear to solve a given scramble so that if the same sequences are applied to a solved cube (and not reversed) they will generate different positions! I believe this does not happen on a 3x3x3 cube because all positions are distinct.

I was puzzled at first when I loaded your solutions because I could not get them to show diagonals on all four centres either by treating them as solvers or generators!

My sequence was intended to be a solver view but if you treat it as a generator, it creates the position that I suspect you used as the start position for your solve? Your solutions are from that position (which does not have diagonals on each face) to solved. These sequences are not precisely the inverse of my sequence because the same color middles are permuted in different ways...

Please can someone confirm whether my understanding is correct?

Perhaps for consistency and to avoid this happening again, we should all post either solvers or generators? What do you think?

In the mean time I fixed a minor issue with my solver that was causing it to miss exploring some potential reductions and it has subsequently found this *Solution* to the position I suggested which is the diagonal centres proposed by cmhardw with the addition of a single edge flip (note that I do not think that composing a generator for a centre diagnonal and a generator for a single edge flip generator will not necessarily generate because of the centre permutations):

U' R B' Rw2 B2 Fw2 Dw' D Rw L' Uw2 U D Lw F' R Uw R2 F' R2 F Uw' R' U F' U' R2 F D' L' D2 L B D' B U 36 turn OBTM

 

[ben1996123]

Not too bad?

Did you do a single edge flip yet?

 

[IAssemble]

Did you do a single edge flip yet?

The best it has achieved so far is:

U2 L2 Lw2 U2 F2 Lw F2 L Lw' F2 Lw2 U2 Lw R' F2 R Lw' F2 Lw L' F2 L F2 23 turn OBTM

 

[ben1996123]

The best it has achieved so far is:

U2 L2 Lw2 U2 F2 Lw F2 L Lw' F2 Lw2 U2 Lw R' F2 R Lw' F2 Lw L' F2 L F2 23 turn OBTM

mirroring and simplifying a bit:

U2 2R2 U2 x U2 r' U2 2R U2 r2 x' U2 2L' U2 2L x U2 2R' U2 R' U2 x'

30qtm

 

[IAssemble]

mirroring and simplifying a bit:

U2 2R2 U2 x U2 r' U2 2R U2 r2 x' U2 2L' U2 2L x U2 2R' U2 R' U2 x'

30qtm

Indeed, it "could be better" compared with the known best pure edge flip algorithms However, I think I expect this because of the method.

The algorithm is a reduction with parities fixed to a pure 3x3x3 position. It tries to find short solutions to the reduction phase without considering anything about the "simplicity" of the 3x3x3 position.

For example it finds this reduction for the pure edge flip case which is only 13 turns OBTM. I suspect is probably pretty short for an OBTM edge flip parity algorithm?

Uw' F R2 F' Uw' R2 Uw' R2 Uw' B' R2 B Uw'

I would argue that the chance of such an approach finding a reduction which just happens to end with the 3x3x3 solved is approaching 1 in 4.3x10^19 (possibly divided by some factors to take into account centre piece permutation and maybe less because the number of possible positions reached by a short reduction phase may be fewer than this. However, it is almost certainly far too low a probability to hit "by chance").

In order to find a good solution for a pure edge flip, I believe the algorithm would have to target the complete solution directly rather than by reduction. Of course it has already been observed that reduction is not optimal (although it it could be that the worst case position(s) has/have optimal solutions that are effectively reductions if it has a point after which only outer layer turns are made).

I am probably more interested in bounding general solutions rather than necessarily finding optimal solutions for positions that are known to be far below the lower bound of worst case. Although this is one of the things that has made me think about trying to "guide" the reduction phase towards 3x3x3 positions that are easier to solve rather than leaving it purely to chance.

Thinking further about the "reduction is not optimal" statement... could it be that reduction is optimal for the worst case positions and if so could it be proven?

What if it could be proven that:

1) one specific position (which "happens" to be one of the worst case positions) requires at least N moves
2) reduction of any position to a pure 3x3x3 position requires at most M moves
3) we already know that 3x3x3 is 20 moves worst case (thanks to Rokicki et.al.)
4) we were "lucky" and N = M+20

This would be the extreme case of using worst case reduction followed by worst case 3x3x3 to find an upper bound that happened to be equal to a lower bound found by some other method.

Even if we cannot do this, or we can do 1) and 2) but M+20 > N, finding either an N to increase the current lower bound or an M shown to reduce the known upper bound would be interesting!

Any thoughts?

 

[Christopher Mowla]

My solver found:

[1] Rw F R F Lw' B R B Lw 9 turns OBTM
[2] Rw2 U2 Rw F2 U2 Lw' B2 U2 Lw2 D2 Lw' F R F U' F' R' D' F U F' D F U' 24 turns OBTM

I will try [3] later...

Thanks. It looks like your solver is on the same page as I am for the 9 mover. For the second algorithm, I guess I wasn't being fair showing you a 21 OBTM solution I found (the briefest in OBTM I found), but I was just curious.

Did you use my sequence as a generator rather than a solver?

You're correct. My mistake.

For the sake of it, I gave the inverse a shot, but the best I could create was a 56 OBTM solution (Reduction: 38 OBTM, 3x3x3: 18 OBTM).
F' B Dw' B2 F2 Dw Lw' F Uw' F2 Uw B' Uw B2 Uw' B F U' D Fw R2 Fw' U' R2 U B Rw B2 Rw' F2 L2 D' L D' F Lw D2 Lw'
F2 L U2 F2 R U' F L' F R2 U L' D2 B2 D' B' L' U' x'

I didn't spend as much time on it as I should have, however. If this position manages to stay of great importance, I will have another crack at it...maybe I can shorten my solution a little more to perhaps be sub 50 in the future (if that's the minimum your solver can solve it in).

EDIT:
I just redid the ending of the reduction and got a 52 OBTM solution (Reduction: 35 OBTM, 3x3x3: 17 OBTM)
F' B Dw' B2 F2 Dw Lw' F Uw' F2 Uw B' Uw B2 Uw' R D F2 U Lw' F2 Lw R D2 L Bw' R2 Bw R' B R B' Lw' B2 Lw
R F2 U' F2 D B2 L2 F' D2 F2 R' D2 B L' R U2 F2 x'

 

[IAssemble]

Thanks. It looks like your solver is on the same page as I am for the 9 mover. For the second algorithm, I guess I wasn't being fair showing you a 21 OBTM solution I found (the briefest in OBTM I found), but I was just curious.

You're correct. My mistake.

For the sake of it, I gave the inverse a shot, but the best I could create was a 56 OBTM solution (Reduction: 38 OBTM, 3x3x3: 18 OBTM).
F' B Dw' B2 F2 Dw Lw' F Uw' F2 Uw B' Uw B2 Uw' B F U' D Fw R2 Fw' U' R2 U B Rw B2 Rw' F2 L2 D' L D' F Lw D2 Lw'
F2 L U2 F2 R U' F L' F R2 U L' D2 B2 D' B' L' U' x'

I didn't spend as much time on it as I should have, however. If this position manages to stay of great importance, I will have another crack at it...maybe I can shorten my solution a little more to perhaps be sub 50 in the future (if that's the minimum your solver can solve it in).

EDIT:
I just redid the ending of the reduction and got a 52 OBTM solution (Reduction: 35 OBTM, 3x3x3: 17 OBTM)
F' B Dw' B2 F2 Dw Lw' F Uw' F2 Uw B' Uw B2 Uw' R D F2 U Lw' F2 Lw R D2 L Bw' R2 Bw R' B R B' Lw' B2 Lw
R F2 U' F2 D B2 L2 F' D2 F2 R' D2 B L' R U2 F2 x'

Ah - thanks for confirming.

I suspect that it may be harder to do the reduction now because now all 6 faces have diagonal centres whereas before you were working with only two?

I mentioned that it has already found a shorter solution: U' R B' Rw2 B2 Fw2 Dw' D Rw L' Uw2 U D Lw F' R Uw R2 F' R2 F Uw' R' U F' U' R2 F D' L' D2 L B D' B U 36 turn OBTM

So diagonal centres does seem to be "hard"...

How about that diagonal center pattern, but with "2-cycles" of centers instead of 3-cycles (e.g. white-red, red-white, green-yellow, yellow-green, blue-orange orange-blue)? Maybe if we add OLL parity to the mix it will be pretty tricky.

So perhaps I should invest some time looking at the 2-cycle cases as well as this 3-cycle case...

Also, an idea: your solver seems to directly solve reduction and then 3x3x3, so what about finding a position that is very hard to reduce and then making it solve a 20f* 3x3x3 position after it?

Yes, this is where my thoughts are heading...

At a slightly different angle, does anyone have any analysis or intuition of edge parity vs. centre scramble? For solved centres it is easy to define edge parity but if the centres are scrambled I am not aware of a definite relationship. For example if you are "half way" through an edge parity algorithm, how does the "edge parity" and centres relate?

I believe that the edge parity relates to the number of quarter inner layer turns. I believe that an edge parity algorithm will always have an odd number of quarter inner layer turns. Is this correct? So when the centres are scrambled, changing edge parity only makes the reduction significantly harder if it forces significantly more turns in order to solve the centres (and pair edges) with an odd number of quarter inner layer turns than with an even number. Does that make sense?

For general, random scrambles I suspect that the centres can be solved with sequences of roughly equal length with either an odd or an even number of quarter inner layer turns (by "intuition" and empirical results) so perhaps edge parity only really makes positions with almost solved centres or symmetrical centres significantly harder?

 

[qqwref]

For example it finds this reduction for the pure edge flip case which is only 13 turns OBTM. I suspect is probably pretty short for an OBTM edge flip parity algorithm?

Uw' F R2 F' Uw' R2 Uw' R2 Uw' B' R2 B Uw'

This is a really cool alg!

 

[Christopher Mowla]

This is a really cool alg!

It is, but it's not new. I'm suprised you don't remember it (a different variation of it, which translates to all cube sizes--using either wide turns or single slice turns, is in the wiki as the very first PetrusParity algorithm on the 4x4x4 parity algorithms page).

cuBerBruce found it almost 2 and a half years ago with a solver he made:

For OLL parity (only), one such alg is:

Uw B' L2 B Uw B2 Uw R2 Uw R F2 R' Uw

He made a nice summary page of all of his optimal parity maneuver searches for the 4x4x4 on this page.

In fact, by studying cuBerBruce's algorithm, I made the following two algorithms (which you were interested in using for fixing parity on very large cubes) by just using the F face and U face: (History)
r' U2 F' U2 F U2 r' U2 r' U2 r' F' U2 F r'
l U2 F' U2 F U2 l U2 l U2 l F' U2 F l

Then I made it into <U,Rw,R> (History)
Rw' U R' U2 R U' Rw' U2 Rw' U2 Rw' U' R U2 R' U Rw'
, but Kåre Krig created this version of the algorithm independently with his solver about a year and a half before I made it. It's one of the first algorithms in his 3flip text document attached to this post (it's surrounded by outer layer turns).

And finally, I found a related path that was in <U, Rw,L> (History)
Rw' U' L' U2 L U Rw' U2 Rw' U2 Rw' U L' U2 L U' Rw'

 

[IAssemble]

It is, but it's not new. I'm suprised you don't remember it (a different variation of it, which translates to all cube sizes--using either wide turns or single slice turns, is in the wiki as the very first PetrusParity algorithm on the 4x4x4 parity algorithms page).

cuBerBruce found it almost 2 and a half years ago with a solver he made:

It isn't quite the same as the one you mention. cuBerBruce's has turns on 5 different faces rather than 4 and the outer layer 180 degree turns are on three different faces. Although I suspect someone might be able to show how one can be derived from the other...

 

[Christopher Mowla]

It isn't quite the same as the one you mention. cuBerBruce's has turns on 5 different faces rather than 4 and the outer layer 180 degree turns are on three different faces. Although I suspect someone might be able to show how one can be derived from the other...

Yeah, I derived yours from his before I made that claim, just to be sure (but I am so familiar with cuBerBruce's alg, I didn't doubt for a second).

Yours
Uw' F R2 F' Uw' R2 Uw' R2 Uw' B' R2 B Uw'

cuBerBruce's
Uw B' L2 B Uw B2 Uw R2 Uw R F2 R' Uw
(Note that cuBerBruce found over 10,000 optimal maneuvers in OBTM for both double parity and OLL parity-only cases. In this post, he gave a skeleton of how to generate a subset of the algorithms he found.)

I'm going to transform cuBerBruce's algorithm into yours:

Spoiler: Transformation

[1] Take the inverse:
Uw' R F2 R' Uw' R2 Uw' B2 Uw' B' L2 B Uw'

[2] Adding in cube rotations to affect the same portion of the cube as your alg,
z2 Uw' R F2 R' Uw' R2 Uw' B2 Uw' B' L2 B Uw' y z2
=
Dw' L F2 L' Dw' L2 Dw' B2 Dw' B' R2 B Dw' y'
=

[3] Using wide turn equivalence Dw' = (Uw' y),
= (Uw' y) L F2 L' (Uw' y) L2 (Uw' y) B2 (Uw' y) B' R2 B (Uw' y) y'
= Uw' y L F2 L' Uw' y L2 Uw' y B2 Uw' y B' R2 B Uw' y y'

[4] Carrying through the first y cube rotation,
= Uw' F R2 F' Uw' y2 L2 Uw' y B2 Uw' y B' R2 B Uw'

[5] Carrying through the second,
= Uw' F R2 F' Uw' R2 Uw' y' B2 Uw' y B' R2 B Uw'

[6] The third,
= Uw' F R2 F' Uw' R2 Uw' R2 Uw' y' y B' R2 B Uw'
= Uw' F R2 F' Uw' R2 Uw' R2 Uw' B' R2 B Uw'
= yours

Same alg. It's very interesting that your solver finds solutions like these, however. I can't imagine what type of algorithm you use (despite that I've read about your description of its basics on this forum, but "you got the brains").

 

[cuBerBruce]

(Note that cuBerBruce found over 10,000 optimal maneuvers in OBTM for both double parity and OLL parity-only cases.

I used block turn metric, not outer block turn metric. Many use inner layer turns which count as 2 turns in OBTM.

 

[ch_ts]

The best it has achieved so far is:

U2 L2 Lw2 U2 F2 Lw F2 L Lw' F2 Lw2 U2 Lw R' F2 R Lw' F2 Lw L' F2 L F2 23 turn OBTM

I ran this single edge flip through my solver. It uses slice turns not wide turns, but it did turn up something I thought was interesting.

So I scrambled with this:
U2l2U2F2LlF2l'F2L2l2U2LlR'F2RL'l'F2lF2LF2

and on the way to solving it, it passes through this position:
r' F2 r2 U2 F2 r F2 U2 r F2 r2 (3-cycle of edges, not really sure what people call this, is it a half-edge? I'm using lowercase letters to denote the inner layer)

The actual way it continued from here seemed a little roundabout so I inserted a commutator instead like this:
r' F2 r2 U2 (D'fD F2 D'f'D F2) F2 r F2 U2 r F2 r2
= r' F2 r2 U2 D'fD F2 D'f'D r F2 U2 r F2 r2

 

[Christopher Mowla]

I ran this single edge flip through my solver...and on the way to solving it, it passes through this position:
r' F2 r2 U2 F2 r F2 U2 r F2 r2 (3-cycle of edges, not really sure what people call this, is it a half-edge? I'm using lowercase letters to denote the inner layer)

It's a 4-cycle, silly. a 4-cycle + the proper 3-cycle creates a 2-cycle.

Just to let you know, the current minimum in OBTM for this case is 19. These two algorithms I found established this move count.
x' Rw2 U2 Lw' U2 r U2 Rw U2 x' U r U' F2 U r' U Rw2 x
x' Rw2 U2 Lw' U2 r U2 Rw U2 x' U' r U F2 U' r' U' Rw2 x

And the current minimum in OBQTM (qtm) for this case is 24. These two algorithms I found established this move count.
z Dw' M D Lw' Uw' r' Uw Lw Uw' Lw2' Bw' r' Bw Rw' R' u y' M' Uw x2 z' (I named it "the holy grail")
Rw' E Uw2 Fw Uw Rw' r' Fw' r Fw Rw Uw' Fw' Uw r Uw E' Rw

At a slightly different angle, does anyone have any analysis or intuition of edge parity vs. centre scramble? For solved centres it is easy to define edge parity but if the centres are scrambled I am not aware of a definite relationship.

First of all, yes, all odd-numbered dedge flip algorithms have an odd number of inner layer quarter turns. Mathematically, there is no relationship between center scrambles and edge parity, neither on the 6-colored 4x4x4 or the 4x4x4 supercube. See example 5 on page 3 of my PDF.

For example if you are "half way" through an edge parity algorithm, how does the "edge parity" and centres relate?

If we are talking about optimal algorithms for any move metric, it really depends (with algorithms which are longer than optimal, anything goes: there is no consistent pattern because there are so many more algorithms which are not move optimal). I have created a lot of these algorithms and decomposed most (if not all) other algorithms I tried to decompose.

The most interesting part of a 4x4x4 parity algorithm is where the extra quarter turn is. So the point of interest can be virtually at any point in the algorithm, though, as you said, it's more commonly closer to the middle than the immediate beginning or end.

So let's observe what the centers are like at the location where the quarter turn is:

Spoiler: Examples

Spoiler: OLL parity (only) algorithms which are not one dedge flips optimal in OBTM and optimal in OBQTM (qtm)

Taking your version of the 13 OBTM algorithm, and applying all of the algorithm before the extra quarter turn,
Uw' F R2 F' Uw' R2 Uw' R2 Uw' B' R2 B Uw'
, observe that the extra quarter turn is the next move, Uw', and notice that two red 1x2 center blocks are adjacent to each other in the u slice.

Spoiler: One dedge flip algorithms optimal in OBTM

Taking my two algorithms (which I have shown at the beginning of this post) and applying all moves before the extra quarter turn,
x' Rw2 U2 Lw' U2 r U2 Rw U2 x' U r U' F2 U r' U Rw2 x
x' Rw2 U2 Lw' U2 r U2 Rw U2 x' U' r U F2 U' r' U' Rw2 x
Notice that the extra quarter turn is the move r and notice that two white 1x2 center blocks are adjacent to each other in the r slice.

Spoiler: One dedge flip algorithms optimal in OBTQTM (qtm) and BQTM (q-b)

Taking my two algorithms (which I have shown at the beginning of this post), and executing all moves before the extra quarter turn...
z Dw' M D Lw' Uw' r' Uw Lw Uw' Lw2' Bw' r' Bw Rw' R' u y' M' Uw x2 z' (I named it "the holy grail")
The extra quarter turn is the move r'. Notice that in the r slice, the D and B faces contain two individual green X-center pieces AND the F and D faces contain two individual orange X-center pieces which are "adjacent" to each other in the same sense as the previous algorithms. Watch this (just for about a minute or so) for a vocal explanation of this formation of individual centers.

A similar situation holds for the second algorithm (the green and orange X-center pieces in the F, D, and U faces)
Rw' E Uw2 Fw Uw Rw' r' Fw' r Fw Rw Uw' Fw' Uw r Uw E' Rw

Spoiler: One dedge flip algorithms optimal in btm (h-b, BHTM, etc.)

As I stated here, there are only two main types of optimal algorithms in this move metric: symmetrical and non-symmetrical algorithms. (I define a symmetrical algorithm to be an algorithm which its first and last moves are inverses of each other. A non-symmetrical algorithm's first and last moves generally are not inverses of each other). Each type only has two distinct algorithms. So this gives us a total of 4 algorithms to look at. I put them and all of their transformations in the wiki here (note that algorithms which end in B2 could technically be two algorithms instead of one if we conjugate the algorithm with B2, since that won't change the location of the flipped dedge neither will it change the center which is rotated 180 degrees).

For the symmetrical algorithms, executing the portions of the algorithms before the extra quarter turn, we observe the same situation as we did for algorithms optimal in OBTM and OBQTM,
r2 B2 U2 l U2 r' U2 r U2 F2 r F2 l' B2 r2
r2 B2 U2 l' U2 r U2 r' U2 B2 r' B2 l B2 r2

For the non-symmetrical algorithms, we find that at the extra quarter turn, the two white 1x2 center blocks (which are going to be swapped with each other) are opposite rather than adjacent.
r' U2 l F2 l' F2 r2 U2 r U2 r' U2 F2 r2 F2
r B2 r' U2 l B2 l2 B2 U2 l U2 l' U2 l2 B2

I was successful to create a brief non-symmetrical 2-cycle algorithm in btm, but it's not optimal in btm (I made four 15 btm symmetrical algorithms), but we can see that all individual center pieces in the r slice in the top half of the cube is similar to the structure of the centers before the extra quarter turn for the optimal algorithms in OBQTM for the singe dedge flip case.
r' Uw Lw Uw' r2 Fw2 Lw' Fw r' Fw' Lw Fw2 r' Uw Lw' Uw'

Now, let's look at some more messy parity algorithms.

Spoiler: OLL parity (only) algorithm which are not one dedge flips optimal in BQTM (q-b)

We look at cuBerBruce's elegant 15 BQTM OLL parity (not double parity) solution:

...The curly braces indicate a choice of any of the moves listed within.

I note that the last two are mirror-symmetric to their own inverse.

{ Uw, u, d } (lr') R D R' Fw f (ud') l' (u'd) Fw b (u'd) F { Lw, l, r } (OLL parity)...

Choosing the wide turns as the first and last moves in the curly braces and adding cube rotations at the end (to bring all composite centers into their original positions),
Uw M R D R' Fw f E' l' E Fw b E F Lw x2 z'

You'll find in the spoiler of this post, I decomposed this algorithm to:
(Uw F' B2 R B' U) (u2 L' R u' R' L u2) (U2 D' B F' L Dw)
where the red move is the extra quarter turn.

cuBerBruce's algorithm is what I call a "single slice turn based" algorithm because wide turns are not required, although they exist in the algorithm due to different slices merging as such. The "holy grail" algorithm and the non-symmetrical 2-cycle algorithm I have above I refer to as "wide turn based" because wide turns are required.

Observe the u slice when the porition of the algorithm before the extra quarter turn (Uw F' B2 R B' U) (u2 L' R): we have "double" of the 4 X-center piece formation described for the holy grail alg (and my oriented 2-cycle non-symmetrical algorithm r' Uw Lw Uw' r2 Fw2 Lw' Fw r' Fw' Lw Fw2 r' Uw Lw' Uw'), except that all of the pieces in the u slice are "slid" once. Watch this to see what I mean by slid.

The extra quarter turn in cuBerBruce's algorithm would make more sense if all of the center pieces in the u slice had the formation I put the center pieces in the r slice in to make the optimal h-b and q-b checkboard algorithm (f2 u' r2 Uw2 S') r (S Uw2 r2 u f2)

Spoiler: OLL Parity algorithms possibly optimal in OBTM and h-b in <U, Rw,R>

I can't recall at the moment exactly which one of Kåre Krig's algs I shortened to create the following 17 move algorithm, however we can see that the two white 1x2 center blocks are again adjacent to each other in the r slice before the extra quarter turn.
Rw U2 Rw2 U' Rw' U2 Rw U2 Rw' U Rw' Rw' U2 Rw2 U R2 U' Rw'

Obviously the alg I showed in my post before last in this thread is also currently the lowest in OBTM for the move set:
Rw' U R' U2 R U' Rw' U2 Rw' U2 Rw' U' R U2 R' U Rw'

If you look carefully, this is nothing more than (Rw' U2)4 Rw' with some U and R turns inserted. My decomposition for (Rw' U2)4 Rw', as I've shown before in another thread, is:

Rw'//setup moves 1
U2 Rw' U2 Rw
Rw2 U2//setup moves 2
Rw'//extra quarter turn
U2 Rw2//undo setup moves 2
Rw//undo setup moves 1

So the portion of this algorithm before the extra quarter turn is:
Rw' U R' U2 R U' Rw' U2 Rw' U2 Rw' U' R U2 R' U Rw'
, which, again the centers have the same formation as most of the algorithms mentioned thus far.

Spoiler: Optimal one dedge flip algorithm in OBTM in <U,Rw>

At the very beginning of the second spoiler in this post, I decompose one of the two optimal algorithms for this case in this intense move restriction set.
Rw U Rw' U Rw' U Rw2 U2 Rw2 U Rw' U2 Rw U2 Rw (Rw) Rw U2 Rw' U' Rw' U' Rw U Rw' U2 Rw U2
Again, notice the formation of the individual center pieces (blue and white) in the r slice in the F and D faces.

The long <U,Rw> algorithm I found is also in that post. It's an entirely different way to tackle the same case (not on the supercube, though) in the same move set. You will find that the individual center pieces (white and yellow) have a similar formation to the one in the r slice of the "holy grail alg".

Rw U Rw U Rw U' Rw' U2 Rw2 U2 Rw U2 Rw' U Rw2 U' Rw2 U' Rw U2 Rw' U' Rw U2 Rw' U Rw U2 Rw' U' Rw U2 Rw' U' Rw U2 Rw' U Rw U2 Rw' U' Rw U2 Rw' U' Rw U2 Rw' U Rw U2 Rw' U' Rw U2 Rw' U' Rw U2 Rw' U Rw U2 Rw U Rw2 U' Rw U2 Rw2 U2 Rw2 U2 (Rw') U2 Rw U2 Rw' U2 Rw' U2 Rw2 U2 Rw2 U2 Rw' U2 Rw2 U Rw' U' Rw' U' Rw' U' Rw U2 Rw' U Rw U2 Rw' U2 Rw U Rw' U Rw U2 Rw' U2 Rw U Rw' U Rw U2 Rw' U2 Rw U Rw' U Rw U2 Rw' U2 Rw U' Rw' U' Rw U Rw' U2 Rw U2 Rw' U' Rw U' Rw' U2 Rw U2 Rw' U' Rw U' Rw' U2 Rw U2 Rw' U' Rw U2 Rw' U' Rw U Rw' U2 Rw U2 Rw' U' Rw U' Rw' U2 Rw U2 Rw' U' Rw U' Rw' U2 Rw U2 Rw' U' Rw U2 Rw' (244,187)

Note that this algorithm is single slice turned based, as its base (which can be found under step6 in the spoiler in the second spoiler in the same post) can be applied to different orbits of wings of higher order cubes like the 6x6x6, but it no longer stays 2-gen. I cannot say that the 26 move <U,Rw> algorithm is single slice turn based, and, looking at the center piece formation in at the intersection of Fw and r, we see the same formation as was in my (holy grail alg). So I'd call it wide turn based.

For general, random scrambles I suspect that the centres can be solved with sequences of roughly equal length with either an odd or an even number of quarter inner layer turns (by "intuition" and empirical results) so perhaps edge parity only really makes positions with almost solved centres or symmetrical centres significantly harder?

This seems to be the case.

 

[IAssemble]

Thanks cmowla for taking the time to write such a comprehensive response!

...

First of all, yes, all odd-numbered dedge flip algorithms have an odd number of inner layer quarter turns. Mathematically, there is no relationship between center scrambles and edge parity, neither on the 6-colored 4x4x4 or the 4x4x4 supercube. See example 5 on page 3 of my PDF.

...

The most interesting part of a 4x4x4 parity algorithm is where the extra quarter turn is. So the point of interest can be virtually at any point in the algorithm, though, as you said, it's more commonly closer to the middle than the immediate beginning or end.

...

I think these statements are immediately useful to me I am currently working on a way of optimising my reduction phase search to take into account edge parity earlier in the process to avoid wasting time searching branches which lead to reductions with edge parity which are later discarded. Confirming my understanding of odd-numbered dedge vs. inner layer turns is particularly useful and the concept of an "extra" quarter inner layer turn and its position is thought-provoking.

The rest of your response is also extremely interesting and I will take time to digest it and the links you provided.

For general, random scrambles I suspect that the centres can be solved with sequences of roughly equal length with either an odd or an even number of quarter inner layer turns (by "intuition" and empirical results) so perhaps edge parity only really makes positions with almost solved centres or symmetrical centres significantly harder?

This seems to be the case.

Thanks. I think this is reassuring that I am not heading in completely the wrong direction with my current attempts to optimize my solver a little

 

[Stefan]

I am currently working on a way of optimising my reduction phase search to take into account edge parity earlier in the process to avoid wasting time searching branches which lead to reductions with edge parity which are later discarded.

Have you considered different reductions? I'd for example be interested in reduction to 3x3x4 (instead of to 3x3x3), which doesn't even have a parity issue.

 

[IAssemble]

Have you considered different reductions? I'd for example be interested in reduction to 3x3x4 (instead of to 3x3x3), which doesn't even have a parity issue.

I have thought about a number of different intermediate routes to get to a pure (without parity issues) 3x3x3. At the moment this is my main focus because it seems to be reasonably efficient and I already have a good 3x3x3 solver for the final phase ;-)

I have also thought about reducing to 2x2x2 (i.e. solving all 2x2x2 corner groups independent of their position). It is easy to implement an optimal solver for the final 2x2x2 phase, and this would also have no parity issues. But there is more work required to reduce to a 2x2x2 state since obviously there fewer positions of the 2x2x2 than a 3x3x3. I have some ideas about how the reduction phase(s) could be implemented but not actually tried any coding yet. Does anyone use this form of reduction on 4x4x4 or perhaps even bigger cubes? e.g. reduce 8x8x8 to 4x4x4 and then 2x2x2?!? The programmer in me asks if this is a way of designing an algorithm that is better then O(N^2)? Is this anything like the technique that was used to show large cubes could be solved in O(N^2/log(N))?

I haven't considered any other reductions.

Your idea of reduction to 3x3x4 is very interesting. Do you mean by no parity issue that the 3x3x4 can always be solved without having to split any of the 2x2x1 and 2x1x1 sub-blocks (or have I mis-understood what 3x3x4 means? I'm trying to visualize this!)

Does this mean you have an efficient (or even optimal?!?) solver for the final phase?

 

[cubernya]

I have thought about reducing a 4x4 to a 2x2. I tried it once, but it was terribly slow and inefficient, so I don't think it's worth it. If you can find a reasonable way to do this, then implement it

 

[ch_ts]

Reduction to 3x3x4 will result in people complaining "your 4x4x4 solutions are so long in qtm!" But I'm interested too...