Parity problem or solutions to unsolvable situations


Some time ago I had an interesting e-mail discussion with one visitor of these web-pages. The topic of our conversation was the 4x4x4 Rubik's cube and inevitably we had to talk over the parity problem, which can occur on it. The questioner sighed during relative correspondence: "it's just a pity that the problem cannot be detected prior to solving of the last layer, so that one wouldn't have to scramble what has been already solved before". I answered in a way that there are several solving methods and some of them try to avoid a parity problem on a 4x4x4 Rubik's cube. It's time to investigate it in more detail!

Foreword

It would be best if the article was written by a mathematician. To express themselves, they use effective system: definition - theorem - lemma (auxiliary theorem) - proof. The advantage of it is the accuracy and explicitness of their statements.

On the other hand, they need to work with a plenty of quantifiers, operators, symbols, operations and who knows how much more other maddening stuff which can be hard to understand for normal people (yes indeed, I find a mathematician as an "abnormal folk", of course in the best meaning of that word). Since I am no mathematician, I have chosen more humane approach to describe a parity problem, even for a price of ambiguous and misleading, or even false statements.

Although we can use a notation for the 3x3x3 Rubik's cube in the following text, soon we would find out it is not so handy. It's because there are more piece types on a 4x4x4 Rubik's cube in comparison with a 3x3x3 Rubik's cube (see? I just made first false statement - both 3x3x3 and 4x4x4 cubes consist of 3 piece types in total), and a 5x5x5 cube is composed of more piece types than a 4x4x4 cube. As a result, the terminology in accordance with Fig. 1 on a page about the number of combinations for the NxNxN Rubik's cube will be used instead.

I cycle, you cycle, we cycle

In order to understand each other, it is useful to first introduce and define a few of mathematical terms. Don't panic now (you will have plenty of time for it later), the terms are related to the well-known puzzles to make it easier for you.

QTM - English acronym for "Quarter Turn Metric". In case of an NxNxN Rubik's cube it means that one move is equal to a layer rotation exactly by 90 degrees (U move, for instance). A layer rotation by 180 degrees counts as two moves in this metric (R2 = R R, for example). A layer rotation by 270 degrees = -90 degrees is taken as one move again (e.g. F3 (or F F2, or F F F) = F').

Orbit - orbit in which a certain type of puzzle pieces can appear. For example a 4x4x4 cube as a whole has one orbit of corners, one orbit of wing edges and one orbit of center pieces.

Permutation - mutually unambiguous (i.e. injective and onto (itself) - collectively so-called bijection) mapping of a finite set of elements.

We imagine the element as a puzzle piece. The meaning of a set of these pieces surprisingly depends on a mathematician's flexibility - in case of a 3x3x3 Rubik's cube, all 26 visible cubies making the puzzle may be understood by that (then we would talk about a puzzle permutation as a whole), but equally only the corners in its orbit may be understood by that as well (then we would talk about an orbit/corner-piece permutation). Therefore, in response to the legal moves, we can either perceive just mentioned 3x3x3 Rubik's cube as one set of 26 pieces (i.e. we may treat corners, centers and edges as the subsets, but may not talk about their permutations), or as three sets of 8, 6 and 12 pieces (i.e. we may distinguish corners, centers and edges as the separate puzzle pieces, and may talk about their permutations).

Apart from that, a set can be theoretically understood as a combination of edges + corners, for instance. We won't be thinking of such cases in the following because from a puzzle solving view those are impractical. Unless otherwise stated, we will understand a pieces-in-its-orbit permutation under the term permutation for the rest of the article.

If we arrange the elements of a set into a sequence {1,2,...,n} (n represents a number of the elements in a set), the permutation can be illustrated by a table

permutation

in which we see preimages (elements) of a set in the first row and their images (so-called values of permutation) in the last row. A permutation can be either even or odd. An odd permutation is composed of odd multiples of cycles of length 2 (a cycle of length 2 (it is a cycle of even length) will be further denoted as a 2-cycle) and even permutation is composed of even multiples of 2-cycles (more precisely - using sgn p - it is formulated below). It is possible to write down every permutation as a product of transpositions (p = T1◦...◦Tn).

transposition

Transposition Tp is a permutation which interchanges some element i with another element j (for i < j) and cubers can imagine it as a swap of only two pieces of the same type. Every transposition is an odd permutation. In other words, a transposition equals a 2-cycle.

N-cycle - permutation which cycles an order of values of permutation.

n-cycle
Tab. 2

In relation to a 3x3x3 Rubik's cube, it deals with a simultaneous displacement of N pieces (2 or more) of the same type (i.e. corners, centers or edges) on condition that if the algorithm generating an N-cycle is executed exactly N-times in a row, the cube will return to its original configuration before an execution of this algorithm.

Let's take a look at some examples of N-cycles. On the left we see one 3-cycle of edges on a 3x3x3 Rubik's cube when viewed from above, on the right there is one 3-cycle of corners for the same puzzle and projection.

3-cycle

On the next pair of pictures we can observe 2 2-cycles of edges on the left and 2 2-cycles of corners on the right.

2-2-cycles

Last example illustrates 1 2-cycle of edges and at the same time 1 2-cycle of corners.

1-2-cycle

It turns out that a number of possible even permutations equals a number of odd permutations for mutually distinguishable pieces on an NxNxN Rubik's cube (as well as higher spatial dimension cubes). If we keep talking about a 3x3x3 Rubik's cube, then e.g. F move is an odd permutation of edges and at the same time an odd permutation of corners and at the same time an even permutation of centers - the proof you'll get soon.

Similarly to odd number + odd number = even number, also odd multiple of cycles of even length (e.g. 2-cycles) in a given piece orbit + odd multiple of cycles of even length (e.g. 2-cycles) in the very same piece orbit = even multiple of cycles of even length (e.g. 2-cycles) in the coequal piece orbit (hence it is an even permutation). It's not a surprise that even multiple of cycles of even length in a given piece orbit + even multiple of cycles of even length in the very same piece orbit = even multiple of cycles of even length in the coequal piece orbit, or that odd multiple of cycles of even length in a given piece orbit + even multiple of cycles of even length in the very same piece orbit = odd multiple of cycles of even length in the coequal piece orbit (hence it is an odd permutation).

Therefore, we can imagine the pieces in particular orbits on a 3x3x3 cube at any stage of solving to be in either even or odd permutation (hereafter denoted as an even or odd puzzle status). We are talking about an odd puzzle status if at least one its piece orbit is in odd permutation. If a permutation of all piece orbits on the puzzle is even, we are talking about an even puzzle status. An idea of a 3x3x3 Rubik's cube perceived this way directly relates its corner orbit + edge orbit + center orbit (possibly understood as the sets in a permutation definition) and the pieces appearing in them (i.e. the elements in a permutation definition). Then the mapping (in a permutation definition) embodies the executed moves on this puzzle.

What is a parity problem?

The term parity problem (or puzzle status) is not defined in mathematics. Consequently, the mathematicians (at least those at FMP CUNI and FNSPE CTU) solely operate with the permutations in this context. In order to tell whether the permutation is odd or even, they are introducing the term sign (signature, signum) of permutation, sgn p. It only takes values of -1 and +1 because by definition, sgn p = (-1)k (k represents a number of transpositions Ti which are required to compose the permutation), or sgn p = (-1)number of cycles of even length, or simply (-1)number of 2-cycles. If sgn p = +1, we say that p is an even permutation, otherwise it is odd. If we, as the cubers, accept a conception of an odd puzzle status, then we can informally write: parity problem = odd puzzle status = a permutation of at least one piece orbit is odd. Thus a parity problem isn't a problem in a true sense of the word, instead it is a totally natural and completely common puzzle state / configuration. Although there is no single valid reason to introduce another synonym / equivalent to the term "odd permutation" (such as a parity problem or odd puzzle status, for example), the cubers generally do so. Unfortunately, they often aren't taking into consideration the presumptions, whose fulfillment is conditioned to further usage of this term.

From a mathematical analysis point of view it is convenient to introduce another exclusively-cuber term at this moment: a parity state of the puzzle. For example on the NxNxN Supercube there are

parity states

parity states on condition that for odd cubes (N is odd) we consider a so-called fixed centers model and for even cubes, which don't have fixed centers, we think of a so-called fixed corner model. To get an idea how a fixed corner model works, see a page about a number of combinations for an NxNxN Rubik's cube. Any middle layer moves, as well as any rotation of the cube as a whole, are excluded in a fixed centers model. Notice that there are no square brackets in an exponent of the expression above, meaning that it is a floor function. Therefore there are 2(floor (N/2)) parity states if we abide that mentioned condition.

