No theory in this article, it's just a proposal I've been thinking of but don't have the skills to program. I've never seen this in practice, but it was an idea I had a while ago and which I'm sure a lot of other people have had independently. It ought to be written up, though...
The thing that inspired this was the realization that people look to the unofficial world record (UWR) pages on speedcubing.com as a reference, but that many fast people don't post their times at all, so they are clearly not representative. I've often heard the excuse that the official times are the only times that matter, but the fact is that most events and puzzles do not have any official counterpart and the only way to compare times on them is through an unofficial list of this sort.
It seems to me that this would solve this problem, plus many additional ones which I'll talk about later. The basic idea is to have a forum where users enter their unofficial personal best times. The times would then be organized in a list in their profile, and there would also be a UWR section which would automatically sort and display the times that users have submitted. Ideally it would be very easy to submit times, so that people would grow used to submitting new PBs as often as they post in Accomplishment threads. A timer could also be added, and then users' single and rolling average-of-12 times could even be automatically updated when they finish a session. From a database point of view it would be a relatively simple addition to the forum system. The way I would do it would be to take a working forum and then add the databases of records and categories; then we would just have to make a way to submit records, display them in people's profiles, and display them in the UWR format. Other additions such as timers or a compare-users function would just involve different ways of interacting with this system.
This doesn't sound like that much of an improvement over a forum like speedsolving.com, but it would solve a lot of problems. There wouldn't be many problems with fake times (like there apparently are on the UWR list) because the mods could simply delete or ban the offending account. Signatures wouldn't need to contain people's best times because they would be easily found in the user's profile. Nothing would have to be manually updated on the unofficial record list, so whenever someone updated their time or e-mail the list would update, and you'd never have duplicate entries. Similarly it would be easy to add new events: you could allow people to create their own events, with certain restrictions, and perhaps show all events with at least two people in them. Since the UWR list and forums would be on the same website, it would be a lot easier to compare people, and you could even have a function which takes two users and compares all of their personal records automatically. You'd also end up with an account for everyone who wants to be on the unofficial list, which means that the community could be more organized than ever; it wouldn't be much of a problem to make different forum sections for people from different countries or people who speak different languages, and perhaps eventually everyone could be using the same website as their speedcubing community (rather than having speedsolving.com for most English-speaking people and then a bunch of other separate websites for various other languages or countries). This would also be a very convenient centralized place for people to talk about their records, since it would all be on one site.
The question is, though, should everyone move from speedsolving or wherever to use this? I kind of think that we should agree on some kind of website that would satisfy all of our needs as a community for the next few years. Cubing is definitely not dying down; in fact it is picking up faster and faster, and I think it's about time we become very organized with the community. Speedsolving is a pretty good forum but it has a big problem with posting times: people can't really display much of their accomplishments because of small signatures, so you have to already know who people are in order to figure out who's amazingly fast. In fact some of the faster people I know don't even know what their best times are, which seems kind of odd given that so many other people want to know that. This tells me that more organization is needed. There's also a problem of lots of smaller, regional cubing forums; this means that the community isn't all in one place, so it can be tricky to find someone who isn't on speedsolving, and if something is posted in one place it won't necessarily reach everyone. So I figure we could use this kind of certainty.
The last thing I think I should say is that, once we are sure we have a forum that will satisfy everything we want, moving to it won't be that hard. Initially you will have people using the old and new system concurrently, but eventually the old system will just become an archive of past cubing discussions. This seems to be the eventual fate of the speedcubing Yahoo group, which was replaced by speedsolving because the Yahoo group message system is much less convenient and organized than the forum system. I am pretty sure that, if a community website can be made which is clearly superior to the existing community forums, we will eventually have everyone in the new website, and it will be much easier to share records and ideas. It will definitely take a while to program and perfect this, but I think that if we use lookahead we can see that it will be well worth it in the long run.
20080511
Number of Positions of Generalized Twisty Polyhedra
I wrote this on 3/30/08.
The goal of this article is to determine the number of positions of various twisty polyhedra. I will first show an algorithmic theory where we can find the number of positions in well-behaved twisty polyhedra (that is, puzzles which are symmetrical and have no move constraints based on the position) without difficulty, and then use it to find the number of positions in a few infinite families of theoretical twisty polyhedra, and a few examples of how to modify this theory for trickier puzzles.
Theory of Positions
Before we start determining the number of positions of a puzzle we must fix the orientation somehow. This is necessary since simply turning a puzzle around without doing moves on it will not change its position. The normal way to do this is to fix one specific piece, or a set of pieces which are fixed relative to one another. If this is impossible we can divide the number of positions we calculate later by the number of possible positions of a solved puzzle (most usually 12 for a puzzle with tetrahedral symmetry, 24 for a puzzle with cubical or octahedral symmetry, or 60 for a puzzle with icosahedral or dodecahedral symmetry) but it is not certain that this will give us the correct result. Note, however, that if we have a few choices for what piece to fix, you will get the same answer no matter which piece you choose.
After this the first step to finding the number of positions of a twisty puzzle is to determine the orbits. An orbit is the set of positions that a given non-fixed piece can be in, and orbits containing the same positions are considered the same. In a 3x3x3 cube we will typically fix the orientation by forcing the centers to be in specific places; then there are two orbits, one for the 12 edges and one for the 8 centers. Note that there can be more than one orbit containing similar-looking pieces; for example on the 3x3x3 square group (where only half turns can be used) there are in fact three edge orbits and two corner orbits.
In general we will proceed by finding the number of positions in each orbit and multiplying them together. Because of parity concerns, the best way to do this is to order the orbits in some way and consider them one by one, assuming that while considering one orbit all pieces in the previously considered orbits are solved. This way, when two orbits have the same parity, we see that one does not obey a parity constraint and the other does, so we correctly divide by 2 only once.
So how many positions are in a single orbit? This is generally an easy problem, as it can be directly calculated with a little casework. First we consider the permutations. If there are n pieces, we start with n!; if there are n pieces each of k types, as in the centers of a higher-order Rubik's Cube, we start with (nk)!/n!^k. If the pieces of the orbit have to obey a (permutation) parity constraint then we divide by 2; note that this is only possible in the first type because if we have indistinguishable pieces we can always make a 2-cycle of same-colored pieces to cancel out a wrong parity. Next we consider the orientation of the pieces. If the pieces cannot be oriented differently when they are in a given position we do not have to consider orientation and we can just multiply by 1. Otherwise, if we let k be the number of possible orientations one piece can have if it is a given position and n be the number of pieces then we should multiply by k^n. If the pieces of the orbit obey an orientation parity, we divide by its order, which is generally 2 or 3 but can be higher.
Let's work through an example to illustrate the technique: the 3x3x3 cube. As I already mentioned, if we fix the orientation by fixing the centers' positions, we have two orbits: edges and corners. First we'll consider edges: there are 12 pieces (12!) with no parity (since corners are unknown), and each has an orientation of order 2 (2^12) with an orientation parity (/2), so the total number of possibilities here is 12! * 2^11. Then we consider corners: there are 8 pieces (8!) with parity (/2, since edges are fixed), and each has an orientation of order 3 (3^8) with an orientation parity (/3), so the total number of possibilties is 8!/2 * 3^7. Thus the total number of positions is (12! * 2^11)(8!/2 * 3^7) = 43252003274489856000, as I'm sure you already know.
Number of Positions of Infinite Families of Twisty Polyhedra
The most important concept here is that of layers. It is difficult to put into words, but the number of layers of a puzzle is basically the number of parallel, twistable slices (not counting slices on the opposite side of the puzzle's center). Puzzles with one layer include the 2x2x2, 3x3x3, Megaminx, and Dino Cube; puzzles with two layers include the 4x4x4, 5x5x5, Gigaminx, and Lattice Cube. A family of puzzles is basically a set of puzzles that function similarly (have the same axes, the same fixed pieces, the same shape, and so on), but which differ in the number of layers, a constant which I will call n throughout the rest of the article. I don't count 'trivial tips' (twistable elements of a puzzle which do not affect any other elements, are not affected by any other elements, and can always be solved in one move) as layers, because they do not share any pieces with the rest of the puzzle; thus, although most families only have twistable puzzles for n >= 1, there are some families where the case for n = 0 has more than 1 possibility.
There are many families of puzzles; however, most families have only had one puzzle constructed or even considered, and there are other families (such as stacked pucks and 2x2x(2n+1) cuboids) where adding one layer simply multiplies the number of combinations by a fixed amount. In this article I will only consider the number of combinations for families of which at least two puzzles have been constructed or designed. Of course, these are the most popular families to consider. All numbers I give have been calculated using the formula given here.
Odd NxNxN Cubes: Just like the 3x3x3, we will hold the centers constant. Then our orbits are: 12 edges with 2 orientations each (12! * 2^11), 8 corners with 3 orientations each (8!/2 * 3^7), n-1 orbits of 24 edge wings ((24!)^(n-1)), and n^2-n different orbits of 24 centers, all of which are made up of 4 pieces each of 6 types ((24!/4!^6)^(n^2-n)). Thus the total number of positions is 12! * 8! * 24!^(n^2-1) * 4!^(-6n^2+6n) * 2^10 * 3^7. For this family the existing puzzles are n=1 (3x3x3, with 4.325 * 10^19 positions), n=2 (5x5x5, with 2.829 * 10^74 positions), and n=3 (7x7x7, with 1.950 * 10^160 positions).
Odd NxNxN Supercubes: This is like the odd NxNxN cubes, except that there are much more parities since the center pieces have no duplicates, and also the centers have orientation. Again keep the centers fixed, then the orbits are 6 centers with 4 orientations each (1 * 4^6), 12 edges with 2 orientations each (12!/2 * 2^11), 8 corners with 3 orientations each (8!/2 * 3^7), n-1 orbits of 24 edge wings ((24!)^(n-1)), and n^2-n orbits of 24 centers ((24!/2)^(n^2-n)). So the total number of positions is 12! * 8! * 2^(-n^2+n+21) * 3^7 * 24!^(n^2-1). The puzzles that have been made so far are n=1 (3x3x3 Supercube, with 8.858 * 10^22 positions) and n=2 (5x5x5 Supercube, with 5.289 * 10^93 positions).
Even NxNxN Cubes: We can't hold centers constant, because there are no centers, but if we fix one specific corner we will always be guaranteed a fixed orientation. So our orbits are: 7 corners with 3 orientations each (7! * 3^6), n-1 orbits of 24 edge wings ((24!)^(n-1)), and n^2-2n+1 orbits of 24 centers, each of 4 pieces in 6 colors ((24!/4!^6)^(n^2-2n+1)). The total number of positions here is 7! * 24!^(n^2-n) * 4!^(-6n^2+12n-6) * 3^6. The puzzles in this family that have been constructed are n=1 (2x2x2, with 3.674 * 10^6 positions), n=2 (4x4x4, with 7.401 * 10^45 positions), and n=3 (6x6x6, with 1.572 * 10^116 positions).
Even NxNxN Supercubes: This is very much like the odd NxNxN supercubes. Keep a corner fixed, and our orbits become 7 corners with 3 orientations each (7! * 3^6), n-1 orbits of 24 edge wings ((24!)^(n-1)), and n^2-2n+1 orbits of 24 centers, all with parity ((24!/2)^(n^2-2n+1)). So the total number of positions is 7! * 24!^(n^2-n) * 3^6 * 2^(-n^2+2n-1). The existing puzzles are n=1 (2x2x2, with 3.674 * 10^6 positions) and n=2 (4x4x4 Supercube, with 7.072 * 10^53 positions).
Megaminx Family: These puzzles work just like the odd NxNxN cubes, except with larger numbers of pieces in each orbit. However, in these puzzles all turns create 5-cycles, so every orbit has a permutation parity. There are 30 edges with 2 orientations each (30!/2 * 2^29), 20 corners with 3 orientations each (20!/2 * 3^19), n-1 orbits of 60 edge wings ((60!/2)^(n-1)), and n^2-n orbits of 60 centers, in 12 colors of 5 pieces each ((60!/5!^12)^(n^2-n)). So the total number of positions is 30! * 20! * 60!^(n^2-1) * 5!^(-12n^2+12n) * 2^(28-n) * 3^19. The existing puzzles are n=1 (Megaminx, with 1.007 * 10^68 positions) and n=2 (Gigaminx, with 3.648 * 10^263 positions).
Pyraminx Family: These puzzles are slightly more tricky to calculate since some of them have middle centers (where there are only 4 pieces instead of 12) and some do not. I am not including the trivial tips in the calculation because they are not an inherent part of the puzzle, but of course to put them back in we can just multiply by 3^4. In this puzzle we are keeping the corners in the same position, although their orientation can change. Note that, just as in the Megaminx family, all turns create even permutations, so every orbit has permutation parity. In this family our orbits are 4 corners with 3 orientations each (1 * 3^4), 6 middle edges with 2 orientations each (6!/2 * 2^5), n-1 orbits of 12 edge wings ((12!/2)^(n-1)), a total of floor((n-1)^2/3) orbits of 12 centers, in 3 centers for each of 4 colors ((12!/3!^4)^(floor((n-1)^2/3))), and ((n-1)^2 mod 3) orbits of 4 centers ((4!/2)^((n-1)^2 mod 3)). Thus the number of positions is 6! * 2^(5-n-((n-1)^2 mod 3)) * 3^4 * 12!^(n-1+floor((n-1)^2/3)) * 3!^(-4floor((n-1)^2/3)) * 4!^((n-1)^2 mod 3). The existing puzzles are n=1 (Tetraminx, with 9.331 * 10^5 positions), n=1 with tips (Pyraminx, with 7.558 * 10^7 positions), and n=2 with tips (Master Pyraminx, with 2.172 * 10^17 positions).
Magic Octahedron Family:This family works just like the Pyraminx family, but now there are parities involved with some of the edges since a turn creates edge 4-cycles. Again, we want to fix the corners, and we're not going to fix the tips. The orbits are 6 corners with 4 orientations each (1 * 4^6), n-1 sets of 24 edge wings ((24!)^(n-1)), one orbit of middle edges (12!/2 * 2^11), a total of floor((n-1)^2/3) orbits of 24 centers, 3 each in 8 colors ((24!/3!^8)^(floor((n-1)^2/3)), and ((n-1)^2 mod 3) orbits of 8 centers ((8!/2)^((n-1)^2 mod 3)). So the number of positions is 2^(22-((n-1)^2 mod 3)) * 24!^(n-1+floor((n-1)^2/3)) * 12! * 3!^(-8floor((n-1)^2/3)) * 8!^((n-1)^2 mod 3). The existing puzzles are n=1 (Magic Jewel, with 2.009 * 10^15 positions), n=1 with tips (Magic Octahedron, with 8.229 * 10^18 positions), and n=2 with tips (Master Octahedron, with 1.029 * 10^47 positions).
Trajber's Octahedron Family: Although the Trajber's Octahedron functions in an analogous way to an odd NxNxN cube, the pieces are colored differently, which means that a different method is required when solving it, and it has a different number of positions. Thus it makes sense to consider it a separate puzzle. Note that octahedra made from even NxNxN cubes are entirely different, in that they have many solutions and no piece has multiple stickers. We will hold the corners constant, although allowing them to rotate. Thus our orbits are 6 corners with 4 orientations each (1 * 4^6), 12 middle edges with two orientations each (12!/2 * 2^11), n-1 orbits of 24 edge wings ((24!)^(n-1)), n^2-n outer center orbits, with 3 pieces each of 8 colors ((24!/3!^8)^(n^2-n)), and 8 inner centers (8!/2). Thus the total number of positions is 12! * 8! * 2^21 * 24!^(n^2-1) * 3!^(-8n^2+8n). The existing puzzles are n=1 (Trajber's Octahedron, with 4.050 * 10^19 positions) and n=2 (5x5x5 Trajber's Octahedron, with 3.429 * 10^78 positions).
Dino Cube Family: This is an interesting set of puzzles to think about, although it is easy to solve, since you basically just have a large number of orbits that are all solved like a dino cube. Note that a true n-layer Dino Cube will have 2n(n+1) stickers on each face, and also has two solutions - if you solve it to a mirrored color scheme you will not encounter any problems. This doesn't change the number of combinations, but it does make the puzzle slightly 'easier'. There are n(n+1)/2 orbits on this puzzle, each of which must have an even permutation because all turns create 3-cycles, and no pieces have orientation since they are in a given orientation whenever they are in a given position. We will fix one piece in the centermost orbit (11!/2) and then keep the other ones free ((12!/2)^((n^2+n)/2-1)), so the total number of positions is 11! * 12!^((n^2+n-2)/2) * 2^((-n^2-n)/2). The existing puzzles are n=1 (Dino Cube, with 1.996 * 10^7 positions) and n=2 (Lattice Cube, with 1.145 * 10^24 positions).
Number of Positions of Some Other Interesting Twisty Polyhedra
We can use these techniques for basically any twisty polyhedron, but in some specific cases we need to use a trick to find the correct answer, because if we are not careful we will miss an important detail about the puzzle. I'll illustrate each one with a puzzle. I will make a large table with the number of positions for each of a number of existing puzzles in another article, so if you are interested in the number of positions of a specific puzzle that isn't mentioned here it should be on that list.
Siamese Cube: The Siamese Cube is composed of two separate puzzles which do not share pieces. Since they are the same, you can find the number of positions by finding the number of positions for one of those puzzles and squaring it. Fix the block and the number of positions is ((24)(120 * 3^5)(11!/2 * 2^10))^2 or 2.046 * 10^32.
Helicopter Cube: The tricky thing about this cube is that (in its non-jumbleable form) it actually has four orbits of centers, which each contains one center of each color, and at least one orbit can have an odd permutation as long as the permutation of all of the orbits combined is even (since each turn flips parity on two orbits but doesn't change the overall parity). So if we fix a corner the number of positions ends up as (7! * 3^6)(6!)(6!)(6!)(6!/2) or 4.937 * 10^17.
Alexander's Star: In the standard coloring scheme each piece has a duplicate. So we want to choose one pair of pieces and fix one. There are two identical pieces, though, so we can fix each position exactly two ways, so we have to divide the result by 2. But note that there still may be positions which look the same in more than one of these states (which we assume to be different), which would mean that the result we calculate is actually too small. Generally there are a very small number of these, not enough to influence the calculated result if we write it scientific notation, but it is important to realize that if we wrote out the number in full it would almost certainly be incorrect. The number of positions is approximately (29*(28!/2!^14) * 2^28)/2 or 7.243 * 10^34.
Here is another way to look at this phenomenon: consider a "puzzle" with six tiles arranged like the faces of a cube, where you can switch any two tiles at any time. Suppose we color these tiles so there are three red ones and three blue ones. Now intuition tells us there are exactly 2 positions; our calculation, on the other hand, says that we can fix one of them in a specific orientation and get (5!/(2!*3!))/3*4 = 120/144 or 0.833... positions. Of course this is a contrived result, with many more identical positions than a real puzzle would have, but it does show how the calculated number is too small.
The goal of this article is to determine the number of positions of various twisty polyhedra. I will first show an algorithmic theory where we can find the number of positions in well-behaved twisty polyhedra (that is, puzzles which are symmetrical and have no move constraints based on the position) without difficulty, and then use it to find the number of positions in a few infinite families of theoretical twisty polyhedra, and a few examples of how to modify this theory for trickier puzzles.
Theory of Positions
Before we start determining the number of positions of a puzzle we must fix the orientation somehow. This is necessary since simply turning a puzzle around without doing moves on it will not change its position. The normal way to do this is to fix one specific piece, or a set of pieces which are fixed relative to one another. If this is impossible we can divide the number of positions we calculate later by the number of possible positions of a solved puzzle (most usually 12 for a puzzle with tetrahedral symmetry, 24 for a puzzle with cubical or octahedral symmetry, or 60 for a puzzle with icosahedral or dodecahedral symmetry) but it is not certain that this will give us the correct result. Note, however, that if we have a few choices for what piece to fix, you will get the same answer no matter which piece you choose.
After this the first step to finding the number of positions of a twisty puzzle is to determine the orbits. An orbit is the set of positions that a given non-fixed piece can be in, and orbits containing the same positions are considered the same. In a 3x3x3 cube we will typically fix the orientation by forcing the centers to be in specific places; then there are two orbits, one for the 12 edges and one for the 8 centers. Note that there can be more than one orbit containing similar-looking pieces; for example on the 3x3x3 square group (where only half turns can be used) there are in fact three edge orbits and two corner orbits.
In general we will proceed by finding the number of positions in each orbit and multiplying them together. Because of parity concerns, the best way to do this is to order the orbits in some way and consider them one by one, assuming that while considering one orbit all pieces in the previously considered orbits are solved. This way, when two orbits have the same parity, we see that one does not obey a parity constraint and the other does, so we correctly divide by 2 only once.
So how many positions are in a single orbit? This is generally an easy problem, as it can be directly calculated with a little casework. First we consider the permutations. If there are n pieces, we start with n!; if there are n pieces each of k types, as in the centers of a higher-order Rubik's Cube, we start with (nk)!/n!^k. If the pieces of the orbit have to obey a (permutation) parity constraint then we divide by 2; note that this is only possible in the first type because if we have indistinguishable pieces we can always make a 2-cycle of same-colored pieces to cancel out a wrong parity. Next we consider the orientation of the pieces. If the pieces cannot be oriented differently when they are in a given position we do not have to consider orientation and we can just multiply by 1. Otherwise, if we let k be the number of possible orientations one piece can have if it is a given position and n be the number of pieces then we should multiply by k^n. If the pieces of the orbit obey an orientation parity, we divide by its order, which is generally 2 or 3 but can be higher.
Let's work through an example to illustrate the technique: the 3x3x3 cube. As I already mentioned, if we fix the orientation by fixing the centers' positions, we have two orbits: edges and corners. First we'll consider edges: there are 12 pieces (12!) with no parity (since corners are unknown), and each has an orientation of order 2 (2^12) with an orientation parity (/2), so the total number of possibilities here is 12! * 2^11. Then we consider corners: there are 8 pieces (8!) with parity (/2, since edges are fixed), and each has an orientation of order 3 (3^8) with an orientation parity (/3), so the total number of possibilties is 8!/2 * 3^7. Thus the total number of positions is (12! * 2^11)(8!/2 * 3^7) = 43252003274489856000, as I'm sure you already know.
Number of Positions of Infinite Families of Twisty Polyhedra
The most important concept here is that of layers. It is difficult to put into words, but the number of layers of a puzzle is basically the number of parallel, twistable slices (not counting slices on the opposite side of the puzzle's center). Puzzles with one layer include the 2x2x2, 3x3x3, Megaminx, and Dino Cube; puzzles with two layers include the 4x4x4, 5x5x5, Gigaminx, and Lattice Cube. A family of puzzles is basically a set of puzzles that function similarly (have the same axes, the same fixed pieces, the same shape, and so on), but which differ in the number of layers, a constant which I will call n throughout the rest of the article. I don't count 'trivial tips' (twistable elements of a puzzle which do not affect any other elements, are not affected by any other elements, and can always be solved in one move) as layers, because they do not share any pieces with the rest of the puzzle; thus, although most families only have twistable puzzles for n >= 1, there are some families where the case for n = 0 has more than 1 possibility.
There are many families of puzzles; however, most families have only had one puzzle constructed or even considered, and there are other families (such as stacked pucks and 2x2x(2n+1) cuboids) where adding one layer simply multiplies the number of combinations by a fixed amount. In this article I will only consider the number of combinations for families of which at least two puzzles have been constructed or designed. Of course, these are the most popular families to consider. All numbers I give have been calculated using the formula given here.
Odd NxNxN Cubes: Just like the 3x3x3, we will hold the centers constant. Then our orbits are: 12 edges with 2 orientations each (12! * 2^11), 8 corners with 3 orientations each (8!/2 * 3^7), n-1 orbits of 24 edge wings ((24!)^(n-1)), and n^2-n different orbits of 24 centers, all of which are made up of 4 pieces each of 6 types ((24!/4!^6)^(n^2-n)). Thus the total number of positions is 12! * 8! * 24!^(n^2-1) * 4!^(-6n^2+6n) * 2^10 * 3^7. For this family the existing puzzles are n=1 (3x3x3, with 4.325 * 10^19 positions), n=2 (5x5x5, with 2.829 * 10^74 positions), and n=3 (7x7x7, with 1.950 * 10^160 positions).
Odd NxNxN Supercubes: This is like the odd NxNxN cubes, except that there are much more parities since the center pieces have no duplicates, and also the centers have orientation. Again keep the centers fixed, then the orbits are 6 centers with 4 orientations each (1 * 4^6), 12 edges with 2 orientations each (12!/2 * 2^11), 8 corners with 3 orientations each (8!/2 * 3^7), n-1 orbits of 24 edge wings ((24!)^(n-1)), and n^2-n orbits of 24 centers ((24!/2)^(n^2-n)). So the total number of positions is 12! * 8! * 2^(-n^2+n+21) * 3^7 * 24!^(n^2-1). The puzzles that have been made so far are n=1 (3x3x3 Supercube, with 8.858 * 10^22 positions) and n=2 (5x5x5 Supercube, with 5.289 * 10^93 positions).
Even NxNxN Cubes: We can't hold centers constant, because there are no centers, but if we fix one specific corner we will always be guaranteed a fixed orientation. So our orbits are: 7 corners with 3 orientations each (7! * 3^6), n-1 orbits of 24 edge wings ((24!)^(n-1)), and n^2-2n+1 orbits of 24 centers, each of 4 pieces in 6 colors ((24!/4!^6)^(n^2-2n+1)). The total number of positions here is 7! * 24!^(n^2-n) * 4!^(-6n^2+12n-6) * 3^6. The puzzles in this family that have been constructed are n=1 (2x2x2, with 3.674 * 10^6 positions), n=2 (4x4x4, with 7.401 * 10^45 positions), and n=3 (6x6x6, with 1.572 * 10^116 positions).
Even NxNxN Supercubes: This is very much like the odd NxNxN supercubes. Keep a corner fixed, and our orbits become 7 corners with 3 orientations each (7! * 3^6), n-1 orbits of 24 edge wings ((24!)^(n-1)), and n^2-2n+1 orbits of 24 centers, all with parity ((24!/2)^(n^2-2n+1)). So the total number of positions is 7! * 24!^(n^2-n) * 3^6 * 2^(-n^2+2n-1). The existing puzzles are n=1 (2x2x2, with 3.674 * 10^6 positions) and n=2 (4x4x4 Supercube, with 7.072 * 10^53 positions).
Megaminx Family: These puzzles work just like the odd NxNxN cubes, except with larger numbers of pieces in each orbit. However, in these puzzles all turns create 5-cycles, so every orbit has a permutation parity. There are 30 edges with 2 orientations each (30!/2 * 2^29), 20 corners with 3 orientations each (20!/2 * 3^19), n-1 orbits of 60 edge wings ((60!/2)^(n-1)), and n^2-n orbits of 60 centers, in 12 colors of 5 pieces each ((60!/5!^12)^(n^2-n)). So the total number of positions is 30! * 20! * 60!^(n^2-1) * 5!^(-12n^2+12n) * 2^(28-n) * 3^19. The existing puzzles are n=1 (Megaminx, with 1.007 * 10^68 positions) and n=2 (Gigaminx, with 3.648 * 10^263 positions).
Pyraminx Family: These puzzles are slightly more tricky to calculate since some of them have middle centers (where there are only 4 pieces instead of 12) and some do not. I am not including the trivial tips in the calculation because they are not an inherent part of the puzzle, but of course to put them back in we can just multiply by 3^4. In this puzzle we are keeping the corners in the same position, although their orientation can change. Note that, just as in the Megaminx family, all turns create even permutations, so every orbit has permutation parity. In this family our orbits are 4 corners with 3 orientations each (1 * 3^4), 6 middle edges with 2 orientations each (6!/2 * 2^5), n-1 orbits of 12 edge wings ((12!/2)^(n-1)), a total of floor((n-1)^2/3) orbits of 12 centers, in 3 centers for each of 4 colors ((12!/3!^4)^(floor((n-1)^2/3))), and ((n-1)^2 mod 3) orbits of 4 centers ((4!/2)^((n-1)^2 mod 3)). Thus the number of positions is 6! * 2^(5-n-((n-1)^2 mod 3)) * 3^4 * 12!^(n-1+floor((n-1)^2/3)) * 3!^(-4floor((n-1)^2/3)) * 4!^((n-1)^2 mod 3). The existing puzzles are n=1 (Tetraminx, with 9.331 * 10^5 positions), n=1 with tips (Pyraminx, with 7.558 * 10^7 positions), and n=2 with tips (Master Pyraminx, with 2.172 * 10^17 positions).
Magic Octahedron Family:This family works just like the Pyraminx family, but now there are parities involved with some of the edges since a turn creates edge 4-cycles. Again, we want to fix the corners, and we're not going to fix the tips. The orbits are 6 corners with 4 orientations each (1 * 4^6), n-1 sets of 24 edge wings ((24!)^(n-1)), one orbit of middle edges (12!/2 * 2^11), a total of floor((n-1)^2/3) orbits of 24 centers, 3 each in 8 colors ((24!/3!^8)^(floor((n-1)^2/3)), and ((n-1)^2 mod 3) orbits of 8 centers ((8!/2)^((n-1)^2 mod 3)). So the number of positions is 2^(22-((n-1)^2 mod 3)) * 24!^(n-1+floor((n-1)^2/3)) * 12! * 3!^(-8floor((n-1)^2/3)) * 8!^((n-1)^2 mod 3). The existing puzzles are n=1 (Magic Jewel, with 2.009 * 10^15 positions), n=1 with tips (Magic Octahedron, with 8.229 * 10^18 positions), and n=2 with tips (Master Octahedron, with 1.029 * 10^47 positions).
Trajber's Octahedron Family: Although the Trajber's Octahedron functions in an analogous way to an odd NxNxN cube, the pieces are colored differently, which means that a different method is required when solving it, and it has a different number of positions. Thus it makes sense to consider it a separate puzzle. Note that octahedra made from even NxNxN cubes are entirely different, in that they have many solutions and no piece has multiple stickers. We will hold the corners constant, although allowing them to rotate. Thus our orbits are 6 corners with 4 orientations each (1 * 4^6), 12 middle edges with two orientations each (12!/2 * 2^11), n-1 orbits of 24 edge wings ((24!)^(n-1)), n^2-n outer center orbits, with 3 pieces each of 8 colors ((24!/3!^8)^(n^2-n)), and 8 inner centers (8!/2). Thus the total number of positions is 12! * 8! * 2^21 * 24!^(n^2-1) * 3!^(-8n^2+8n). The existing puzzles are n=1 (Trajber's Octahedron, with 4.050 * 10^19 positions) and n=2 (5x5x5 Trajber's Octahedron, with 3.429 * 10^78 positions).
Dino Cube Family: This is an interesting set of puzzles to think about, although it is easy to solve, since you basically just have a large number of orbits that are all solved like a dino cube. Note that a true n-layer Dino Cube will have 2n(n+1) stickers on each face, and also has two solutions - if you solve it to a mirrored color scheme you will not encounter any problems. This doesn't change the number of combinations, but it does make the puzzle slightly 'easier'. There are n(n+1)/2 orbits on this puzzle, each of which must have an even permutation because all turns create 3-cycles, and no pieces have orientation since they are in a given orientation whenever they are in a given position. We will fix one piece in the centermost orbit (11!/2) and then keep the other ones free ((12!/2)^((n^2+n)/2-1)), so the total number of positions is 11! * 12!^((n^2+n-2)/2) * 2^((-n^2-n)/2). The existing puzzles are n=1 (Dino Cube, with 1.996 * 10^7 positions) and n=2 (Lattice Cube, with 1.145 * 10^24 positions).
Number of Positions of Some Other Interesting Twisty Polyhedra
We can use these techniques for basically any twisty polyhedron, but in some specific cases we need to use a trick to find the correct answer, because if we are not careful we will miss an important detail about the puzzle. I'll illustrate each one with a puzzle. I will make a large table with the number of positions for each of a number of existing puzzles in another article, so if you are interested in the number of positions of a specific puzzle that isn't mentioned here it should be on that list.
Siamese Cube: The Siamese Cube is composed of two separate puzzles which do not share pieces. Since they are the same, you can find the number of positions by finding the number of positions for one of those puzzles and squaring it. Fix the block and the number of positions is ((24)(120 * 3^5)(11!/2 * 2^10))^2 or 2.046 * 10^32.
Helicopter Cube: The tricky thing about this cube is that (in its non-jumbleable form) it actually has four orbits of centers, which each contains one center of each color, and at least one orbit can have an odd permutation as long as the permutation of all of the orbits combined is even (since each turn flips parity on two orbits but doesn't change the overall parity). So if we fix a corner the number of positions ends up as (7! * 3^6)(6!)(6!)(6!)(6!/2) or 4.937 * 10^17.
Alexander's Star: In the standard coloring scheme each piece has a duplicate. So we want to choose one pair of pieces and fix one. There are two identical pieces, though, so we can fix each position exactly two ways, so we have to divide the result by 2. But note that there still may be positions which look the same in more than one of these states (which we assume to be different), which would mean that the result we calculate is actually too small. Generally there are a very small number of these, not enough to influence the calculated result if we write it scientific notation, but it is important to realize that if we wrote out the number in full it would almost certainly be incorrect. The number of positions is approximately (29*(28!/2!^14) * 2^28)/2 or 7.243 * 10^34.
Here is another way to look at this phenomenon: consider a "puzzle" with six tiles arranged like the faces of a cube, where you can switch any two tiles at any time. Suppose we color these tiles so there are three red ones and three blue ones. Now intuition tells us there are exactly 2 positions; our calculation, on the other hand, says that we can fix one of them in a specific orientation and get (5!/(2!*3!))/3*4 = 120/144 or 0.833... positions. Of course this is a contrived result, with many more identical positions than a real puzzle would have, but it does show how the calculated number is too small.
20080510
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!
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!