Rubik’s Cube and Graphs

Let’s talk about a way to visualize the orientations of the Rubik’s as a graph (the kind with vertices and edges, like the ones shown below). Then, we’ll use this representation to talk about what happens when you repeat a fixed set of moves over and over again on the Rubik’s cube.

The dots labeled with letters are called nodes and the lines connecting the nodes are called edges.

In the case of the Rubik’s cube, each node of the graph represents an orientation of the cube, and an edge connecting two cubes represents the move that takes one orientation to the other. It might be easier to imagine two directed edges (specify at which node it starts and ends) between each node, where the move on one of the edges undoes what the move on the edge in the opposite direction does.

Now, let’s just start picturing what this massive graph looks like. First of all, the graph has over 43 quintillion nodes, since there are roughly that many orientations of the Rubik’s cube. To simplify our graph a little, let’s not allow turns that directly affect any of the center pieces. Let’s also only consider edges that correspond to quarter turns.

At each orientation of the cube, you have 8 different options for how to move to another orientation (since there are four different sections you can rotate and each of them can be rotated two different directions.)

So, imagine building this graph. Out of each node, there are 8 edges. HANG ON… If we did that forever, this graph would have infinitely many nodes! And that would correspond to an infinite number of Rubik’s cube orientations. There ARE a lot of Rubik’s cube orientations, but there are definitely NOT infinitely many Rubik’s cube orientations. So, what does this tell us? It tells us that there must be closed loops within our graph! So, even if you think you’re getting farther and farther away from the correct solution, if you follow some path along the graph, you can only ever get so far away from the node corresponding to a solved cube. Another way of saying that is that given some starting orientation and some ending orientation (our target), there must more than one way of getting from the start to the end!

What else does the loopiness of this graph tell us? Let’s consider a finite set of moves that we repeat over and over again. For example, in Rubik’s cube notation, let’s consider the combination of moves (each letter corresponds to a different twist of the cube, and the prime symbol means turn it the way that’s not implied). Whereas before, each edge of the graph corresponded to a single twist of the cube, now each edge represents multiple twists. But, here’s the crazy thing…this graph will still have loops in it no matter what finite set of moves you repeat! It has to, since the graph has finitely many edges!

This is true because the only option is for it to either visit every node of the graph (orientation of the cube) or eventually come back to the starting orientation before hitting all of them. Since the set of moves you’re repeating is fixed, you’ll never jump around the graph and not get back to where you started.

This is so cool! Given any fixed set of twists of the cube, you know that you can repeat them and eventually get back to where you started!