Parity states are characterizing both puzzle statuses - even as well as odd. On an NxNxN Supercube, each outer layer move in accordance with QTM toggles, among others, a permutation of corners, and each inner layer move (except for a middle layer moves in case of odd cubes) in accordance with QTM toggles, among others, a permutation of wing edges. These findings were elegantly formulated by Christopher Mowla in his C(n,w,c) function. Later it will be briefly shown (via specific puzzle examinations) what one can deduce from it.

A little bit of practice won't hurt

First, let's turn our attention to the 2x2x2 Rubik's cube. It consists of 8 pieces of the same type (corners). In a solved state we can assign the numbers 1-8 to the particular corners; e.g. numbers 1-4 to four corners in upper layer and numbers 5-8 to the remaining corners in lower layer. By that we will obtain a sequence 1-2-3-4-5-6-7-8 (which corresponds with an upper row (preimages) in Tab. 2 stated above). What will happen if we execute a U' move?

A corner no. 1 will move to the place where was originally a corner no. 4. That one will move to the place where was initially a corner no. 3. That one will move to the place where was, at first, a corner no. 2. And finally a corner no. 2 will move to the place where was originally a corner no. 1. The remaining corners in a lower layer will remain at their initial positions, thus we will obtain a sequence 2-3-4-1-5-6-7-8 (which corresponds with a lower row (images) in Tab. 2 stated above). Since 4 pieces were cycled, in accordance with an N-cycle definition we talk about 1 4-cycle (one four-cycle). Our task is to determine whether it is an even or odd permutation of corners, an even or odd puzzle status, if you like. In other words, we are going to count a number of 2-cycles we need to make in order to get from a lower row sequence of Tab. 2 back to the sequence stated in an upper row of that table.

4-cycle

As 1 2-cycle we understand a swap of any two numbers (in our case it means a swap of any two corners on an 2x2x2 Rubik's cube). So we can first swap the numbers 1 and 2, which will lead to a sequence 1-3-4-2-5-6-7-8. By second 2-cycle we will interchange the numbers 2 and 3, thus getting a sequence 1-2-4-3-5-6-7-8. By third 2-cycle we will swap corners under the numbers 3 and 4, so that an original (solved) puzzle state is obtained due to a resulting sequence 1-2-3-4-5-6-7-8. On the basis of just mentioned procedure one can say that a U' move on a 2x2x2 Rubik's cube creates an odd permutation (1 4-cycle) of corners (an odd puzzle status, if you like) because 3 2-cycles are required to compose it and a number three belongs to odd numbers.

Logically, it implies that 2 4-cycles are an even permutation because a minimum of 2·3 = 6 2-cycles are required to compose them (a number six belongs to even numbers). If you don't believe it, go ahead and simulate a following situation on a 3x3x3 Rubik's cube: execute L and R moves. Now try to determine a permutation of edges only (because centers didn't move anywhere and corners are in another orbit - thus following our interpretation of the term permutation, they are in entirely different set of elements, so ignore them in this example model for now. Don't be confused, however - L and R moves otherwise result in 2 4-cycles of corners). Now, if you label the edges in a left layer by numbers 1-4, the edges in a right layer by numbers 5-8 and finally the edges in a middle layer by numbers 9-12, from a solved state expressed by a sequence 1-2-3-4-5-6-7-8-9-10-11-12 you should get a sequence 4-1-2-3-6-7-8-5-9-10-11-12 after applying L and R moves.

2-4-cycles

Let's define a solved puzzle (a solved puzzle state) as a configuration whose characteristic is exactly one mutual arrangement of all puzzle pieces and at the same time it is necessary to apply 0 2-cycles to them. A status of solved puzzle is even.

Note that a solved puzzle state (or a permutation itself) doesn't take pieces orientation into account at all.

Terminology agreement: with respect to the aim of the puzzle, we will apprehend an orientation of all puzzle pieces in a solved puzzle state as correct. The meaning of wrong and correct piece orientation is intuitive, hence it won't be further explained.

A parity problem of chosen combinatorial puzzles

On a 2x2x2 Rubik's cube, these moves are applicable: one move in accordance with QTM (e.g. U), two moves according to QTM (R2, for example), a rotation of the puzzle as a whole (x, for instance) and a double puzzle rotation (y2, for instance). From a solved state, one move in accordance with QTM toggles a permutation of corners from being even to being odd, because 1 4-cycle is done and it can be composed of 3 2-cycles. Two moves in accordance with QTM don't toggle a corner permutation because it is necessary to do an even number of 2-cycles to solve the puzzle. A double move can also be perceived as two "single" moves that are executed straightway consecutively (from a sequence 1-2-3-4-5-6-7-8 will become a sequence 3-4-1-2-5-6-7-8) and since a "single" move toggles a permutation of corners, after its first execution a permutation of these pieces will be odd and after further execution will be, on contrary, even (because odd + odd = even, in other words 3+3 = 2·3 = 6).

You can easily see for yourself that a puzzle rotation doesn't influence its permutation. If you do a rotational move (e.g. z), from an initial solved state (that is characterized by 0 2-cycles), 0 2-cycles will be still needed to do in order to solve the puzzle. Analogically, if you do, from a solved state, 1 move with a subsequent rotation of the puzzle, it will still be necessary to do 1 move again in order to solve the puzzle. Based on this hypothesis we can claim that both single and double puzzle rotation doesn't affect its permutation.

Therefore, in reality it is only necessary to examine one move in accordance with QTM on a 2x2x2 Rubik's cube, simply because all the other moves (double move and rotations) can be combined by means of the single ones.

Since every single move toggles a corner permutation from being even to being odd (or from being odd to being even), and we also know that a permutation of corners is even in a solved puzzle state, it is not possible to solve a 2x2x2 Rubik's cube that has been scrambled by an even number of moves in accordance with QTM by an odd number of moves according to QTM. To swap only two corners (i.e. 1 2-cycle), we will always need an odd number of moves in accordance with QTM. Why? Because we will get from an odd permutation of corners (e.g. a state in which it is necessary to swap only two corners) to an even permutation of corners (e.g. a solved state) only using an odd number of moves according to QTM. Naturally, a 2x2x2 Rubik's cube scrambled by an even number of moves in accordance with QTM is not solvable by applying an odd number of moves according to QTM, because from an even corner permutation (a permutation after a puzzle-scramble is meant) we will not reach an even corner permutation (a solved state is meant) using an odd number of moves in accordance with QTM.

So in case of a 2x2x2 Rubik's cube we talk about a parity problem not only when we require to swap only two corners (which is an exemplary demonstration of transposition, i.e. an odd permutation) - as it can be seen for example after an execution of algorithm R2 U' R2 U R2 U D' R2 U R2 U' R2 D. Equally, we talk about a parity problem if there is only one move (according to QTM) left from a solved puzzle state. Quite frankly, on a 2x2x2 Rubik's cube there are 3 674 160 / 2 parity problems, or there are 1 837 080 configurations forming an odd puzzle status. All of them are summarized in the C(n,w,c) function by an expression C(2,0,1). On contrast, the rest 1 837 080 configurations forming an even puzzle status can be expressed as C(2,0,0). For a 2x2x2 Rubik's cube we will obtain overall 2 parity states, which is in good agreement with a formula 2(floor (N/2)) (where N is a number of layers).

Consider a configuration in which 1 move according to QTM is left to obtain a solved puzzle state. Then a puzzle permutation is odd (if 8 pieces are meant as a set in a permutation definition) and a puzzle status is odd as well (already shown before).

Let's have a look at the 3x3x3 Rubik's cube now. Due to the fact it is an odd cube (N = odd number), a middle layer moves as well as rotations as a whole are, in conjunction with a parity states condition, forbidden. Thus we need to examine the remaining moves: 1 move of outer layer in accordance with QTM and a double move of outer layer. It is easy to see that a double move is a combination of two single moves, so we reach a conclusion that 1 move of outer layer according to QTM represents the only possible type of move on a 3x3x3 cube.

From a solved cube state it results in an odd permutation of corners (1 4-cycle; can be composed of 3 2-cycles) and simultaneously an odd permutation of edges (also 1 4-cycle; can be composed of 3 2-cycles) - so a puzzle status is toggled with each of this move applied. Since centers moved nowhere, they won't be considered in the upcoming.

A double move of outer layer (two moves according to QTM) doesn't toggle a puzzle status because 2·(either even or odd multiple of cycles of even length) = even puzzle status (we can talk about an even puzzle status here because a corner permutation and an edge permutation are always the same).

We will get similar conclusions for a 3x3x3 Rubik's cube as for a 2x2x2 cube: in a solved state a permutation of both corners and edges is even (it is not needed to consider a permutation of centers into our fixed centers model). Since each move of outer layer in accordance with QTM (which corresponds to the only possible type of move on the puzzle) toggles simultaneously a permutation of corners and edges either from being even to being odd or from being odd to being even (compare with each single move on a 2x2x2 Rubik's cube and its corners), it is not doable to solve a 3x3x3 Rubik's cube that has been scrambled by an odd number of moves of outer layers in accordance with QTM (which would lead to an odd permutation of scrambled edges as well as odd permutation of scrambled corners), using an even number of moves of outer layers according to QTM (and vice versa). It means that a permutation of corners will be the same as a permutation of edges after each move of outer layer applied in accordance with QTM, so if we hypothetically swap only two edges, also two corners has to be swapped and to get this configuration, always an odd number of moves of outer layers according to QTM will be needed to apply. Why is that so? Because from an odd permutation of both edges and corners (i.e. an odd puzzle status) we will obtain an even permutation of both edges and corners (i.e. an even puzzle status) only using an odd number of moves of outer layers in accordance with QTM. Mechanical / manual swap of only 2 edges or corners (from initially even puzzle status it would become an odd puzzle status) would lead to a puzzle-unsolvability (because it is not possible to apply a move that toggles either only a permutation of edges or only a permutation of corners independently - as it has been mentioned several times before, one move of outer layer according to QTM toggles a permutation of corners as well as a permutation of edges simultaneously).

