Puzzles, Groups, and Groupoids

by

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:

Rubik's Cube

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:

Inside of a Rubik's Cube

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:

The Dihedral Group of the 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:

Fifteen Puzzle

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:

Positions and Moves

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:

Groupoid Transformation 1

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:

Comparison of a Group and a Groupoid

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 pP, 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 gG 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:

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:

Moving 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:

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 A_{5}, 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 A_{15}. 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:

Second Step

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:

Fourth Step

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:

Fifth Step

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!

About these ads

Tags:

14 Responses to “Puzzles, Groups, and Groupoids”

  1. John Armstrong Says:

    Those who are interested in the Rubik’s Cube from a group theory perspective might like my series on the subject (arranged, as WordPress does, in reverse chronological order).

  2. Jim Belk Says:

    Indeed. There is also a series of posts at neverendingbooks on the 15-puzzle, the related Conway M(13) puzzle, and a game called Mathieu’s blackjack.

    For those interested in groupoids, I should mention the wonderful AMS Notices article by Alan Weinstein entitled Groupoids: Unifying Internal and External Symmetry.

  3. Simon Says:

    “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.”

    Assuming a solution exists. The configuration of the 15-puzzle has a parity, 0 for an even permutation of 1…15 or 1 for an odd permutation. This parity can not be changed by any move, thus if the puzzle starts in an odd permutation then it can not be solved.
    This is the basis for the $1000 prize offered by Sam Loyd in 1880 to the first person who could solve the 14-15 puzzle. (Which was sold with all numbers in order except 14-15… obviously the prize was never successfully claimed)

  4. lieven Says:

    @jim : very nice post! also, you are more in tune with what students want than i was when i mentioned the 15-puzzle in a group theory course and explained the connection with A(15). all they wanted to knw was how to solve the puzzle… i had simliar experiences with sudoku, they dont want to hear about the symmetries of solutions but rather how to solve and construct sudokus. needless to say that my attemp to use the rubik-cube group as an illustration to the Jordan-Holder theorem also failed… probably ill have to rethink my courses.

    btw. thanks for mentioning the neverendingbooks-series!

  5. Aaron F. Says:

    Oooh, cool! The Rubik’s cube has just become my favorite example of a group of transformations. ^_^ Traditional examples, like symmetry groups, have always disappointed me. The symmetry object is usually presented without color, making it hard to see that the transformations are actually doing anything to it, and is usually such a pointless shape that it’s hard to see why you’d want to do anything to it. The Rubik’s cube, on the other hand, is brightly colored, and lots of people have played with it before.

    The Rubik’s cube might be an especially good example for non-mathematicians in freshman-seminar-type classes. The “math as fun toy” angle is something that I think should be played up a lot more, and the cube could also help students get a feel for the experimental side of mathematics. Is the Rubik’s group commutative? Does it have any non-trivial subgroups? The answers are just a few twists away!

  6. John Armstrong Says:

    Does it have any non-trivial subgroups?

    Tons! In fact, the solution (inspired by Jeff Adams of E_8 fame) I present in the above-linked series of posts works its way down through a tower of nested subgroups, each preserving the structure we’ve already solved, until we get down to the trivial subgroup and the solved cube.

  7. John Baez Says:

    “Usually when someone says “category” I think of something like “topological spaces and continuous functions” or “modules and homomorphisms”.”

    That used to be true for me too. But that’s because the people who first taught us category theory did it in a really obnoxious way… sort of like teaching group theory and starting with this example: “the group of all permutations of the class of all sets” – hard to visualize and mired in set-theoretic subtleties. When we think of a category, we should think of
    something like the 15 puzzle but where we’re not allowed to reverse some of the moves!

  8. Jim Belk Says:

    I partially agree with you.

    There certainly do seem to be a lot of situations where it helps to think of categories as primarily algebraic objects, i.e. as “monoidoids”.

    On the other hand, it certainly helps in understanding fields like algebraic topology or commutative algebra to consider large categories such as Top or Mod(R). Indeed, so many mathematicians study these fields that that there is certainly some merit to focusing on “large” categories in an introduction for graduate students.

    The real problem is that “large category” and “small category” are essentially two different concepts with the same name. Thinking about large categories certainly doesn’t help if you’re trying to understand the meaning of the word “groupoid”. In some contexts, it doesn’t even help you understand what is meant by the word “category”!

  9. John Armstrong Says:

    Here’s the one I always like to start with: matrices. Someone can be a little shaky on thinking of all vector spaces and linear transformations, but they probably have a good idea what a matrix is. So take the objects to be natural numbers and the morphisms from m to n to be m\times n matrices, with matrix multiplication as composition. I think it splits the difference between the abstraction of the big categories and the toylike nature of the small ones.

  10. Micromegas Says:

    “But that’s because the people who first taught us category theory did it in a really obnoxious way…”

    Shouldn’t dwarfs on the shoulders on giants be a little less arrogant?

  11. quotes of the day | neverendingbooks Says:

    [...] a comment over at The Everthing Seminar Shouldn’t dwarfs on the shoulders on giants be a little less [...]

  12. John Baez Says:

    If the people who first taught me category theory had been “giants” in the field, I might have gotten interested in it sooner.

  13. play free online blackjack Says:

    play free online blackjack…

    [...]Puzzles, Groups, and Groupoids « The Everything Seminar[...]…

  14. Скачать оперу мини Says:

    Скачать оперу мини…

    [...]Puzzles, Groups, and Groupoids « The Everything Seminar[...]…

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


Follow

Get every new post delivered to your Inbox.

Join 102 other followers

%d bloggers like this: