Puzzles, Groups, and Groupoids

Over at Good Math, Bad Math, MarkCC has a nice post introducing groupoids which uses the fifteen puzzle as an example. I like this example a lot, and I thought it would be interesting to expand on it a bit. So I’m going to tell you:

1. Why the Rubik’s Cube is a finite group,
2. Why the fifteen puzzle is a finite groupoid, and
3. How to solve the fifteen puzzle.

I’m not going to assume any knowledge of groups or groupoids, but if you don’t know much group theory, you’ll have to skip over certain parts of the second half.

The Rubik’s Cube

You’ve probably played with a Rubik’s cube at least once:

Each face of the cube is cut into nine pieces, which are colored red, orange, yellow, green, blue, or white. The goal is to rotate the sides of the cube until all of the faces are a solid color.

The first thing to realize about a Rubik’s Cube is that the squares in the centers of the six faces are fixed. They turn in place when you rotate the sides, but otherwise they don’t really move. In fact, if you take a Rubik’s cube apart, you will see that these six squares are connected to three axles along which the faces rotate:

Because the center squares are fixed, we can assign names to the six sides of the cube. For example, the front of the cube can be the face with a red square in the center, the top of the cube can be the face with the green square in the center, and so forth. Understanding this idea is the first step in understanding most solutions.

Moves and Transformations
I’m not going to go into detail on exactly how to solve a Rubik’s cube. Instead, I’d like to explain why the Rubik’s cube fits into a part of mathematics called group theory.

First we need some terminology. When manipulating the cube, a move is any 90-degree clockwise rotation of one of the faces. There are six possible moves, which we will label according to the face that was rotated:

Left, Right, Top, Bottom, Front, Back

Any sequence of moves gives a transformation of the cube. For example, one way to transform the cube is to first rotate the Front face, then rotate the Right face, and then rotate the Back face twice:

Front · Right · Back · Back

Two transformations are equal if they always have the same effect on the cube. For example, if you want to rotate the front and back faces, it doesn’t matter which order you do it in, so:

Front · Back = Back · Front

also, if you rotate any face four times, you always get back to where you started:

Left · Left · Left · Left = Doing Nothing

Note that “Doing Nothing” is considered a transformation of the cube. It is called the identity transformation.

The Rubik’s Cube Group
In total, there are 43,252,003,274,489,856,000 different possible transformations of the Rubik’s cube, and together they form a mathematical object known as a group. From a mathematician’s point of view, understanding the Rubik’s cube is the same as understanding its transformation group.

Roughly speaking, a group is any collection of transformations of an object, subject to the following requirements:

1. If you compose two transformations (i.e. perform one and then the other), the result is also a transformation.
2. Any transformation can be undone by some other transformation.

To clarify the idea of a group, I’d like to give two more examples. The first is the sixteen possible transformations of an octagon:

Each stop sign above illustrates one transformation. The first illustrates the identity, or “Do Nothing” transformation; the others on the top row represent rotations, while those on the bottom row represent reflections. Together, these sixteen transformations form a group, namely the dihedral group of the octagon. Dihedral groups are important in chemistry, where they describe the symmetries of certain crystals.

Another example of a group is the set of all possible rotations of a sphere. Because you can rotate a sphere about any axis, and through any angle between 0 and 360 degrees, this group consists of infinitely many different transformations. The rotation group is very important in physics for studying angular momentum and the motion of rigid bodies.

The theory of groups is large and important subject in modern mathematics, with many applications to physics, chemistry (especially the study of crystals), and so forth. Most undergraduate math majors take a course in group theory, but often the theme doesn’t come through clearly enough: group theory is nothing less than the mathematical study of symmetry.

The Fifteen Puzzle

The picture below shows the fifteen puzzle. Fifteen numbered squares are arranged on a 4×4 grid, with one square missing. Usually the squares are jumbled, and the goal is to slide the squares around until you manage to put them in numerical order:

You can play the fifteen puzzle online here.

If you want to solve the fifteen puzzle, the most important thing to realize is that the blank square is the one that moves. For example, if you want to move a certain piece to the right, the thing to do is move the blank square until it lies to the right of the piece, and then move the piece. Try using this technique to put the 1, 2, and 3 into the correct positions in the online game. (After you position the 1, 2, and 3, it’s a bit harder to position the 4 correctly. See the solution below.)

Mathematically, the fifteen puzzle is similar to the Rubik’s Cube: the goal is to arrive a certain position by performing the correct sequence of moves. However, unlike the Rubik’s cube, the available moves depend on the current position. For example, if the blank square is in the upper-left corner, it can only be moved right or down.

The following picture shows the sixteen possible positions of the blank square and the moves between them:

Transformations of the Fifteen Puzzle
You can transform the fifteen puzzle by performing a sequence of moves. For example, if the blank square starts in the lower right (position 16), you can move it Up, Left, Up, Right, and Down. This is called a transformation:

16 → 12: Up, Left, Up, Right, Down

The “16 → 12” indicates that the transformation begins at position 16, and ends at position 12. This transformation has the following effect on nearby pieces:

Two transformations are equal if they have the same starting and ending positions, and they effect the numbered pieces in the same way. In total, there are 167,382,319,104,000 different transformations of the fifteen puzzle.

