Optimal parity fix maneuvers on the 4x4x4 cube

I recently investigated optimal reduction parity fixes on the 4x4x4 cube.

First some explanation of terms. A common strategy used in solving the 4x4x4 cube is to solve the center pieces, and then pair up the 12 pairs of edge pieces. The puzzle can then be solved like a 3x3x3 cube by turning only the face layers, except for two possible types of parity conditions that can't normally occur on the 3x3x3. These parity conditions are often called OLL parity and PLL parity (since whether or not these parity conditions are present typically isn't recognized until attempting to solve the last layer). Since the 4x4x4 is "reduced" to a pseudo-3x3x3 cube, this strategy is generally referred to as reduction.

OLL parity corresponds to an odd number of edge pairs being misoriented. A misoriented edge pair can be oriented by swapping the positions of the two edge pieces making up the pair. OLL parity is basically the result of the 24 edge pieces being in an odd permutation. An odd permutation of edge pieces can be converted to an even permutation by simply turning any inner layer (along with the adjacent face layer, if you like) a quarter-turn. Such a turn, of course, will break up four edge pairs, along with generating unsolved centers.

PLL parity corresponds to the 12 edge pairs being in an odd permutation (treating a pair as if it were a single cubie) with respect to their solved state, using the solved centers as a reference for the solved positions.

OLL parity and PLL parity are basically independent of each other. When both parities are present, this is generally called double parity.

PLL parity can be fixed with a relatively short maneuver. There are popular maneuvers for fixing OLL parity that contain 15 turns, including 10 turns that are half-turns, for a total of 25 quarter-turns. These standard maneuvers can flip one edge pair in place without disrupting the rest of the cube (ignoring permutation of center pieces within the same face) or swap two edge pairs while changing the orientation of one of the pairs.

