How to tell if a Rubik's cube is solvable

How can I determine if a certain Rubik's cube, that is in a certain state, is solveable? By "certain state" it could mean that the cube has been dismantled and put together again. And in my experience if you don't put it together the right way, the cube might not be solvable.

A way to check for a 3x3x3 cube would be great. For any size cube, awesome!

-
A very simple way would be to apply a well-known algorithm for solving it until you reach a point where it is "obvious" that you cannot proceed. – Jesko Hüttenhain Apr 3 '12 at 11:59
Yeah, it would be easy if it were a human. but I wanted to apply this to a computer program. So I am trying to create an algorithm that can determine if the cube is solvable. – Mel Apr 3 '12 at 12:11
Well the literature on the subject tells us that there are twelve different sets of configurations, and you can't get from one to the other without taking the cube apart. They are shown by parity considerations - so twisting a single corner cube creates an unsolvable cube (there are three orientations to a corner cube). The edge cubes give a similar factor 2, and the parity consideration that each move of the cube gives an even permutation (the basic move is a product of two 4-cycles on edges and corners respectively). So you need to measure these parity changes against a base case. – Mark Bennet Apr 3 '12 at 12:21
Have a look at emba.uvm.edu/~snapp/teaching/cs32/lectures/rubik.pdf, starting on page 38. It may answer your question. – Gerry Myerson Apr 3 '12 at 12:46
@Gerry: That text gives one way each of defining orientational invariants (without mentioning that this is only one of many ways to define them) but is vague if not to say wrong on the positional invariant. It says: "Each sequence of operations always moves a multiple of 4 pieces. It is thus impossible to interchange just two corners, or just two edges." But the number of pieces moved $\bmod 4$ is not an invariant; successive rotations of adjacent sides can move exactly one piece back into position and thus lead to an odd number of pieces moved. – joriki Apr 3 '12 at 14:50

For a 3×3×3 cube there are three different conditions to check, usually decomposed as "permutation parity", "edge parity", and "corner parity".

