Group Theory

Group theory is a branch of theoretical mathematics that can be used to describe the way the functioning of the Rubik's Cube and various related puzzles. Although pure group theory can get extremely complicated (there is one proof, a classification of what are known as simple groups, which took an estimated tens of thousands of pages in its first incarnation) there are several simple applications of group theory to twisty puzzles.

First, we should explain what a group is. A group is nothing more than a set of elements and some binary operation on those elements; so we could make a group out of the set of integers and the operation +. Generally people describe a group just as the set of elements, since the operation is usually obvious from context. A group also has to satisfy several properties:
- Closure: Whenever we apply the operation to two elements in our group, the result is an element in the group.
- Associativity: If a, b, and c are in the group, and * is our operation, then (a * b) * c and a * (b * c) are always the same thing. This means that we can write things like a * b * c * a * c without needing large numbers of parentheses, which is very convenient.
- Identity: There is some identity element, so that if we apply the operation to the identity element and any element a the result will just be a again.
- Inverse: Every element has an inverse in the group, so that if you apply the operation to the element and its inverse it becomes the identity.

This is a pretty abstract concept, but fortunately it isn't too difficult to use. Basically, each puzzle has one group, with the elements being the puzzle's possible positions. Our operation is composition. Basically, suppose we have two elements in the group, A and B. Then A * B is what you get when you take the moves you would use to reach B from a solved cube, and apply them to A instead of a solved cube. This is a very simple and useful operation for several reasons. First, the identity is the solved state, which is easy to work with. Second, if we define a set of basic moves (for example F, R, U, B, L, and D, and their inverses, for a 3x3x3) we can get to every position from the identity using some sequence of these moves, which means that every element in the group can be written as some sequence like F * B * L inverse * D * D, and we can even describe positions by the way that they can be written like this. Third, the inverse of a position is also easy to find: group theory tells us that the inverse of A * B * ... * Z is Z inverse * .... * B inverse * A inverse. Since the inverse of basic moves are basic moves, we can very easily find the inverse of a certain position by just switching the order of the basic moves that bring you to that position and then inverting each one of them. Note that the inverse of the inverse of any position P is just P again.

By the way, since the operation * is always implied, we often write a series of moves in what is called multiplicative notation, where we write the separate moves next to each other without a *, and use exponents (like in algebra) to indicate doing something multiple times or inverting it. This means that we would write something like F B L^-1 D^2 instead of F * B * L inverse * D * D. This is the origin of our modern notational system, which has been simplified so that the inverse sign (which normally looks like a superscript "-1") is changed to a ' and the square sign (a superscript "2") is changed to a normal 2. I believe it was David Singmaster who created the modern Rubik's Cube notation this way. As for my notation system, it works just like this, but includes many more basic moves so that sequences of moves can be written more succinctly.

Along with the concept of a group comes the idea of a subgroup. A subgroup is what you get when you find a normal group and create another group with the same operation but only some of the elements. Because puzzle groups are only finitely large, it turns out that all you need to check to make sure a subgroup is valid is closure, so it's easy to find subgroups. Note that a subgroup always has to contain the identity (solved state). Since we always use the same operation, you can think of a subgroup as basically describing a sub-puzzle of a normal puzzle. A few interesting subgroups of the 3x3x3 are:
- The "two-generator" subgroup, all positions which can be solved using only R and U turns;
- The orientation-only subgroup, positions where all pieces are in place, but can have any orientation;
- The half turn subgroup or square group, positions that can be solved using only 180-degree turns.

The concept of a subgroup is closely tied in with the idea of a generator. A generator for a group is a set of moves or algorithms in that group, so that you can reach any position in the group only using moves or algorithms from that set (or their inverses). * For a given set of moves, there is always some group that is generated by them, that is, some group that contains exactly the positions that you can reach using those moves (in some order and doing them as many times as you want). For any set of moves, say the set R, U, and F2, we write the group generated by them as <R,U,F2>. One particularly famous generated group is a subgroup which we have already discussed: the subgroup of 3x3x3 positions which can be solved using only R and U turns. This is known as the 2-generator group, since it is <R,U>, the group generated by moves of two adjacent faces. Playing with generators can create a lot of new and interesting challenges out of a normally non-challenging puzzle.