There are 43 252 003 274 489 856 000 / 2 positions on a 3x3x3 Rubik's cube that we call a parity problem (an odd puzzle status). The very same number characterizes an even puzzle status, too. That being said, we distinguish overall 2 parity states expressed as C(3,0,0) and C(3,0,1), which is in agreement with earlier mentioned formula 2(floor (N/2)).

Consider a configuration in which 1 move according to QTM is left to obtain a solved puzzle state. Then a puzzle permutation is even, because 1 4-cycle + 1 4-cycle = 2 4-cycles (if 26 pieces are meant as a set in a permutation definition) and a puzzle status is, on contrary, odd, because 1 4-cycle + 1 4-cycle ≠ 2 4-cycle in this case (already shown before). We clearly see that it is a must to express precisely what is meant by a permutation, a set of elements, if you like. It is the only way how to prevent a possible misunderstanding, because what seems to be a contradiction at first sight is, in fact, in good harmony.

Rumours say that Sam Loyd got rich when he applied a principle of even and odd permutation on the Fifteen puzzle. He deliberately swapped two numbered pieces on it - so from an odd permutation he made an even permutation. Then he offered a high reward to anyone who would solve the puzzle but it was unsolvable because of that "permutation change" (because each move on this puzzle creates an even permutation of numbered pieces when keeping a blank square at down right).

Knowledge gained until now can be even used elsewhere, for example in solving a 3x3x3 Rubik's cube blindfolded. On that linked page, both corners and edges are being solved using 2-cycles. If we "solve" all edges using an odd multiple of 2-cycles (therefore we would meet a parity problem), we will also solve all corners by means of an odd multiple of 2-cycles, thus we will solve the puzzle using an odd number of moves of outer layers in total, according to QTM. I haven't tested it experimentally though, only a logical reasoning in which one move of outer layer in accordance with QTM is done have brought me to this conclusion.

Let's think of the Void cube now - an ordinary 3x3x3 Rubik's cube with black stickers glued on centers (so that these pieces would be identical, i.e. mutually indistinguishable) is sufficient for us.

Restickering of centers plays an important role because for a classical Rubik's cube 3x3x3 we can claim that there is 24 / 24 = 1 solved puzzle state (in which both corners and edges are related to the centers), whereas in case of a Void cube we will find (24/24)·4·3 = 12 such solved states (since even if a fixed centers model is considered, corners and edges cannot be related to anything - one solved state differs from another one by the moves R2 L2 (U2 R2)·3 (F2 R2)·3 (B2 R2)·3 (U2 R2)·3), for instance). While on a 3x3x3 Rubik's cube we understand an M move as L' R x' moves, the very same M move could be wrongly interpreted as only L' R moves in case of a Void cube. By that we would wrongly admitted that the centers in the M-ring are not being moved by applying an M move (for a 3x3x3 Rubik's cube this is not an issue because of a rotation of the puzzle as a whole after the L' R moves, respectively because of a literal M move execution-disabling - see the parity states above). But a real Void cube doesn't even have centers, so we cannot really talk about their fixation. As a result, a <U, D, R, L, F, B> model, in which only U, D, R, L, F and B moves are allowed to apply, is introduced. Technically speaking, for both Void cube and 3x3x3 (as well as 2x2x2) cube only a <U, D, R, L, F> set is sufficient because the sixth possible move can be combined by means of the previous five. Since centers on a classical 3x3x3 Rubik's cube are being cycled by an M move (L' R x' moves, if you like) for sure, a situation of seemingly only two swapped edges - corners are supposed to be solved - cannot occur on it (due to the distinguishable centers). However, on a Void cube this configuration can occur (due to the indistinguishable centers).

If we put a Void cube into the C(n,w,c) function while preserving the same properties that we applied to a 3x3x3 Rubik's cube (fixed centers model to be specific), we will come to a conclusion there are (43 252 003 274 489 856 000 / 2) / 12 positions that we call an even puzzle status (seemingly only two edges swap belongs here as well), and the same number of configurations is formed by an odd puzzle status.

Same mathematical laws which apply to a classical 3x3x3 Rubik's cube apply even to the Megaminx. A Void cube is related to a 3x3x3 cube as a Megaminx to the Holey Megaminx (eventually a Megaminx without distinguishable centers). It raises a question whether there is also a parity problem on a Holey megaminx, similarly to a Void cube?

First, let's imagine an analogy of a Rubik's cube 3x3x3 and its one outer layer move execution in accordance with QTM (instead of 90° on a Rubik's cube, the layer is rotated by 72°) for a Megaminx or Holey megaminx. By that we will obtain an even permutation of corners (1 5-cycle; can be composed by means of 4 2-cycles) and simultaneously an even permutation of edges (1 5-cycle; can be composed of 4 2-cycles) - i.e. an even puzzle status. It implies that a parity problem can not occur on a Holey megaminx (nor a Megaminx) because similarly to a 3x3x3 Rubik's cube, there is no move which would toggle a permutation of one piece type independently on the other piece types (in a fixed centers model), so a puzzle status is always even. If you disbelieve, go ahead and try to determine a puzzle status after an application of a double, triple or quadruple move.

In case of the 3x3x3 Supercube, unlike a 3x3x3 Rubik's cube, a solved state depends on the orientation of centers. Since a permutation definition says nothing about an orientation of pieces, all of that what has been said for a 3x3x3 Rubik's cube applies also to a Supercube.

In addition, one move on a 3x3x3 Supercube according to QTM orients a center piece by one multiple (it means an odd number) of 90°. Therefore, each next move of outer layer in accordance with QTM will toggle a center orientation from an even multiple of 90° to an odd multiple of 90° (or vice versa). Thus if we have a scrambled puzzle state with an odd permutation of corners, a permutation of edges is odd as well, and centers are oriented by an odd multiple of 90°.

In a solved puzzle state a permutation of corners (as well as a permutation of edges) will be even, so an orientation of centers will be possible to express by an even multiple of 90°. This practically means that in a dependence on used solving method, we can register following simplified situations: 1) one center oriented by 180° or two centers oriented by 90° clockwise and/or counter-clockwise, 2) one center oriented by 90° clockwise and at the same time one center oriented by 90° counter-clockwise. Nevertheless, we can't get a puzzle configuration in which only one center would be oriented by 90° (because both corner and edge permutation would be odd in a solved puzzle state, which is a contradiction).

While a situation 2) can be solved using a commutator in the form of A B A' B', a situation 1) cannot seemingly be solved this way (that's because a commutator in the form of A B A' B' is not determined to orient only one piece). Instead of rotating a single center by 180°, it is necessary to suitably rotate the rest of the layer around this center (e.g. by a commutator (L R U2 L' R') U (R L U2' R' L') U' for oriented center situated in upper layer), and then arrange the layer (using a U2 move).

