Symmetry for Beginners – The Rubik’s Cube

Symmetry is everywhere in our natural world. Just take a look at your hands, a butterfly, or a sunflower.  It’s easy to pass off the idea of symmetry and symmetric structures as a simple quirk of existence, and to pay it little mind. If this is your view, I can assure you it will no longer be by the end of this series. If we force ourselves to look beyond the grade school applications of symmetry, we find a world rich in connections via many different types of symmetric identities. One of the most interesting is Gauge Symmetry, which lies at the heart of Quantum Electrodynamics, or QED (we’ll get into this a bit later in the series). Several branches of higher level mathematics study symmetry in detail, allowing a host of sciences, from physics to chemistry,  to view difficult problems and theories from a different perspective.

The subject matter of the ideas explored in symmetry is complicated, and not well known outside of academia and the theoretical sciences. It is the goal of this series of articles to simplify some of the concepts that underpin the study of symmetry, so that the average hacker can gain a basic (and I mean basic) understanding of this fascinating body of knowledge, and put it to use in future projects.  We’ll start things off by taking a look at a machine that has crossed the Hackaday server many times – those nifty Rubik’s Cube solvers. Just how do those things work anyway?

The Rubik’s Cube

When [Erno Rubik] invented his famous puzzle in the late seventies, he quickly found out that trying to solve it via random twists was an impossible task. He was quite right, as there are over 43 quintillion states, or permutations, that can be made on a 3×3 Rubik’s Cube. It’s hard to imagine him not getting a chuckle out of watching a machine solve his invention in a single second. Now, we all know how that thing works. We know how webcams and stepper motors work, and how to tie them to a SBC running some type of solving algorithm. But what about the algorithm itself? What is it doing to solve the puzzle?

cube_03
Source

One approach is to turn the instructions on the Rubik’s Cube website into source code. Indeed, this is how many of these solvers work.  This process works in layers for which you designate by orienting the cube so that the top layer faces up and the bottom layer faces down. The top layer is solved by aligning the middle cubes first (making ‘the cross’), and then the corners. Once the top layer is solved, the middle layer is tackled. And finally the bottom to complete the puzzle. Solving each layer can be done by simply following the directions on the website.

The problem with this approach is it follows Searle’s Chinese Room argument – a thought experiment to show that computers can never be “intelligent.” It consists of a man in a room following directions. One person inputs some questions and the man follows the directions that allow him to answer the questions, even though he doesn’t understand the questions themselves. They are written in Chinese. He outputs his results. The person reads the output and declares the room intelligent. But the man was simply following directions…he has no idea of what he wrote means. With our Rubik’s Cube algorithm, we’re simply following directions without the slightest clue on how or why it works.

Another approach, more appropriate for this article, is to consider the Rubik’s Cube in light of a branch of mathematics called Abstract Algebra, as this algorithm does. This will allow us to exit out of Searle’s room and truly understand what we’re doing.

Abstract Algebra

Now, this is where we enter simplistic mode. Abstract algebra is a graduate level math course, and I will not pretend to understand or explain it on that level. My goal is to give you a basic definition of what it means, so that we can understand a little more about symmetry and symmetric structures.

cube_01
Source

Let us consider the equation:

5x=2

Many of us will provide the answer of x = 2/5. This is because we’re making some implicit assumptions, such that 5x means “five multiplied by x” and that the real numbers are allowed answers. From this point out, we’re no longer allowed to make those assumptions.

Let’s generalize the above equation to:

a\cdot x=b

We have to ask ourselves the following questions:

What objects are “a” and “b”? They don’t have to be numbers. They can be anything, including permutations of a Rubik’s Cube.

What is “x” allowed to be?

What does the “•” operation do?

You should be able to see where the ‘abstract’ in abstract algebra comes from. Let’s push this idea further and see what happens when me make up some new rules to answer these questions.

Group Theory

Let us consider a particular set of elements. Elements can be anything…numbers, Rubik’s Cube permutations, Arduinos, anything. A set is just a collection of distinct objects (our elements). A well known example would be the set of integers. Each integer is an element of the set. Think about a box of resistors. The box containing all of the resistors is a set, and each resistor is an element of that set. You get the idea.

Now let us apply some rules, also known as axioms (I use ‘rules’ because it sounds less intimidating), to our set. If a set of elements passes all of our rules, it shall be considered a Group.

Rule 1 – Closure

If a and b are in our group, then a • b is also in the group
cube_02
Symmetry in Nature. Click here for more

Remember that the ‘•’ does not mean multiplication. It’s called a binary operator and it can be anything. An example would be if a and b are permutations of our Rubik’s Cube and the ‘•’ operator means turning the top, side, bottom, etc. In this case, a Rubik’s Cube passes the Closure Rule, because after we perform our binary operation, the resulting permutations exist within our set (the cube itself).

Rule 2 – Associativity

If a, b and x are in our group, then (a • b) • x = a • (b • x)

Only addition and multiplication of real numbers are associative. Subtraction and division are not. Thus when working with groups, instead of subtracting we must add a negative. For division, we multiply by the reciprocal. In abstract algebra, these are known as inverses.

For our Rubik’s Cube, turning a face twice, then once will produce the same result as turning the face once, then twice. Our cube passes the Associativity Rule.

Rule 3 – Identity

There exists an element of our group, that we shall call 'e', such that for any element a of our group, a • e = e • a = a