Another useful result of group theory is the use of so-called "cycle notation". Imagine a group where, instead of a normal puzzle, you have a bunch of pieces labeled 1 through n, and you can put them in any order (permutation) you want. We can still use the composition operation for this group, and it works a lot like the puzzle groups we have looked at. The question is: how do we represent objects in this group? What we will do is represent a permutation by following where pieces go. Give each piece a spot, labeled 1 through n, which represents its original location; so we can write down a permutation by writing the list of numbers we see, following the locations from 1 to n. So if we have five pieces and the permutation leaves them looking like "3 4 2 1 5" we can use this to represent the permutation. There is a better way, though: instead of just looking at each piece, follow where pieces are actually sent. In this case, the piece that was at position 1 is now at position 4; the piece at position 4 is now at position 2; the piece at position 2 is now at position 3; and the piece at position 3 is now at position 1. We can encode all of this information by writing (1 4 2 3). This is what we call a cycle, and we can imagine making this permutation by simultaneously moving all of the pieces in it to the location where it will go. More specifically this is a 4-cycle, because it has 4 elements. Now what about the piece at position 5? It's still there, and although we could write this as a 1-cycle we usually do not, because that piece doesn't have to move at all. This is really useful, because (1 4 2 3) is a valid permutation for ANY number of pieces, as long as you have at least 4 of them! If we have more than one cycle at the same time, we can write them by writing them next to each other. So if 1 goes to 2 and 2 goes to 1, and 3 goes to 4 and 4 goes to 3, we will write this as (1 2)(3 4).

We call a cycle with n elements an n-cycle. In puzzles we usually consider permutations on the pieces of the puzzle. Because of some more complicated math that will be discussed later, the basic unit that you can use to solve puzzles is the 3-cycle, which moves three pieces around. You may already know a few 3-cycles of pieces on the 3x3x3. Permutations of the pieces, however, is very important in the study of how to solve puzzles, as well as integral to blindfold solving.

There are two last useful mathematical terms which are very useful to understand cubing. They are conjugation and commutation. In conjugation you take two move sequences, which we will call X and Y, and then you make the sequence X Y X^-1. The interesting thing about this is that we end up with the same cycles as in Y, just with different pieces being moved around. You can use this to make other algorithms out of a given one, because the pieces that are moved in the conjugated algorithm are actually the pieces that X puts in the spots Y moves around. Commutation is similar: for two move sequences X and Y the commutator is X Y X^-1 Y^-1. In theory this can make many of the cube's possible patterns, but in practice we mostly use commutators to create nice 3-cycle maneuvers, or to flip/twist two pieces on a puzzle. The way it works is this: have X be a single turn, and then choose Y so that it modifies just one piece on the layer. If Y flips or twists the piece, you will end up with one piece in X's layer flipped/twisted and another flipped/twisted the same amount in the opposite direction. If Y replaces the piece with some piece from another layer, you will end up with a 3-cycle. The really useful thing about commutators is that if you understand them well enough you can literally make up commutators quickly while you are solving a puzzle, and do any 3-cycle you want in just a few seconds.

Well, those are most of the group theory topics you are likely to see. I've tried to explain them simply, but if you don't understand you can look them up on Wikipedia or look for a topic on the speedsolving.com forum. Again, good luck!

Some Basic Vocabulary

There are a lot of terms in the theory of cubing that won't be at all understandable to outsiders, or even that are used in a different way in cubing than in the outside world. I'm going to define some of them; since I have an imperfect memory this list is not complete, but just a list of some things which I think are commonly or easily misunderstood and which I'd like to explain.