For expressing maneuvers, I will use the classic notation here where inner layer turns are represented by lower case equivalents of the the letters used for the outer layer turns. Double-layer turns will be listed using both individual layer turns within parentheses. So turning the top two layers will be written as (Uu). This is sometimes now written as Uw, with the "w" meaning "wide" turn. Moving the two layers in between the L and R face layers in the same direction as R will be written as (l'r).

OLL parity: (Rr)2 B2 U2 l U2 r' U2 r U2 F2 r F2 l' B2 (Rr)2

Double parity: r2 B2 r' U2 r' U2 B2 r' B2 r B2 r' B2 r2 B2

(Some popular variants of these replace all inner layer turns with wide turns. Visible permutation effects still only affect only one layer.)

People have wondered if shorter maneuvers exist, especially if you are willing to allow permuting of corners and more of the edge pairs. Indeed it has been known that shorter maneuvers do exist, but it has been generally claimed that not much shorter maneuvers exist, and those that do would preserve less of the state of the cube, and generally not really be any better for speedsolving.

So anyway, I thought I would try to see if I could find out exactly what the optimal maneuvers for fixing OLL parity (or double parity) are, assuming reduction must be preserved. I first tried using a depth-first search. This turned out to be too slow to search quite deep enough to prove optimality. Thus, I ultimately used a bidirectional breadth-first search to find optimal maneuvers. Using a bidirectional search, I only needed to store positions to a depth of 6 to search an effective depth of 13. This turned out to be deep enough. (In fact, depth 13 maneuvers had been previously found.) I also note that there is a symmetry between the two search trees. So I actually only needed to generate one of the two trees. The depth-first search would be used to enumerate various maneuvers for each of the "mid-point positions" of the solutions found via bidirectional breadth-first search.

My approach for both searches used a minimum of information about the state of the puzzle. Corner cubies were ignored totally, since their state is irrelevant to whether or not a position is a "reduced" position. For the edges, I only cared about how the pairs were arranged on the cube, not where the individual pieces actually belong. Without knowing where the cubies belong, the parity of the edge pieces can not be determined, so I used a separate boolean variable to keep track of edge parity. This boolean would be toggled whenever applying a quarter-turn of an inner layer, or a wide quarter-turn of a face layer and adjacent inner layer. For the centers, I basically needed to know the color of the piece at each position. I note that there are 24 possible cube orientations giving 24 possible solved states for the centers. For the breadth-first search, I needed to minimize storage, so positions that were the same except for cube orientation, or equivalent by one of the 48 symmetries of the cube, were considered the same positions. I used a brute force approach of finding a representative for each symmetry class, so execution was rather slow, but good enough for the search to be completed within several days.

Results:

Using half-turns and quarter-turns:

The standard algorithm uses 15 turns and I knew that at least a 14-turn sequence was known. In fact, a 13-turn sequence was also known. My search yielded no maneuvers up to 12 turns, so 13 turns is, in fact, optimal. My search found 12 "distinct" positions (see above for what I defined a position to consist of) that were 6 moves from the solved state that could be part of an optimal sequence. The 12 same positions but with opposite edge parity are 6 moves away from the "solved except having edge parity" state. I refer to one set of 12 positions using the letters A-K and the other set with the same letter and an apostrophe. While I found 1695*9 such optimal maneuvers, I will simply give one from each category (and omit inverse cases), where each category is identified by the two midpoint positions. The full list of 1695 maneuvers (ignoring trivial substitutions for the first and last moves) is available at this link.

A -> A': (OLL parity)
(Uu) B' L2 B (Uu) B2 (Uu) R2 (Uu) R F2 R' (Uu)

A -> K' (OLL parity)
(Uu) B' L2 B (Uu) B2 u R2 (Uu) R' F2 R (Uu)

B -> B' (OLL parity)
(Uu) B L2 B' u B2 d B2 u B' R2 B (Uu)

B -> C' (OLL parity)
(Uu) B L2 B' u B2 (Uu) R2 d B R2 B' (Uu)

D -> D' (double parity)
(Uu) B2 (Uu) F2 (Uu)2 L2 (Uu) F2 (Uu)2 L2 (Uu) R2 (Uu)

D -> L' (double parity)
(Uu) B2 (Uu) F2 (Uu)2 L2 (Uu)' L2 (Uu)2 F2 (Uu)' R2 (Uu)

E -> F' (double parity)
(Uu)' R2 (Uu) F2 (Uu) R2 (Uu)' B2 (Uu) B2 (Uu)' L2 (Uu)

G -> J' (double parity)
(Uu) F2 L2 (Uu) L B' U B' (Uu)2 R2 (Uu)' R2 (Uu)2

H -> I' (double parity)
(Uu) F2 L2 (Uu) L' B D' B (Uu)2 R2 (Uu)' R2 (Uu)2

L -> L' (double parity)
(Uu)' R2 (Uu) F2 (Uu)2 L2 (Uu)' F2 (Uu)2 L2 (Uu) B2 (Uu)'

Using only quarter-turns as single moves:

In quarter-turns, the standard algorithm is 25 turns. There were maneuvers known to exist at least as short as 19 quarter-turns. My search found maneuvers as short as 15 quarter-turns! There were very few such maneuvers, though (and none shorter). I also note that these all require a double-layer turn of inner layers to be counted as a single turn. The list of optimal maneuvers (in quarter-turns) are:

{ (Uu), u, d } (lr') R D R' (Ff) f (ud') l' (u'd) (Ff) b (u'd) F { (Ll), l, r } (OLL parity)

{ (Uu), u, d } R' b (ud') d' L' b L u' b2 (Uu) (l'r) B' { (Uu), u, d } (double parity)

{ (Uu), u, d } (fb') L B' R u d f' u d L B' R (fb') { (Uu), u, d } (double parity)

{ (Uu), u, d } (fb') L' F R' u d f' u d L' F R' (fb') { (Uu), u, d } (double parity) 

The curly braces indicate you can choose any of the three moves within them.

My search indicates there are no other 15-quarter-turn maneuvers that fix OLL parity and preserve a state of reduction, except ones directly related to these maneuvers.