Last discussed puzzle prior to the 4x4x4 Rubik's cube (to which all of you are looking forward so much) will be the Square-1. It is a standalone chapter. It has been proven that if the upper and lower layers have a shape of a square (and also a permutation of corners is equal to a permutation of edges), the puzzle can be solved without a need to leave this shape of both layers. If we get to the square shape of both layers with the same permutation of edges and corners, we can partly compare the puzzle to a 3x3x3 Rubik's cube. Each turn which preserves this shape (a middle layer is not considered) always creates 2 2-cycles of corners and simultaneously 2 2-cycles of edges (which is an analogy to a R2 move on a 3x3x3 cube). We already know that a parity problem on a 3x3x3 cube is being solved using one outer layer move and the same technique can be used even for a Square-1. By that we will achieve unchanging (i.e. an even) puzzle status over the solve (at the end of each step of the solve, if you like).

Besides the square shapes of upper and lower layers with equal permutation of corners and edges, a case in which permutations of these pieces will be different for the same shape can occur. This situation requires to leave square shape of both layers, because ultimately it will be needed to do an odd number of 2-cycles of either edges or corners and it can't be reached in the square shape of both layers - similarly to a 3x3x3 Rubik's cube (for which a permutation of edges cannot generally be different from a permutation of corners).

So, in order to determine an eventual equality of edge and corner permutations at the beginning of the solve on a Square-1, we would have to be able to determine a permutation of both corners and edges in any shape of both layers (in which the pieces can appear). However, this alone is not sufficient because a permutation of both edges and corners can toggle when getting from any shape of both layers to the square shape.

Good thing is you can actually proceed in the opposite way. Let's have, at first, a solved puzzle state (that means the square shape of both layers, too). Now it remains to convert the puzzle into a suitable (reference) shape of both layers from which it is easily possible to toggle a permutation of only corners or only edges. One such reference shape is shown on the picture below (the shape of upper layer when viewed from above looks like the shape of lower layer viewed from below). Let's call an arrangement of particular corners and edges in the reference shape as the reference state (the ref. state is related to a solved puzzle state, from which it is created using a few moves).

square-1

If we meet the reference shape during a real solve, we must compare by how many 2-cycles of edges and corners we could get to an identical arrangement of corners and edges as in the reference state. If both numbers (for corners and edges) are even or odd, there will be no need to leave the square shape of both layers (on condition of reaching the square shape of both layers by applying the inverse moves, which led from a solved state to the reference shape of the puzzle). If a corner permutation and an edge permutation are different (in comparison with an arrangement of both piece types in the ref. shape) in that shape of layers, there will be necessary to either leave the square shape during the solve (on condition of reaching the square shape of both layers by applying the inverse moves, which led to the reference shape of the puzzle) or solve a parity problem (in this context an equality of a permutation of corners and a permutation of edges is meant) directly in this shape (or in another shape which will lead to the square shape of both layers). On the picture above it can be done by a turning of the right part of the puzzle because it does only 3 2-cycles of corners, so from a different corner and edge permutations would become equal permutations.

Any reference shape can be chosen - see e.g. a page about a Square-1, section parity problem solution to be more precise. First seven moves will bring us to the reference shape in that linked tutorial, by eighth move 1 6-cycle of corners is being done, which is an odd permutation of corners, thus we will obtain the same permutation as a permutation of edges (a permutation of edges in the square shape (a shape identical to the reference one, if you like) of both layers was odd, whereas a permutation of corners was even).

Outlined procedure for a solution to parity problem (in this context an obtaining of the same corner permutation and edge permutation is meant) at the beginning of the solve is not, however, useful for a speedcubing, due to the heavy time-consuming case recognition of an even or odd permutation of edges and corners in the reference shape (we have to compare a real arrangement of both piece types with the reference state, and make appropriate correction to a permutation of one piece type accordingly). We can, of course, choose more reference states (in order to not passing through always the one shape of both layers, which would lead to move as well as time losses), nevertheless by doing so the greater memory demands are placed on a solver (instead of memorizing the appearance of edges and corners in one shape, a solver would have to memorize the appearance of these pieces in more shapes of both layers).

On the other hand, if the solver remembers all reference states in all reference shapes (there are people who can already do this), a comparison of real arrangement of corners and edges on a scrambled puzzle with its reference state is extremely useful for speedsolving because a solution to parity problem (obtaining of the same corner permutation and edge permutation is meant in this context) can be planned during an inspection time of 15 seconds prior to solving of puzzle itself. It leads to saving of moves, hence saving of time. Plus a case-recognition time is not included here (compared to parity problem solution at the end of the solve).

Those who can solve a Rubik's cube blindfolded on the basis of these web-pages can imagine a parity problem solution in case of a Square-1 (in this context an obtaining of the same corner permutation and edge permutation is meant) at the beginning of the solve as something like a memorization of a scrambled cube, except that the reference shape of a Square-1 represents a scrambled cube before memorizing and an arrangement of pieces which is compared to the reference shape of a Square-1 represents a scrambled cube after its memorization.

If you haven't been confused so far, I have a special point for you to conclude a Square-1 examination :-). Besides two pieces in a middle layer, the puzzle consists of 8 corners and 8 edges. Despite of it, it is also possible to perceive one corner as two edges glued together. Then it can be said that apart from two pieces in a middle layer, the puzzle is composed of only 24 edges. If we accept this conception, then one move of a layer by 30° toggles a puzzle status (a permutation of edges, if you like) because 1 12-cycle is done. On contrary, a swap of 2 corners (which don't exist in our train of thought) is an even permutation, because it is possible to compose it using 2 2-cycles. If we treat corners as individual pieces, we will reach exactly opposite conclusion - an even permutation is a move of one layer by 30°, while an odd permutation is a swap of 2 corners. Paradoxically, one approach allows (on conditions mentioned above) to solve a parity problem without a need of leaving the square shape of both layers (when we imagine a corner as two pieces), whereas the other approach requires to leave the square shape of layers (when we perceive a corner as a single piece).

Comprehensive analysis (in which the square shape of both layers would not be required to preserve during a solving process) of the puzzle, including its 90 unique shapes (excluding a middle layer), is beyond the scope of this article.

Analysis of the 4x4x4 Rubik's cube and a little bit of C(n,w,c) function

Recall that a permutation is merely the mapping of a set of n elements with certain properties. One of them is a finite set of elements - related to a Rubik's cube, it is about a finite number of puzzle pieces. Another property is mutually unambiguous relationship between the preimages and images of this set of elements - related to an NxNxN Rubik's cube, it is about a distinctiveness of pieces. Since the real puzzle is always composed of a finite number of pieces undoubtedly, let's discuss the second one of just mentioned points for a moment.

As an example, let's consider a "solved" state of a 4x4x4 Rubik's cube (quotes will be explained in the following paragraph). We defined earlier that it is characterized by an even puzzle status. Now, if we manually swap two center pieces of the same color, the puzzle will still look as it was, even though a permutation of centers should be odd - which is however in contradiction with the definition of a solved puzzle state. Therefore, it doesn't make any sense to talk about a permutation of pieces (thus neither N-cycles of these pieces) which are identical.

Another problem with center pieces of a 4x4x4 Rubik's cube is that by definition, we can't actually solve them at all - i.e. we can't place all of them always into the same mutual arrangement. Moreover, there wouldn't be only one "solved" puzzle state (as required by definition), but 4!6 of them (because the first center piece belonging to the given face can be placed in there by 4 ways, a second center piece of the same color can be placed towards the first one by one out of 3 remaining ways, a third center piece can occupy one out of 2 remaining places and finally a fourth center piece belonging to the same face will take 1 remaining place - hence 4! for one face, but there are 6 of them in total) = 246 = 191 102 976 such "solved" states. We will obtain one half of this number by applying allowed (legal) moves on a cube (i.e. it will be needed to execute an even multiple of two center pieces swaps) and the other half would be obtained by executing of one non-allowed (illegal) move (i.e. by only two center pieces swap, for example due to the so-called POP, when integrity of the cube is disrupted - therefore we could swap two center pieces during a cube re-assembling and continue in solving).

Anyway, a 4x4x4 Rubik's cube (generally NxNxN for N > 3) is unsolvable because its solved state is not sufficiently defined due to the undefined permutation of indistinguishable center pieces. Instead of solving, we are only grouping these pieces together, and after it we are solving the corners and edges (because these are already mutually distinguishable).

It's probably not necessary to convince you that both corners and middle edges cannot be interchanged. Let's watch how it is in case of the wing edges.