Algorithm: This just means a sequence of moves, whether it is made up on the spot or memorized beforehand. The common abbreviation is "alg". Typically it is a sequence that accomplishes something specific (such as solving part of a cube), but people sometimes talk about scrambling algs. A way to solve a specific puzzle is not an algorithm, but a method (see below). Some methods have many algorithms to memorize, and some require less or no memorization.

Bandaged: A puzzle is bandaged if some of its pieces are connected to what would normally be adjacent pieces in a way that restricts the movement of the puzzle depending on where those pieces are, which often increases the puzzle's difficulty. A bandaging is a way of connecting pieces together to make a bandaged puzzle.

Blindfold Solving: This is a way of solving a puzzle by memorizing the positions of all of its pieces, then putting on a blindfold and solving the whole puzzle without looking at it. The typical abbreviation for blindfold or a blindfold solve is BLD. There are really two types of BLD: solving all of the pieces like a speedsolve, and tracking where they go while you memorize, then memorizing what moves to do; or solving a few pieces at a time while not affecting the others, so you can memorize where each piece is supposed to go, which is often easier.

Block: This can either mean a group of adjacent layers on one axis, or a cuboidal set of pieces. A block turn is a turn of some group of adjacent layers. Block building is a type of intuitive step of a method where you assemble a block of pieces.

Center: Any piece which belongs to only one face. Some puzzles have a lot of these on each face, in many different types. Since they have only one color, though, if a puzzle is not a supercube (see below) they can often be interchanged with each other without making the puzzle unsolved. Centers typically do not have orientation, except sometimes on a supercube.

Corner: Any piece which belongs to more than two faces. Corners usually have from two to five possible orientations. Note that trivial tips (see below) are generally not considered corners, though, since they don't affect other pieces and are thus not really part of the puzzle.

Cube: Although formally this means a cubical puzzle, the Rubik's Cube is so popular that people will often casually refer to any twisty puzzle as a cube.

Cuber: Anyone who is interested in solving the Rubik's Cube or other twisty puzzles. If they are also interested in solving as fast as they can, they are a speedcuber.

Edge: Any piece which belongs to two faces. Edges usually have two possible orientations.

Face: One face of the puzzle. A face is solved when all of its stickers match (on a normally-colored cube this would mean they were all the same color). However, solving a face on many puzzles (such as 3x3x3) is useless, since it might still be necessary to permute the pieces on that face in order to solve the puzzle; it is much better to solve in terms of layers or blocks.

God's Algorithm: In general this term means a method to always solve a puzzle in the fewest possible number of moves. However, it can be used in a few different ways: sometimes it means a way to find this solution for any given scramble (or a list of solutions for every scramble), sometimes it means a solution for a given position, and sometimes it is used to mean the maximum number of moves that an optimal solution for a scramble can take.

Intuitive: A step is intuitive if you solve it by figuring out what moves to do during the solve, rather than by using algorithms you know (which is called an 'algorithmic' step). Typically people think of commutators as intuitive, since you don't memorize the moves that are in them, but instead learn the concept. Intuitive steps in a method are good because they require less memorization, take fewer moves, and are generally more fun to execute, but it does take more practice to be fast at them.

Lucky: A solve is lucky if one or more of the steps in the method is skipped; solves can be very easy without being lucky. Note that if a solver uses a different algorithm than normal to deliberately skip a step in their method, most people would say that does not make the solve lucky.

Method: A method is a predetermined way of solving a puzzle in a series of steps. Typically methods are named after their creator(s) or the steps themselves. A method created by Stefan Pochmann might be referred to as the Pochmann method, Pochmann, or even poch; abbreviations are common if the name is long. For example, there is a family of methods called Corners First (CF) because the first step or first few steps solve the corners of the puzzle without regard to other pieces.

Metric: A specific and well-defined way to count the length of an algorithm or a puzzle solution. The most common metrics are htm or ftm (half turn or face turn metric, where every move of one face, or block containing a 1st slice, is counted as one turn), stm or btm (slice turn or block turn metric, where every move of one face, block, or slice is counted as one turn; some would say stm does not count blocks as one move but as separate slices), and qtm (like htm, except that only turns of the smallest valid angle increment (90 degrees on 3x3x3, for example) are counted as one move, and larger turns may be more than one move).