The Transformation Groupoid
Unlike the transformations of the Rubik’s cube, transformations of the fifteen puzzle cannot always be composed. Specifically, you can only compose two transformations if the ending position of the first is the same as the starting position of the second. For this reason, the transformations of the fifteen puzzle are not a group — instead they form what’s called a groupoid.

Roughly speaking, a groupoid consists of:

1. A set of possible positions, and
2. A collection of transformations

Each transformation has a starting position and an ending position. The transformations are subject to the following requirements:

1. If you compose two transformations (i.e. perform one and then the other), the result is also a transformation. However, you can only compose two transformations if the ending position of the first is the same as the starting position of the second.
2. Any transformation can be undone by some other transformation.

A group is a special case of a groupoid: groups are groupoids that have only one position. The following picture illustrates the difference:

Formal Definition
For those of you who like rigorous mathematics, I should probably give a formal definition of a groupoid. Just skip over this part if you’re not used to formal mathematical language.

Definition. A groupoid consists of:

1. A set P of positions,
2. A set G of transformations,
3. A pair of functions start: G → P and end: G → P, and
4. A partially defined binary operation G × G → G.

subject to the following requirements:

1. The product g · h is defined if and only if end(g) = start(h).
2. If g · h and h · k are both defined, then g · (h · k) = (g · h) · k.
3. For every position p ∈ P, there exists an identity e(p) ∈ G, which starts and ends at p. This element satisfies g · e(p) = g for any g that ends at p, and e(p) · h = h for any h that starts at p.
4. For any g ∈ G starting at p and ending at q, there exists an inverse h starting at q and ending at p, such that g · h = e(p) and h · g = e(q).

If you know what a category is, a groupoid is just a category where every morphism has an inverse. However, I always feel like this statement is a little bit misleading: usually when someone says “category” I think of something like “topological spaces and continuous functions” or “modules and homomorphisms”. When someone says “groupoid”, I think of the fifteen puzzle. In this respect, groupoids are much more like groups than they are like categories.

By the way, I once had a friend who knew what a groupoid was, but not a category. When I explained the definition of a category, his face lit up, and he said, “Oh, it’s just a monoidoid!”

The Fifteen Puzzle Group

Now that I’ve explained why the fifteen puzzle is a groupoid, I’d like to backpedal and explain how it’s still possible to view it as a group. In fact, it’s possible to view any groupoid as a group: the secret is to ignore all but one position.

Let me start by explaining it for the three puzzle:

This puzzle has only four positions for the blank square, and the only productive activity is to move it around in a circle:

As you can see, a complete revolution of the blank square rotates the positions of three numbered pieces. If we think of this as a single move, then our understanding of the three puzzle becomes a lot simpler: all you have to do to solve the puzzle is rotate the pieces into the correct place. By focusing on the position where the blank square is in the lower-right corner, we have simplified the groupoid into a group with three elements (namely the identity, the rotation 1 → 2 → 3 → 1, and the rotation 1 ← 2 ← 3 ← 1).

Now let’s do the five puzzle:

If we focus on the position where the blank square is in the center bottom, there are two obvious moves available: we can move the blank square around the left half of the puzzle, or around the right half. The first rotates the pieces in postions 1, 2, and 3, while the second rotates the pieces in positions 3, 4, and 5. These generate a group of 60 transformations, all of which start and end with the blank square in the center bottom position.

You can learn about this group by playing the five puzzle (set the applet to two rows and three columns). It really is helpful to keep the blank square in the bottom center, and to use the two rotations as basic moves.

Incidentally, if you know about permutation groups, observe that the five puzzle is really just the group of permutations of the set {1, 2, 3, 4, 5} generated by the rotations 1 → 2 → 3 → 1 and 3 → 4 → 5 →3. These two permutations generate the alternating group , i.e. the group of all even permutations.

In general, given any groupoid G of transformations, you can get a group from G by focusing on all of the transformations that start and end at a certain position. It doesn’t matter which position you pick — different positions give isomorphic groups. (Strictly speaking, this is only true if the groupoid is connected, meaning that there is at least one transformation between any two positions.)

For the fifteen puzzle, any fixed position for the blank square gives you a group of 15!/2 = 65,383,7184,000 different transformations. This is the alternating group . Unfortunately, the fifteen puzzle doesn’t have a simple set of “moves” based at a certain position like the five puzzle, so we’ll need to look elsewhere for a good strategy.

How to Solve the Fifteen Puzzle

Our strategy will involve the solutions to the three puzzle and the five puzzle. If you haven’t figured out the five puzzle yet, you should play using this applet until you understand how it works. (Remember: start with the blank square in the bottom center, and use the two rotations to move the numbered pieces.)

OK, here’s the solution to the fifteen puzzle:

1. First put the 1 and 2 into the correct places.

2. Now move the 3, the 4, and the blank square close to the upper-right corner, like this:

Move the blank square around the red box to put the 3 and 4 into place.

3. Use the same process to place the 5, 6, 7, and 8.

4. The final two rows are more tricky. To start, move the 9 and 13 near the lower left corner. It doesn’t matter exactly where:

Play the five puzzle inside the red box to put the 9 and 13 into place.

5. Finally, play the five puzzle in the lower right to place the remaining pieces:

That’s it. It’s not the fastest solution possible, but it should let you solve the fifteen puzzle consistently within two or three minutes. Enjoy!

Tags: math.GR