Now this one looks a bit tricky at first, but it’s simple once you see some examples. It’s also closely related to Rule 4, and might make more sense after reading both Rules 3 and 4. If our set is to be considered a group, there must exist an identity element. This element is neutral, and when the binary operation is performed with any element in the set against the identity element, the result will be the unmodified element. If our binary operator were addition, the identity element would be zero. If our binary operator were multiplication, the identity element would be one.

The Identity Rule is important to identifying symmetry as it looks for some type of invariance within a structure (or group). Invariance meaning parts of the group that do not change even when its elements undergo an operation.

The Identity element for our Rubik’s Cube is basically to do nothing. This will make more sense after reading Rule 4.

Rule 4 – Inverse

For any element a of our group, there is an element a-1 such that a • a-1 = e and a-1 • a = e

As advertised, Rule 4 is related to Rule 3 in that it involves our Identity element. It says that in order for our set to be considered a group, there must exist an inverse for each element in the set, so that when our binary operator is applied to the element and its inverse, the result will be the group’s Identity element.

For our Rubik’s Cube, the inverse is the opposite move of what was made. So if I turn the top face right, the Inverse would be to turn the top face left. This would leave us with an unchanged cube, which is what we would get for our Identity element, because doing the inverse is the same as doing nothing.

Example

Consider the set of integers and let us apply the binary operator of addition. Is the set of integers a group?

Rule 1 – Closure – PASS

Any element in the set of integers added to another element within the set will result in an element within the set.

Rule 2 – Associative – PASS

Addition is associative, so this one’s a no brainer.

Rule 3 – Identity – PASS

Zero is the identity element because any element in the set added to zero does not change.

Rule 4 – Inverse – PASS

Every element in the set has an inverse in its negative value, and when added to the element results in the identity element of zero…i.e 4 + (-4) = 0

It would appear the set of integers is a group. We have also shown that the 42 quintillion permutations of a Rubik’s Cube can be considered a group. It is therefore possible to apply Group Theory to the Rubik’s Cube and solve the puzzle.

Let the concept of these axioms set in and in the next article we’ll show how Group Theory lets us understand symmetry in a new way. Take a look at the short video below for a recap on Group Theory and how it not only applies to a Rubik’s Cube, but to music as well.

Sources

Dogschool (this page is old and might crash your browser)

Socratica

12 thoughts on “Symmetry for Beginners – The Rubik’s Cube

  1. Back around 1981 I solved the cube on my own without help from books (there were no websites remember). My process is quite different from the ‘standard’: I solve the top four corners to the center piece, then it’s relatively easy to correct the four “middles”. Then I solve the four bottom corners using a subroutine (right, bottom, -right, front, -bottom, -front) which leaves one corner alone, twists another and exchanges the other two. Then there are two subroutines that can be used to solve the remaining middles: vcenterx2, bottomx2, vcenterx2 which swaps the top and bottom middles facing you with those opposite or rightx2, bottomx2, rightx2 which swaps the right and bottom middles facing you with those opposite.. Usually, a couple of ‘winds’ are needed to get into the position that the subroutines work on, then unwound after the subroutine finishes.

    I remember there are rules for manipulating the cube that correspond to quantum mechanics properties.
    Here’s an article talking about corner cubies’ relationships to quark confinement.

          1. Why should this be a counterpoint? It starts as it should start – with definitions and then move to theorems/lemmata and its proofs. I am unable to make corrections in comments without any tools like LaTex.

  2. A nice, article, but I have to say, if I were not already familiar with group theory the example of it as applied to Rubik’s Cubes would have left me hopelessly confused. This is because of a muddle regarding the binary operation.

    The binary operation is not “turning the top, side, bottom, etc.” it is composition of the elements which are cube arrangements. One can think of each cube arrangement as the list of motions necessary to reach that arrangement from a solved cube. Then if a and b are such cube states a \dot b just means, “do a, then do b on the cube resulting from doing a”.

    Trying to think of the operation as “turning the top, side, bottom, etc.” means that somehow one has to specify which and then maybe a and b end up being different types of things (a might be a cube arrangement and b might be a motion, or something) which would make \dot no longer a binary operation.

    Also you really should mention the binary operation in the paragraph before rule one. A group is both the set and the operation, and in many cases a different operation exists which, when combined with the same set would make a different group.

    The important part is the confusion regarding what the binary operation is though.

  3. Please correct me if I am wrong but …

    1) I thought the “cube” was used as stage prop in magic shows long before “Rubik” decided to patient it.

    2) The figure quoted for permutations comes from Rubik’s fanboys who exaggerate like this – pace the cube face down on the white face there are now 4 permutation to that provision by rotation and even more for the other faces. This may be true in some context BUT if you are taking about symmetry then you are taking about the relationship between piece and not their color so this figure is wrong.

    3) Even doing the cube by symmetry is mind testing. I can to the 3 this way, the four is easier because it is *just* symmetry but I only get the 5 down to one parity error by symmetry (sometimes I luck the whole cube). It is mind blowingly difficult to do a cube by symmetry.

    4) because above, “symmetry” “beginners” and “Rubik Cube” cannot co-exist in the same sentence or you will cause a tear in the time space continuum.

    5) It’s a “Rubik Cube” but I see that even Rubik has given up on that semantic.

    If you are going to buy a “cube” then Rubik makes a “fair” 3 but any bigger is shit from Rubik – buy a speed cube instead.

    The Rubik 4 is worse than the Rubik 5.

    The Rubik 5 has one redeeming property, when it is so worn that it is no longer practical to use then mix it up and throw it at a brick wall and it will explode into so many pixels of color like a real life physics engine failure and this is most satisfying. Just be warned that if you have a hard floor surface then they will travel throughout the house and you will be stepping on little cubes for years to come.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s