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 $3 \times 3 \times 3$ cube would be great. For any size cube, awesome!

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). On 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 2/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.

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.