Orbit: This is the set of all pieces that can be moved to a specific location on the puzzle without rotating the puzzle. Sometimes there is more than one orbit of pieces that look the same.

Orientation: The way that a piece is positioned, independent of where it is on the puzzle; you can define a 'correct' orientation for each piece and location. On a Rubik's Cube, for instance, corners have three possible orientations. When you do moves to give a set of pieces the correct orientation, you are orienting them (not orientating). Pieces with the wrong orientation are typically said to be flipped (in the case of edges) or twisted (in the case of corners and centers) and algorithms to solve them are thus called flippers or twisters.

Parity: As I'll discuss later, pieces can normally be solved in cycles of three pieces, but if pieces cannot be solved like this then there is a (permutation) parity. There can also be orientation parities, if only one piece in an orbit is wrongly oriented, but these do not occur on all puzzles. The algorithm to fix any parity without disturbing other pieces is typically very long.

Permutation: Where a piece is on the puzzle, independent of the way it is positioned; if a piece is in the correct permutation it might still be misoriented (twisted or flipped). When you do moves to give a set of pieces the correct permutation, you are permuting them (not permutating).

Slice: One of the layers on an axis, not counting the outermost layer. A slice turn (or sometimes just slice) is a turn of one of these layers only.

Supercube: A puzzle where some or all pieces are marked so that the position and orientation of every piece must be correct for the puzzle to be solved.

Trivial tip: A piece on the puzzle which can always be brought to its solved position in one move without disturbing any other pieces; they are called trivial because they are so easy to solve that they are often not even mentioned in methods. They are also known as tips. A pyraminx has four of these.

Twisty puzzle: Basically a sequential move puzzle where the goal is to turn various parts of it until it reaches one of its solved states. A pretty good list can be found at the twistypuzzles.com website. These are often simply referred to as puzzles, or even cubes.

Notation

In this post I'll describe my generalized notation for twisty puzzles. I might stray from this notation at times but I think this does a pretty decent job of describing moves for puzzles. There are a few levels of notation built on each other, and although it might seem overcomplicated most applications of this (such as writing down specific algorithms) only use simple features of it: for example, the well-known Sune algorithm for the 3x3x3 is still written R U R' U R U2 R'.

Not all of this will necessary make sense or seem useful to you now. However, if I use some notation that you are not familiar with, it would be helpful to come back to this post as a reference.

First you give each face of your puzzle a letter (or more than one if you are careful about it). Fortunately, for algorithms on dodecahedral and icosahedral puzzles, you usually don't have to label all of the faces. The standard naming for cubical puzzles, which you have probably seen before if you are into speedsolving, is to call the faces U (for the upper face), D (for the down face), F (for the front face), B (for the back face), R (for the right face), and L (for the left face). Typically if you see three faces in a shot of a cube they are assumed to be U, F, and R. I'll assume that you know what faces I am using when I talk about cubical puzzles, but if I am discussing a different puzzle I'll probably describe how I am naming faces or at least make it so that you can determine the meanings from context.

Now you can label the axes that you turn pieces around. There are three types of axes: faces, edges, and corners. Check out the puzzles at gelatinbrain if you aren't entirely sure what this means; the most common puzzles with various axes are the Rubik's Cube (face), Bevel/Helicopter Cube (edge), and Pyraminx (corner). Face axes are labeled by their face, edge axes are labeled by the two faces they touch, and corner axes are labeled by the three faces they touch; the face's names can be in any order, but they should not have spaces between them. This means that if you see an axis label (say UF on a 3x3x3) you should be able to quickly determine what type of axis it belongs to, so this notation can still handle puzzles with more than one type of notation.

