Link (with remarks): 20 Moves Or Less Will Solve Rubik’s Cube

This story showed up on Morning Edition yesterday, and I thought it would be worth explaining a little more carefully what it means to “solve” a Rubik’s Cube, and why professional mathematicians would be interested.

This is not a story about puzzles or cubes; it’s a story about groups.  Groups are what mathematicians use to talk about symmetry.  A group is a set of objects (which we can think of as transformations), together with a composition operation which satisfies certain properties, designed formalize our natural notion of symmetry.  Sometimes a group comes naturally with a set of generators, special elements of the group with the property that every element of the group can be built out of those generators and the composition.  The group of symmetries of the Rubik’s cube is generated by the operations of turning the faces of the cube.  (Each of six faces can be turned widdershins or antiwiddershins, so we’ll call that 12 generators.)

If you pick up a Rubik’s cube which has been jumbled up, what you really have is the element of the symmetry group of the Rubik’s cube which represents the transformation from an unmixed cube to what you now see before you.  You know it’s in the symmetry group because your adversary mixed the cube up by turning faces (probably many, many times).  But you weren’t watching her turn the faces, so you don’t know what she did (if you did know, you could just reverse her steps).  All you know what the cube looks like now.  Your job is to think of some sequence of turns that might be what she did, that would have produced the jumble you now hold in your hands; then you do that, backwards.

(Here I’ve been assuming that the cube was mixed by some other person turning the faces in some complicated and/or haphazard way. If you jumble a Rubik’s cube by switching stickers, then you’re evil!  There’s no guarantee that the pattern you made could have been generated by turning faces, so there’s no guarantee .  That is, there’s no guarantee that your transformation is in the Rubik’s cube group.)

This is what a mathematician might see when solving a Rubik’s cube.  Un-jumbling a cube is (in some sense) the same as identifying the transformation used to jumble it and expressing that transformation (really its inverse) in terms of the basic ones (face turns).  Problems like this are important often in mathematicians.  Given a group G, a set of generators $g_1, g_2, g_3,\ldots$, and a group element $x$, how can we actually write down $g$ as a composition of the $g_i$?  In general there will be a lot of such representations, but can we find a simple one?  Is there a simplest one?  Can we find it?  These are not (at least, not always) frivolous or recreational questions.

But hadn’t people already solved the Rubik’s cube problem?  So how is this announced result different than what we’ve known about Rubik’s cubes for years?  It’s much stronger.

• What we usually mean by “being able to solve a Rubik’s cube” is, given a jumbled cube, figuring out a sequence of moves that will unjumble it.  Not necessarily the shortest sequence of moves.  A mathematician might say they have an efficient process for expressing any Rubik’s cube symmetry in terms of face turns.
• The new result says that, given a jumbled Rubik’s cube, we (more precisely, their computer) can unjumble it in the minimum possible number of moves.  That is, we can express every symmetry as a product of the minimum number necessary.

P.S.

If you’ve never heard of Looney Labs, the company of the person interviewed here, check out their website.  Several of their games are on my favorites list.

P.P.S.

Sometimes you will see a novelty Rubik’s cube in which the faces of an unjumbled cube are 6 different pictures (of cartoon characters, say) instead of 6 solid colors.  This is actually not the same puzzle as a classic Rubik’s cube; it’s slightly more complex.  Why is that?

3 Responses to Link (with remarks): 20 Moves Or Less Will Solve Rubik’s Cube

1. EastwoodDC says:

>P.P.S. … Why is that?

Rotation of the squares at the center of each face. This is unimportant with solid colors, but it matters if it must line up with the rest of the picture.

2. Cap Khoury says:

Kudos, EastwoodDC!

When we distinguish between orientations of squares, there are (at least potentially) multiple symmetries that differ ONLY in the orientations of some squares, which means that originally we weren’t calling them different at all.

For people who haven’t thought much about this before, convince yourselves that the only place this issue can show up is, in fact, in centers of faces.

For people who have thought about Rubik’s cube before, a rather more difficult challenge. HOW MUCH bigger is the symmetry group of the Rubik’s cube with pictures? That is, HOW MANY symmetries of that cube change only orientations?

3. Hi, big thanks for your work.. I searched for something like that, but Icouldn’t find anything that’s that what I was looking for:( You helped me to save god knows how much time.. Thanks!