Solving the Rubik’s cube using group theory

Do you remember the time when everyone was so obsessed with solving the cube? We used to have numerous competitions to see who could do it fastest, and being able to solve it swiftly, earned you a little extra respect from all your friends (who didn’t know the trick).

All the cube solvers would know that we generally follow an algorithm to solve the cube. We have a list of possible states of the cube, and then we choose an algorithm to follow, based on which state it is in. (As you probably have figured by now, I too once was mesmerized by that colorful puzzle.)

In this article, we will be looking into why this works mathematically.

What is used here is something called group theory. Let us look into what group theory actually is, and how it can be used here :)

So what is a Group?

Let us first look at some examples before we go into the definition of a group. Mathematicians came up with groups with the aim to classify symmetries. These could be for any shape, 2-D or 3-D or even more! The actions that maintained the shape were all put into a structure, we call a group.

• Let us understand one specific such group, called a dihedral group.

Consider a square. Observe that the set of rotations by 90°, 180°, 270° and 360°, along with reflection about its axis of symmetry, does not change the orientation of the square. Through these operations, we can generate 8 squares, as given below. These together form a group which is commonly known as the dihedral group (Dn), with n=4.

We can have similar groups for other regular polygons like triangles or pentagons.

• Let us now try to arrange 3 distinct objects in a specific order. We can see that there are a total of 6 ways to arrange them.

Together these permutations form a group. Each element of the group is a bijective function from {1,2,3} to {1,2,3}

Similarly we have groups for any number of distinct objects, and the group for n objects is called Sn. These groups are of special significance as they contain all the other finite groups in them. Also, using these groups we can show that while we have expressions for the solutions of polynomial equations up to order 4, we do not have such an expression for a fifth order polynomial. Feel free to check out the youtube video in the references for a better understanding!

• Now let us see how a group is defined. A group is simply a set, with a binary operation(⋅). The binary operation along with the set, follows some properties, like closure(if a and b are in the group, then a⋅b is also in the group) and associativity(for a,b,c, elements in the group, a⋅(b⋅c)=(a⋅b)⋅c). Additionally, the group has an identity, which when operated with any element, gives back that element. Also, every element has an inverse, which when it is operated with, we get the identity. Note that in a group, the identity element is unique, and for each element there is a unique inverse.
• Another example of a group is all the integers, with + as the operation. Note that here the identity will be 0, and the inverse for any element, x, will be -x. Groups are abstract, and they are used in mathematics to study various other things, as they have a particular structure, which we can use to characterize them.

How are we using groups here?

In the case of solving a Rubik’s cube, we create a group, containing the possible moves as the elements. The group would contain R(right), L(left), U(up), D(down), F(front) and B(back), which tell us which face to rotate. We will fix the direction of rotation, say as clockwise. Then using the inverses of these elements, we can represent anti-clockwise rotation. Each of these elements changes the position of some of the cubicles on the cube. We can easily observe which cubicles go where for each of the operations.

In this group, our binary operation will be composition. So, what we do is we compose multiple moves in a particular order. And since we know what each move does to the cubicles, using that, we can deduce where each cubicle goes after the composition of some elements.

Now, usually, the cube is solved layer by layer, which means that first we solve it such that all the colors in one layer are in sync, then we do the same thing for the second layer, then we finally solve the third layer and we are done.

One challenge we face is that when we decide which elements in which order we want to compose for the first layer, it is fairly easy, because we need to worry about only where those 9 cubicles move. The other cubicles will also change positions in the process, but we don’t really care about them when we are solving for the first layer.

This becomes a problem for the subsequent layers, because we need to ensure that the first layer stays intact when we are solving the second layer, and the first and second layers should stay intact when we are solving the third layer. This puts extra constraints on our algorithm, i.e., on the elements we compose to achieve the desired output. Hence as we decide which movements to do when solving a layer, we need to keep in mind how all the cubicles are moving. The group theory abstraction of the moves in a cube helps us to do that efficiently.

If you are interested in details of how the group looks and how the elements look, or if you want to see how simple (or complicated) the algorithm really is, I would encourage you to check out the paper given in the references, by Courtney Cooke, Rhode Island College!

References:

Group theory, abstraction, and the 196,883-dimensional monster (youtube.com)

https://digitalcommons.ric.edu/cgi/viewcontent.cgi?article=1164&context=honors_projects

Counting Methods, Permutations, and Combinations (gmatfree.com)

This article is based on a project offered by Stamatics, IIT Kanpur, in 2023, ‘Solving the Rubik’s Cube using Group Theory’.