Finally, we get to the turns themselves. Turns are all around an axis, so you should modify the following basic types of turns based on the axis. For the examples I'll use the axis UR. We're going to suppose there is more than one slice around the axis (like in big cubes) for the purpose of the notation. Label the slices with integers starting at 1 for the outermost slice and ascending as you move deeper into the puzzle. There are five types of moves; all moves are clockwise turns as seen from a vantage point outside the puzzle.
- 3UR is a clockwise turn around the UR axis, turning the 3rd slice only (a slice turn). If the number is 1 (1UR) then it is allowed to just omit the 1, since this is a very common type of move.
- 3ur is a clockwise turn around the UR axis, turning all slices up to the 3rd slice (a block turn). If the number is 2 (2ur) then it is allowed to omit the 2, since this is the smallest block turn that can't be just written as a slice, and is also very common.
- 2-4ur is a clockwise turn around the UR axis, turning slices from the 2nd to the 4th (a block turn). This isn't a common type of move, but it's useful for writing patterns in block turn metric.
- *ur is a clockwise turn around the UR axis, turning basically half of the slices on the UR axis (and its opposite axis) rounded down. On a 4x4x4 or 5x5x5 cube this would be 2 slices; on a 6x6x6 or 7x7x7 it would be 3. Note that since it is lowercase it should be a block turn. This is useful for writing algorithms in a more general form.
- cUR is a clockwise cube rotation around the UR axis. Note that it's unambiguous because having lowercase and uppercase letters together is unique. Observe that sometimes we might need cube rotations around axes that you can't turn; for example on a 3x3x3 cube sometimes a rotation like cURF is useful.

Separate moves should always be written with spaces separating them. A group of moves can be enclosed with parentheses (i.e. ( and )). You can modify a move or a group of moves by putting a number after it (to indicate it is to be done that many times) or a ' (to indicate that its inverse is to be performed instead). Thus combinations such as 3UR' and r2 are possible. If we want to use both of these, either R2' or R'2 is acceptable, but personally I will tend to use R2' because I like it more.

Rarely, in generalized patterns or commutators, variables are needed to show that any slice or any amount of turn can be used. Typically any letters that are not in use to describe axes are acceptable. As in the notation we have already seen, if a variable is placed before the axis name (such as nr) it describes a slice number, and if a variable is placed after (such as Rx) it describes a number of times a turn should be done.


Finally, I'd like to say that it's true that this notation differs a bit from the conventional notation, especially when it comes to large NxNxN puzzles (bigcubes, that is), but I think that it is better generalizable to other puzzles and more consistent than the standard notation. Moves such as (rm') or Rw, as written in standard notation, are difficult to expand to different puzzles and often unwieldy. I hope my notation is reasonable enough to be understood by most visitors here.

Introduction

This is a blog about twisty puzzles themselves. I aim to explain the way they work and the way they are solved so that the reader should eventually gain a deep understanding of the way these puzzles work, a thing which is sadly lacking in many of today's speedcubers. I also hope to put some of the methods I use or have discovered on here. Some of the material here might be original research and some may not; it's safe to assume that I've created anything that I explicitly credit to me, but I don't necessarily claim authorship of all that I write here.

The first couple posts will probably concern themselves with the mathematics of the cube, to get a feel for why things work as they do. Although I'm considering majoring in Math I'm not going to be too formal or theoretical, so anyone with an early high school understanding of mathematics (or better) should be fine. Then after that I'll start to go into the more interesting stuff, or perhaps some more complicated mathematics. Don't think of this as a kind of textbook where every section builds on the one before it: the material in these opening sections should be enough to understand all or most of the rest. If you are confused about something you can always ask me, or the friendly folks on speedsolving.com.

So what's with this name "Notes on Twisty Puzzles"? It is based off of the title of an early Rubik's Cube treatise by David Singmaster which he called "Notes on Rubik's Magic Cube" and which was a great leap ahead in understanding how the standard 3x3x3 cube works. Despite not having read his books about the Cube I do recommend that you read them if you have a chance, as I've heard they are excellent.

Finally, all opinions expressed herein, and all writing, are mine unless stated otherwise. Opinions can and do change, so if you have a problem with anything here feel free to tell me about it.

Have fun, and good luck!