orientation and permutation of edges

On the left part of a picture we see a white-green wing edge no. 1 and no. 2. We won't find a way to orient reversely (flip) an edge no. 1 at its current position (and the same applies to an edge no. 2 as well). However, if we swap both edges, a configuration expressed by the right part of a picture will be obtained. Even there we can't flip the edges no. 1 and 2. By that it is shown the wing edges can be swapped but they can't be oriented (hence they are distinguishable).

It does make sense to talk about a puzzle permutation on a 2x2x2 and 3x3x3 Rubik's cube because all their pieces in all orbits are mutually distinguishable. To continue in defining a permutation unambiguously, let's replace a Rubik's cube NxNxN (where N > 3) by a Supercube NxNxN. By doing so, the unambiguity of all puzzle pieces is guaranteed.

Considering a so-called fixed corner model, only the corners, middle edges and fixed centers can be swapped as well as flipped on an NxNxN Supercube. For the rest of the piece types (X-centers, + centers, oblique centers and wing edges) only the term permutation is introduced, since by a legal (allowed) moves it is not possible to place the same piece at the same position with its different orientation (see the previous picture).

On a 4x4x4 Supercube, one move of outer layer in accordance with QTM creates an odd permutation of corners (1 4-cycle) and at the same time an odd permutation of center pieces (1 4-cycle) and at the same time an even permutation of wing edges (2 4-cycles). Therefore, a puzzle status is odd after this move is being made. After its double move (R2, for instance), it will be even (2· odd or even multiple of cycles of even length = even permutation).

parity rubiks cube 4x4x4

On a 4x4x4 Supercube, one move of inner layer creates an odd permutation of wing edges (1 4-cycle) and at the same time an even permutation of center pieces (2 4-cycles; in first of them the pieces denoted as 1, 2, 3, 4 on the right side of the previous picture are being cycled and in second of them the pieces denoted as 5, 6, 7, 8 are being cycled). Therefore, a puzzle status is odd after this move is being made. After its double move (r2, for example), it will be even (2· odd or even multiple of cycles of even length = even permutation). See a tutorial on how to solve a 4x4x4 Rubik's cube on these web-pages to understand the meaning of used lower case letters.

Christopher's C(n,w,c) function is a mathematical tool which serves for an examination and categorization of permutations of all piece orbits into 2(floor (N/2)) parity states on an NxNxN Supercube. Input parameter n indicates a number of layers of the puzzle, w represents a number of orbits of wing edges in an odd permutation and finally c specifies a permutation of corners (c = 0 for an even permutation of corners, c = 1 for an odd permutation of corners). Even puzzle statuses are characterized by the expression C(n,0,0), other expression means an odd puzzle status. Thus in case of a 4x4x4 Supercube we will get 4 parity states, namely:

  • C(4,0,0) - e.g. a solved puzzle
  • C(4,0,1) - e.g. a solved puzzle after an R move
  • C(4,1,0) - e.g. a solved puzzle after an r move
  • C(4,1,1) - e.g. a solved puzzle after the R r moves

Starting by a 6x6x6 Supercube, we will get several "duplicate" parity states which are expressed by the same input form - e.g. C(6,1,0) for an r move as well as 2r move, or C(6,1,1) for the r U moves as well as 2r U moves. However, we don't need to take duplicate parity states into account from the number of orbits of pieces in even and odd permutations point of view. In other words, if the input form of the C(n,w,c) function is identical, its output will be identical as well.

It means that if we don't distinguish orbits of wing edges on the input (we only put in a number of orbits of these pieces in an odd permutation), we won't get distinguished orbits of X-centers, + centers and oblique centers on the output (we will only get a number of X-centers, + centers and oblique centers in an odd permutation). But in case we would distinguish orbits of wing edges on the input (there are two such different orbits on a 6x6x6 Supercube, for example), on the output we would get not only an information about how many orbits of center pieces are in an odd permutation, but also a specific list of these different orbits.

c(n,w,c)-function

Input and output parameters of the C(n,w,c) function are reflecting all piece types of an NxNxN Supercube except for the middle edges and fixed centers. These occur only on an odd Supercube (N is odd). A so-called fixed centers model is considered for an odd N, on whose basis it can be said that a permutation of middle edges is always the same as a permutation of corners (assuming allowed/legal puzzle moves), and a permutation of fixed centers is always even. Therefore, without a loss of generality, we can assign a prescription of c · n mod 2 to middle edges, as well as a constant value of 0 to fixed centers.

To make this site vital and fresh, interactive animated simulators will be used from now on in order to increase topic's clarity. On the left below we see a configuration in which it remains to apply 2 2-cycles of wing edges to get a solved state. Conversely, on the right below we will solve the puzzle using only one two-cycle of wing edges (directions of the arrows can be neglected, they are only pointing out solved center pieces).

No parity problem
Even permutation of wing edges
Parity problem
Odd permutation of wing edges

Let's think of the following picture as a Rubik's cube at first, and then as a Supercube. So ignore the numbers at first - a Rubik's cube doesn't work with them at all.

no parity problem

By doing so, we would obtain seemingly only two center pieces swap. But it is impossible configuration in case of a Supercube because not only the pieces no. 1 and 3 would be unsolved, but also the piece no. 2 would be unsolved (it comes directly from the C(n,x,c) function - see a functional prescription for X-centers when a permutation of corners is odd). As a result, we will do 1 3-cycle instead of 1 2-cycle in that given configuration (from a form 2-3-1 we want to get 1-2-3), so it is not a parity problem. For both puzzles we can practically solve mentioned configuration by a commutator (r' u r) U (r' u' r) U'.

Dual concept of a parity problem: mathematician vs. speedcuber

In the 80's of the last century an interesting phenomenon has occurred when a 4x4x4 Rubik's cube has been released to the market. Early solvers-pioneers, who have been trying to solve this yet unknown puzzle, have soon used also a method for a 3x3x3 Rubik's cube (which has already been several years available), only modified to a 4x4x4 cube - i.e. grouping of center pieces together, pairing up of wing edges and then using a reduction to already mentioned 3x3x3 cube (see a tutorial on the 4x4x4 Rubik's cube, for example). For the last step (a reduction) they have been assuming that the puzzle will be solvable only by the moves which are permitted in a solving of a 3x3x3 cube. Sadly, that assumption turned out to be wrong, as they figured out soon.

Two configurations, unknown from a 3x3x3 cube, have appeared. These mysterious states have been called a parity problem. The term got familiar and spread out spontaneously, hence we can meet it in this context up to the present day - especially in a speedcubing community. From a 3x3x3 cube point of view, it is only one flipped edge and only two swapped edges.

Parity problem
(so-called OLL parity)
Odd permutation of wing edges
and even permutation of corners
No parity problem
(so-called PLL parity)
Even permutation of wing edges
and even permutation of corners

If you are objecting that another impossible configuration is only two corners swap (or a swap of two adjacent edges instead of diagonal ones which are shown on the right hand side simulator), go back to the analysis of a parity problem on a 3x3x3 Rubik's cube - these configurations, in fact, are equivalent on it.

Over the time, a need to verbally distinguish both states has been established. There have been introduced terms such as parity error and permutation parity error, through orientation parity problem and permutation parity problem, up to the current OLL parity and PLL parity.

Today we know that this conception of a parity problem is unambiguous neither for a 4x4x4 cube, nor for the other combinatorial puzzles. Furthermore, it is kind of confusing (because of unhappily chosen terminology) and internally inconsistent (how's that a Rubik's cube which is being solved in a "normal way" has no parity problem according to this theory, but the same puzzle which is being solved blindfolded has one?), hence it cannot be recommended. For instance, a so-called OLL parity has nothing to do with an orientation of wing edges because these can be only permuted. A variant no. 1 in case of a so-called PLL parity - only two composite edges (as known as dedges - a dedge is short for double edge) swap on a 4x4x4 Supercube, or only 2 middle edges swap on a 3x3x3 cube, if you like - would be a real parity problem (i.e. an odd permutation of pieces) only on a 3x3x3 cube (if this position could be obtained using the allowed moves) because in order to solve a 4x4x4 Supercube, 2 2-cycles of wing edges are required to be done. That being said, only a variant no. 2 (only two corners swap on a 3x3x3 cube, or 2 corners and 2 center pieces swaps in case of a 4x4x4 Supercube, if you like) is a real parity problem on a 4x4x4 Supercube (for a 3x3x3 cube, if this configuration would be reachable, we would talk about a parity problem again, as it was also in a variant no. 1).

We will solve a so-called OLL parity on a 4x4x4 Supercube using an odd number of moves of inner layers in accordance with QTM (and an even number of moves of outer layers according to QTM). On contrary, for a so-called PLL parity on mentioned puzzle we need to apply an even number of moves of outer layers in accordance with QTM (and for a variant no. 1 an even number of moves of inner layers according to QTM, while for a variant no. 2 an odd number of moves of outer layers in accordance with QTM). We clearly see that non-distinguishing of both variants of a so-called PLL parity (e.g. when reducing a 4x4x4 Rubik's cube to a 3x3x3 cube) leads, on a 4x4x4 Supercube, to unnecessary confusion of the less informed readers and a loss of interest of the more knowledgeable visitors.

Trouble is when the sympathizers of "mathematical definition" and "reduction definition" of a parity problem are discussing with each other, since even though they can agree on something, in many aspects they disagree. For all cases let's at least mention the situation on a Void cube, in which it is needed to seemingly swap only two edges, or only two corners, if you like (no parity problem according to the "mathematical definition", a parity problem according to the "reduction definition") or one move of outer layer in accordance with QTM on a 3x3x3 Rubik's cube (a parity problem according to the "mathematical definition", no parity problem according to the "reduction definition"). A so-called PLL parity has already been discussed in previous two paragraphs.

I honestly think the whole conception of a "reduction" parity problem sucks, and it would be best if the cubers stopped to use it once and for all. Things would become to be called by their right names (as the mathematics, as an exact science, initially intended) and a dispute such as whether a certain puzzle configuration can be called a parity problem or not, and what does a parity problem actually mean, would be avoided.

What's the cause of a parity problem?

We cannot go wrong by saying that the cause of a parity problem lies in a transition from an even puzzle status (e.g. a solved state) into an odd puzzle status (arranged by an application of allowed moves). As a consequence of a parity problem, it is necessary to do an odd multiple of 2-cycles of certain piece type at least in one orbit of the puzzle, on condition that all the pieces occurring on the puzzle are mutually distinguishable. By this awkward (and hopefully right) articulation it has been repeated what is guiding us through the whole article from the beginning (see our interpretation of a mathematical permutation definition).

To get speedcubers more involved, it will be mainly spoken about a parity problem from their point of view for the rest of the article. First thing we can do is replacing a 4x4x4 Supercube back by a 4x4x4 Rubik's cube, since we won't work with the terms like a permutation or an N-cycle in a mathematical sense anymore. Neither a solved cube state is defined from this aspect.

Naturally, a parity problem is influenced by a puzzle solving method. Therefore if we use Reduction method (to a 3x3x3 cube) on a 4x4x4 Rubik's cube, a so-called OLL parity will occur, if:

  • we grouped center pieces together and paired-up wing edges using an odd number of moves of inner layers (in accordance with QTM), while a scrambling of the puzzle was done using an even number of moves of inner layers (according to QTM) or
  • we grouped center pieces together and paired-up wing edges using an even number of moves of inner layers (in accordance with QTM), while a scrambling of the puzzle was done using an odd number of moves of inner layers (according to QTM)

The reason for mentioning only the center pieces and wing edges in the text highlighted by bullets above is that only the moves of inner layers (containing stated pieces) toggle a permutation of wing edges (because the moves of outer layers don't toggle a permutation of wing edges).

Even a so-called PLL parity is, of course, affected by used 4x4x4 cube solving method. When using Reduction technique (to a 3x3x3 cube), then the reason for this phenomenon to be shown up lies in improper (careless, one might say) pairing process of a few last non-paired-up wing edges.

If analysis of a "reduction" parity problem is not done when solving a 4x4x4 cube using Reduction technique (to a 3x3x3 cube), then:

  • so-called OLL parity will occur in 50% of cases
  • so-called PLL parity will occur in 50% of cases
  • so-called OLL parity along with a so-called PLL parity will occur in 25% of cases
  • so-called OLL parity along with a so-called PLL parity will not occur in 25% of cases

By the way, only two edges swap or wrong orientation of only one edge (when seen as a 3x3x3 cube) won't happen on an NxNxN cubes with an odd N, because unlike the cube with an even N, they have also the middle edges. Those, as we already know, have to be in a solved state in an even permutation (so only 1 2-cycle of these pieces in a solved state is excluded), and at the same time there is no way to flip only one middle edge (it comes e.g. from a commutator definition for an even status of a 3x3x3 cube, or a conjugation definition for an odd status of the same puzzle, if you like). In contrast, wing edges behave all the same in their orbits on both odd and even NxNxN cubes (therefore their occurrence on a 5x5x5 cube correlates with an occurrence on a 4x4x4 cube and vice versa, for instance).

How to avoid a parity problem?

The essence of a scrambled puzzle is getting it back to a solved state. In order to do so, we are executing well-defined moves on it which can toggle a permutation of some pieces occurring on the puzzle. From a principle of the matter, a parity problem in a mathematical sense cannot be avoided. If we get a scrambled puzzle in an odd status, we are forced to apply at least one move that toggles a permutation of pieces from being odd to being even to reach a solved state. If we get eligible-scrambled puzzle in an even status, about its at least one occurred configuration over the solve can always be said (due to used solving method) that it is an odd puzzle status. That's because we are not trying to keep an even puzzle status at all costs, we are rather trying to meet our goal for each step of a solving method. And that can be achieved in an odd puzzle status, easy peasy. For example, a permutation of corners on a 2x2x2 Rubik's cube scrambled by R U moves is even, nevertheless, the puzzle is unsolvable using only a double moves in accordance with QTM, which keep/don't toggle a permutation of corners.

Yet there is a speedcubers' interpretation. If we stay at a 4x4x4 Rubik's cube and Reduction technique (to a 3x3x3 cube) as the most common way of solving in the area of speedcubing, then before each solve (and at any time during it) it can be done an analysis on whose basis it is possible to determine whether a so-called OLL parity will/won't occur over the solve. That allows us to choose in which solving stage we want to solve a possible occurrence of a so-called OLL parity.

In a real world it looks something like this:

  • we'll solve a so-called OLL parity at the end of the solve, usually by nothing-saying (at first sight) algorithm
  • we'll solve a so-called OLL parity at the end of the solve, this time by an intuitive algorithm
  • we'll solve a so-called OLL parity at the beginning of the solve

First point above is probably known to all speedcubers-beginners, who are not expected to understand the meaning of moves in the algorithm. They simply memorize the algorithm by heart and the cause of given moves is unknown to them (let r2 B2 U2 l U2 r' U2 r U2 F2 r F2 l' B2 r2 be an example). Second point above can be known e.g. to the visitors of these web-pages, because in how to solve a 4x4x4 Rubik's cube tutorial an algorithm which solves a so-called OLL parity in its first move is used. By following eight moves (in accordance with WCA notation, not QTM) it gives back the center pieces to the initial state. Then the scrambled wing edges are re-paired-up/re-solved using an even number of moves of inner layers.

Finally the third point above can be applied in a way that prior to a solve we will determine whether the wing edges are in an odd or even permutation (some top solvers of a 4x4x4 Rubik's cube while blindfolded can do it during 15 seconds, which is official inspection time for a cube before starting to solve it in speedcubing events). Then, we will group center pieces together by means of either even or odd number of inner layers (in accordance with QTM) so that a permutation of wing edges would be even after this step is complete. Afterwards, just pair-up wing edges "normal way" (i.e. use an even number of moves of inner layers according to QTM), without making useless stupid things (such as pairing-up by means of an odd number of moves of inner layers in accordance with QTM). Out of curiosity, compare this train of thought with a parity problem solution in case of e.g. a Square-1 and you should come to an analogy (including that required analysis to solve a parity problem can be done even prior to solving of both puzzles itself).

More detailed description is as follows: on a scrambled cube, at first count a number of 2-cycles which are needed to apply in order to solve wing edges. If this number turns out to be odd, you have to group center pieces together by an odd number of moves of inner layers (according to QTM). If this number turns out to be even, you have to group center pieces together by an even number of moves of inner layers (according to QTM).

A grouping of 6·4 = 24 center pieces together while counting the needed moves of layers seems like a quite difficult task considering a demand on fast execution. Fortunately, the process can be simplified (for example by just that instead of 24 pieces we need to group together only 20 of them - the remaining 4 will be automatically in required configuration). After grouping of the first 4 center pieces of the same color together (by using X moves of inner layers in accordance with QTM) is done, we can continue by grouping of another 4 center pieces of the same color together (by using Y moves of inner layers in accordance with QTM) which belong to the opposite face compared to the first 4 center pieces (on a classical cube color scheme, the opposite faces differ by a shade of yellow color so that white is opposite yellow, green is opposite blue and red is opposite orange). The advantage of grouping the opposite centers together is that we don't need to count sequences like r U (or U2) r' - these don't toggle a permutation of wing edges, since two moves of inner layers according to QTM are done. As a result, a number Y won't be unnecessarily big. Third 4 center pieces are grouped together similarly (by using Z moves of inner layers in accordance with QTM). The sum of moves X + Y + Z = C (as centers) is afterwards compared to a number of 2-cycles which are needed to apply in order to solve wing edges prior to an actual solve of the puzzle (or a grouping of 12 center pieces together = W (as wings), if you like).

If a number C is odd while a number W is even (or C is being even while W is being odd), turn the puzzle so that one quaternion of center pieces grouped together would be at the F position, whereas the remaining two quaternions at the L and R positions. Then do an algorithm r U2 r U2 r' and as a result a permutation of wing edges will be toggled (due to an odd number of moves of inner layers according to QTM). Next, just continue in grouping of the remaining center pieces together usual way (that means by making a move of inner layer (a so-called de-construction), grouping the pieces together and making an inverse move of inner layer (a so-called re-construction)). Good news is we don't need to count anything for the remaining 3 quaternions of center pieces because a current even permutation of wing edges is now not affected by suitably applied allowed moves.

Two previous sentences apply to a case in which C as well as W is odd (or even) after grouping of 12 center pieces together is done (hence we don't need to take an algorithm r U2 r U2 r' into account over the solve).

By an outlined procedure we will avoid the need to solve a so-called OLL parity on a 4x4x4 Rubik's cube at the end of the solve. Perhaps it will be more understandable on a video. In any case, don't forget that the video is filmed from a speedcubing (reduction) point of view on a parity problem, not a mathematical conception of this term!

You may notice that some moves which have been denoted as Y and/or Z in the written form are unnecessarily counted into the total sum of C. Specifically, it concerns the moves of inner layers in a sequence such as r U (or U2) r'.

Of course it's not required to distinguish among X, Y and Z when counting them, because only their total sum is what's important for us. Thus when determining a number of moves of inner layers during a grouping of 3 quaternions of center pieces together, we don't need to do ascending counting (like 1, 2, 3, 4 etc. as in case of a video) because on principle, all odd numbers can be replaced by one symbol (e.g. 1 (retraced as monosyllabic "one") or O (as odd)) and all even numbers by a different symbol (e.g. 2 (retraced as monosyllabic "two") or E (as even)), and it could be operated only with these two symbols.

Naturally, there are other techniques (methods, if you like) on how to solve a 4x4x4 Rubik's cube (Cage method, for instance, is such a nice example - see below). When using unusual reduction to a 2x2x2 cube (instead of a 3x3x3 cube), we will completely avoid a so-called PLL parity (since wing edges are directly associated with corners, i.e. they are occupying the places where they actually belong in a solved state). For a so-called OLL parity we will use already known procedure - we will let the orbit of wing edges in an even permutation (eventually, for this purpose, we will do an algorithm which results in an odd number of 2-cycles of this piece type - for example in case of solving a 3x3x3 Rubik's cube blindfolded it is R2 U' R2 U R2 U D' R2 U R2 U' R2 D). For more see a video whose author is Jon, a lover of combinatorial puzzles (it can be said that Jon, in a final effect, solves an occurring so-called OLL parity by 3 2-cycles of wing edges (time 22:44) - stated algorithm R2 U' R2 U R2 U D' R2 U R2 U' R2 D adapted on a 4x4x4 cube is in his execution formed by 19 moves of outer layers and 7 moves of inner layers in accordance with QTM. On a 4x4x4 Supercube when analyzing each move separately, we would get an odd permutation of corners (19 4-cycles) and at the same time an odd permutation of center pieces (2·7 + 19 = 33 4-cycles) and simultaneously an odd permutation of wing edges (2·19 + 7 = 45 4-cycles). When analyzing an algorithm as a whole, we would get 1 2-cycle of corners and at the same time 3 2-cycles of center pieces and simultaneously 3 2-cycles of wing edges.).

For the last time, let's get back to a Reduction technique of a 4x4x4 Rubik's cube (to a 3x3x3 cube). One thing that's left is an explanation of how to avoid a so-called PLL parity.

First, during a pairing process, leave only two pairs of wing edges non-paired-up. This configuration can be always achieved (2 pairs are chosen by a reason of exercise - the issue can be best explained on them, however, even for 3 pairs of non-paired-up wing edges we would get similar conclusions). Next, on the basis of centers, determine a permutation of both corners and composite edges/dedges (if a permutation of wing edges is even, exactly one pair of non-paired-up wing edges is "half-solved" at one out of two places where non-paired-up pairs of wings edges belong to; if a permutation of wing edges is odd, we can either imagine a swap of two wing edges in one pair and consider previous situation or we can consider one pair of non-paired-up wing edges as to be solved for now (this is an analogy to "half-solved" non-paired-up pair of wing edges) at one out of two places where non-paired-up pairs of wings edges belong to - hence a permutation as well as orientation of the other non-paired-up pair of wing edges (from the composite edges point of view) is always unambiguously given). Basically it is an analyzing of 2-cycles of corners and composite edges, similarly to a solving of a 3x3x3 Rubik's cube blindfolded (composite edges are replaced by middle edges in such case). Then (on the basis of analysis), all we need to do is to apply a pairing algorithm for two pairs of wing edges (e.g. (d R U R' U' F' U F d') (F' U' F U R U' R')) in the right order, which means using a proper setup moves so that after an execution of that algorithm a permutation of both corners and composite edges would be the same.

It will be more illustrative on the simulators (we see almost solved puzzle there because of better illustration - by that way an outlined analysis of 2-cycles is not required to be made).

Prior to applying a pairing algorithm, we must be sure which wing edges will be moved and where. On the left hand-side simulator it is desirable to swap a blue-yellow wing edge at the UB position with a yellow-green wing edge at the UF position, and afterwards swap also both blue-yellow wing edges at the UB position. On contrary, not desirable swap of a green-yellow wing edge at the UB position with a yellow-blue wing edge at the UF position, and afterwards a swap of both blue-yellow wing edges at the UB position is shown on the right hand-side simulator. In both cases there are 4 setup moves, subsequent 9 moves are responsible for 2 2-cycles of wing edges, the rest of moves brings the puzzle back into its initial state using inverse moves (to the first 4 ones). Exactly one "half-solved" pair of non-paired-up wing edges at the UF position indicates that these were in an even permutation at the beginning.

For the sake of completeness you can watch analogous duo of simulators with initial odd permutation of wing edges (so either both pairs of non-paired-up wing edges or neither of them are "half-solved"). The idea of pairing (using 2 2-cycles of wing edges) is the same, as well as a principle of execution (with the only difference that a number of setup moves has changed - instead of four, there are needed only two of them).

An analysis required for a determination of occurrence of a so-called OLL parity or a so-called PLL parity in any (i.e. even initial) stage of solving is usually very time-consuming. That is the main reason why an overwhelming majority of speedcubers solves a "reduction" parity problem at the end of the solve.

Cage method

After various optimization processes, the Cage method is apparently more effective (by means of moves, hence time) when solving larger cubes (from approx. 10x10x10) in comparison with Reduction technique to a 3x3x3 Rubik's cube. I personally use Cage method for the 4x4x4 and 5x5x5 cubes (I don't own larger cubes), and in contrast to Reduction technique (to a 3x3x3), it is also suited for solving an NxNxN Supercube.

Before you begin to read following tutorial frantically, I suggest you to get familiar with the text written on this page above (if you haven't done that yet). Besides an understanding of established terminology/notation, you will also get a general insight into a parity problem issue.

Cage method has nothing to do with an actor Nicolas Cage. It was introduced in the 80's of the last century in conjunction with a 4x4x4 Rubik's cube itself. The name reflects a visual characteristic state of center pieces on the puzzle, since these seem to be trapped in a cage. You can also encounter a term "centers last". For a 4x4x4 Rubik's cube the method can be schematically sketched as follows:

Cage method

Some cubers are solving corners at first. We will start by a grouping of center pieces of one color together, simply because I find it less time-consuming (faster in comparison with a process in which we would group all center pieces together at the end of the solve). The truth is, it doesn't matter and a final decision is on you anyway - so if you want to group 4 center pieces together now, go ahead. If you prefer to group them together at the end of the solve, nothing happens. You can't go wrong here.

The simulator below groups center pieces (by these they are understood internal (N-2) · (N-2) pieces of one face on an NxNxN cube) together and then it solves corners (well, after a U move those would be solved). In the first approximation we can imagine them as the 2x2x2 Rubik's cube.

Then all wing edges (for N being odd (i.e. for the cubes with an odd number of layers) along with middle edges) are solved, except for those which belong to the M-ring (from a 3x3x3 cube point of view) - for an inspiration see the corners-first method or a simulator itself below. Pairs of wing edges are being solved in this order: white-green, white-orange, white-blue, yellow-green, yellow-red, yellow-blue and finally yellow-orange.

Since from the beginning we are inserting wing edges to the places where they actually belong, we are actively avoiding a so-called PLL parity.

Unfortunately, sometimes the last pair of wing edges in a given orbit (considering the cubes larger than 5x5x5, where there is more than one orbit for wing edges) which doesn't belong to the M-ring (from a 3x3x3 cube point of view) is not paired-up yet, as it can be seen on a simulator above. For a 4x4x4 Rubik's cube, generally three cases may occur:

  • both wing edges are in the M-ring (from a 3x3x3 cube point of view)
  • one wing edge is in the M-ring (from a 3x3x3 cube point of view)
  • both wing edges are not in the M-ring (from a 3x3x3 cube point of view)

Last mentioned option is addressed in linked article about the corners-first method. If you want more intuitive way of orientation of that composite edge (and some other composite edge in the M-ring), have a look at a Void cube tutorial or watch a video below. First mentioned option highlighted by a bullet above can be further divided into two situations. If wing edges on a 4x4x4 cube can be paired-up only by the moves r or l, pair them up and look again on a page about corners-first method, where the next step of a solution is explained. If wing edges on a 4x4x4 cube cannot be paired-up only by the moves r or l, place one wing edge at the position of UF composite edge and place the other wing edge at the position of FD or BD composite edge. Now, do a U2 move, pair-up concerned wing edges using r or l moves and subsequently do an inverse U2' move in order to get back composite edge which belongs to the UL position. Afterwards, visit a page about corners-first method (or, if you dare, solve intuitively).

If there is one wing edge in the M-ring (from a 3x3x3 cube point of view) while the other one is not in there for a given orbit (there is only one such orbit on a 4x4x4 cube), relocate a composite edge from the UL position to the UR position in a way so that all necessary non-paired-up wing edges would be in the M-ring. Continue by pairing them up (see previous paragraph) and solve all composite edges except for those which belong to the M-ring. One exemplary situation is shown on the simulator.

For the NxNxN cubes with an odd number of layers it is now convenient to solve 4 remaining middle edges. It can be done by means of corners-first method (it is mainly aiming at speed, thus for a more intuitive way look at the Void cube tutorial - see the sections permutation of edges in remaining layer and orientation of edges in remaining layer).

In the next step we will solve remaining wing edges - at first in one layer ("one half of wing edge orbit") and then in the other layer ("the other half of wing edge orbit"). It requires a bit of caution because it is necessary to apply an even multiple of R2 move (or an equivalent to R2 move that interchanges wing edges in both layers ("both halves of the orbit")) in order to not scramble already solved puzzle pieces.

At first we see a solved blue-red wing edge at the UF position on the simulator on the left. After a puzzle orientation (z y), red-green wing edge is being solved by an R2' move in the same layer. In order to apply inverse R2, it is needed to put both mentioned edges away, so that they wouldn't be scrambled again - to reach this, we will use a u move. Corners will return to their original state by an R2 move and initially solved edges will be placed at their places using a u' move. It is followed by a puzzle rotation (y) that prevents to scramble already solved wing edges by eventual R2 move execution.

You may notice that an orange-blue wing edge at the RB position got luckily solved by itself and the last wing edge belonging to the same layer (orange-green one) is placed at the LF position. It is tempting to apply R2' move in order to "pair them up" with their subsequent inserting into appropriate layer by means of d R2 moves. However, by doing so both concerned wing edges would be swapped (plus we can't count on an occasional solve of the other layer, as it would be in case on a simulator (after a d move)).

Therefore it is better to insert third wing edge into the first layer (on a simulator, by first layer is understood the second layer from the top) at the wrong place (there is only one such place), because when doing just outlined "pairing-up" process, both wing edges will be solved (instead of a previous case in which they were swapped). Hence a simulator tries to get a blue-orange edge at the position to which a green-orange edge belongs (but in a way that already solved wing edges in this layer wouldn't be scrambled). By R2' d R2 moves the goal would be reached, however, sadly the same arrangement of pieces as in a previous paragraph would be achieved again - that means both wing edges would be swapped instead of just one of them.

Thus a simulator puts a green-orange edge at the LF position away by a d' move and then it is getting a blue-orange wing edge into its needed configuration. Now it is sufficient to "pair-up" both wing edges (by d' R2 moves) and insert them together at their places (by d' R2' moves).

The other layer becomes the first layer after a z2 move and there can be two present cases in it: either all wing edges are solved (after possible u (arranging) move is applied) or it is needed to swap two of these (after possible "arranging" move is applied). On principle it somehow doesn't matter whether two adjacent or two diagonal wing edges are being swapped - mathematically speaking, it is an odd permutation of wing edges (and if we had been using Reduction technique to a 3x3x3 cube to solve a 4x4x4 cube, we would be talking about a so-called OLL parity in any case). Now we can't apply the previous process of inserting of wing edges at their places yet, simply because a current lower layer would by scrambled by doing so.

To swap two wing edges at the RF and RB positions, an algorithmic solution with an odd number of inner layers in accordance with QTM can be used. For instance R2 u' R2 u R2 u d' R2 u R2 u' R2 d (see a section solution to two inner layers in the 3x3x4 puzzle tutorial). If we want to swap two diagonal wing edges (as in case of a simulator), we will execute the algorithm three times (and we will properly rotate the cube or make a purposeful setup move in between), while the latest out of three algorithm executions is exclusively related to a swap of two adjacent wing edges.

An alternative to a configuration after a move no. 16 is to use B2 d B2' setup moves, followed by mentioned algorithm R2 u' R2 u R2 u d' R2 u R2 u' R2 d and finished by the inverse setup moves B2 d' B2'.

A statement about possible intuitive solution will certainly cheer up everyone who doesn't want to memorize the algorithms. Of course we won't prevent a requirement of getting wing edges from being in an odd permutation to being in an even permutation, nevertheless, it is possible to do so using only a single move of inner layers in accordance with QTM - a u move, for example. By doing so, from 1 2-cycle of wing edges will suddenly become 1 3-cycle and such a task should be easily solvable, e.g. by a conjugation B [u' (R U R') u (R U' R')] B', or by its symmetrical case B' [u (L' U' L) u' (L' U L)] B, see a video below.