(Mathematically, the group that the describes all ways to take apart and reassemble the cube has the group of legal movements as a normal subgroup, and the quotient group is $C_2\times C_2\times C_3$, so it is natural to group the check into three parts. In principle there ought to be equivalent ways to deal with the $C_2\times C_2$ factor, but the overall and edge parities are so natural that looking for the other decompositions doesn't seem worth the trouble).

We imagine that the spindle axes (and therefore the center cubies) stay fixed in space -- turning the entire cube is trivial and ignorable.

Permutation parity: This rejects 1/2 of all configurations. In this step, ignore which way each of the little cubies is turned and just look at where it has ended up. In this way each way to assemble the cube corresponds to some particular permutation of the 20 non-center cubies. Each legal permutation is an even permutation (because each quarter turn is a product of two 4-cycles and therefore itself even). Oh the other hand it is well known that any even permutation can be achieved, as long as it doesn't try to interchange edges with corners.

To check whether a given permutation is even, just write down the permutation (i.e. the function from "where the cubie is" to "where it ought to be") and compute its sign by any standard methods -- e.g., by counting inversions or unraveling its cycle structure.

For edge and corner parity, we temporarily forget the difference between opposing colors on the cube -- say, we call both of white and yellow $X$, both of green and blue $Y$ and both of red and orange $Z$.

Corner parity: This rejects 1/3 of all configurations, and can be defined in the following way: Since we have unified opposing colors, each corner has the colors $X$, $Y$ and $Z$. Let's say that a corner is "oriented correctly" for its instant position if its $X$ side is next to an $X$ center. (This treats the $X$ color pair specially; the $Y$ and $Z$ sides may or may not line up with matching centers). Now for any way to assemble the cube, consider how many clockwise 120° twists of a corner-in-place it would take to orient all of the corners "correctly" without moving them. If this number is a multiple of $3$, the configuration passes the corner parity test. (It is easy to see that a quarter turn of an $X$ face keeps this number unchanged, and only slightly more complex that a quarter turn of $Y$ or $Z$ changes it by a multiple of $3$).

Edge parity: This rejects 1/2 of all configurations. It can be computed much in the same way as the corner parity, except that the definition of "correct orientation" for an edge is a bit more involved. One may take, for example:

• An edge with a $X$ side is oriented correctly if the $X$ side is next to an $X$ center or if the edge is in the middle layer and would become correctly oriented by a quarter turn of the $Y$ (but not $Z$) face it is in.

• A $YZ$ edge is oriented correctly either if it sits between a $Y$ and a $Z$ center in the obviously matching way, or if its $Z$ side is next to an $X$ center.

One may now check that a quarter turn of an $X$ or $Y$ face doesn't change whether any edge is oriented correctly or not, whereas a $Z$ quarter-turn changes each of the four edges it moves from correct to non-correct or vice versa. Thus, every legal move changes the number of correctly oriented edges by an even amount. So we must reject any way to assemble the cube that ends up with an odd number of incorrectly oriented edges.

Though not immediately obvious, these three tests will reject any configuration that cannot be solved.

The corner-parity check carries over to larger cubes unchanged, but the two other tests cannot always be directly applied to larger cubes. For a 4×4×4 cube with indistinguishable center pieces, the corner parity check is the only check; anything that satisfies it can be solved. For a 5×5×5 cube, the virtual 3×3×3 formed by corners, middle centers and middle edges must be solvable according to the 3×3×3 rules, and it turns out that the remaining pieces can always be solved, again assuming that centers are indistinguishable. I think that larger-yet cubes continue the pattern from 4×4×4 and 5×5×5.

There are special parity checks to apply for supercubes (where the orientation and/or permutation of center pieces of the same main color matters); I don't remember offhand how they work.

-
The regularity in the assignments you describe is useful for a computer evaluation but not required mathematically; any assignments from $\mathbb Z_2$ to edge pieces and edge slots and any consistently oriented assignments from $\mathbb Z_3$ to corner pieces and corner slots will do. – joriki Apr 3 '12 at 15:04
I didn't know that, but did notice it in your answer (somehow I didn't get a new-answers alert while typing, or I would have been considerably less verbose here). – Henning Makholm Apr 3 '12 at 15:07
+1 Well done, Henning. AFAICT I used exactly the same method to describe corner parity on my Rubik's cube page (in Finnish only, so I'm not gonna bother with the link - the page is old anyway :-). The word parity suggests to me that the check is two-valued, whereas here it is 3-valued. Doesn't matter! Interesting stuff about 4x4x4 and higher!!! I didn't know that these were the only checks (though I once had a working 4x4x4 and a 5x5x5, but they were not very durable). – Jyrki Lahtonen Apr 3 '12 at 17:49
@Jyriki: Agree about parity but couldn't think of a better word. Triplity? The 4×4×4 and 5×5×5 properties follow because I can transpose two edge cubies (outer edges on the 5×5×5) without disturbing centers or corners, which together with conjugation generates the entire $S_{24}$ of edge pieces. The centers themselves are easily solved from any starting point because the pieces are interchangeable in groups of 4. – Henning Makholm Apr 3 '12 at 18:05
Thank you for explaining in plain english! I'm just a little confused with the permutation/positional parity. I am supposed to compute for the sum and it should be divisible by four right? (not just even). If I swap 2 adjacent edges or corners, that would be an even permutation right? but the cube wont be solvable. – Mel Apr 4 '12 at 7:24

As explained at Wikipedia, the operations you can perform without disassembling the cube lead to $12$ different equivalence classes; you want to know whether the current state of the cube is in the same class as the solved state. One way to do that is to use invariants that characterize the classes.

As discussed in comments under example's answer (now deleted), the invariants decompose into a $\mathbb Z_2$ edge orientation invariant, a $\mathbb Z_3$ corner orientation invariant and a $\mathbb Z_2$ positional invariant.

For the edge orientation invariant, arbitrarily assign the elements of $\mathbb Z_2$ to the two faces of each edge slot and to the two faces of each edge piece; then the invariant is the parity of the number of matches between the assignments of the edge pieces and the assignments of the edge slots they're in. If you take out an edge piece and insert it the other way around, you change the invariant. On the other hand, if you turn a side (the only operation you can perform without disassembling the cube), the sum of the four changes you induce is the change you'd get for one piece being turned around by $2\pi$, so this operation doesn't change the invariant. Of course you'll want to choose an assignment that's easy to handle systematically on a computer, but any assignment will do.

Likewise, for the corner orientation invariant, arbitrarily assign the elements of $\mathbb Z_3$, say, clockwise, to the three faces of each corner slot and to the three faces of each corner piece; then the invariant is the element of $\mathbb Z_3$ that you get by adding up all the differences (in $\mathbb Z_3$) between the assignments of the corner pieces and the assignments of the corner slots they're in. For analogous reasons as above, this invariant changes if you take out a corner piece and insert it with another orientation, but doesn't change if you turn a side.

The positional invariant is just the parity of the permutation of all the pieces, edge pieces and corner pieces together, disregarding orientation. If you swap any two corner pieces or any two edge pieces, you change the parity; on the other hand, if you turn a side, you apply a $4$-cycle to the edge pieces and a $4$-cycle to the corner pieces, so the parity of the overall permutation doesn't change.

-