At last we will group center pieces together. A tool for that are the commutators and conjugations. The last simulator is dealing with center pieces in this order: red, green, yellow and orange.

Final word

If the article you just read has been forcing you to think about a logic of described things from time to time, I am happy to announce it has fulfilled its purpose. I secretly hope you have been also learning something new. Perhaps that you can't solve the 4x4x4 Rubik's cube :-).

Furthermore I believe I adequately responded to the questioner's query quoted in a prologue, as well as that I offered slightly different and unusual view (conceived in a broader context) to another combinatorial puzzles.

Last but not least, I would be pleased if we could agree on the existence of an odd permutation of at least one orbit of pieces (i.e. a parity problem) for the last 6 random configurations on a 4x4x4 Supercube.

Parity problem
Reduction method (to a 3x3x3)
Parity problem
Cage method
Parity problem
Layer by layer method
No parity problem
2 2-cycles of wing edges
Parity problem
1 2-cycle of corners and 1 2-cycle
of center pieces
No parity problem
1 3-cycle of center pieces



Christopher Mowla deserves my big thanks for all the effort he shown regarding our private correspondence, not only on a topic of permutations and analysis of the NxNxN Supercube. It wouldn't be possible to write up this article into its current form without his kind and extremely useful consultations.
Michael Feather (who requested a translation of the article above) helped me to get more complete perception of permutations and N-cycles, therefore I would like to thank him from the bottom of my heart as well.

The page was graphically improved by Boris Mouradov and Michael Feather.

ADVERTISEMENT:
„Žádný člověk není tak bohatý, aby mohl koupit svoji minulost.“ Oscar Wilde