Online since 2002. Over 3300 puzzles, 2600 worldwide members, and 270,000 messages.

TwistyPuzzles.com Forum

It is currently Sat Apr 19, 2014 3:16 pm

All times are UTC - 5 hours



Post new topic Reply to topic  [ 12 posts ] 
Author Message
 Post subject: Twisty Puzzle Maths
PostPosted: Wed Jan 29, 2014 7:46 pm 
Offline

Joined: Wed Apr 17, 2013 5:44 pm
Hello Twisty Puzzle Forum! I wanted to know what kind of mathematical concepts are involved in twisty puzzles. I want to compile a list of topics so I can write a paper on it for school. Any contributions are welcome. Thanks!


Top
 Profile  
 
 Post subject: Re: Twisty Puzzle Maths
PostPosted: Wed Jan 29, 2014 8:13 pm 
Offline
User avatar

Joined: Wed Jun 19, 2013 2:50 pm
Location: Deep in the Heart of Texas
I guess the main thing is group theory. There's also permutations and I guess probability for OLLs and PLLs. That's all I've got, but I'm sure someone far more experienced than me will answer your question more clearly.

_________________
For all of you that bought a KO 8x8x8: You should have bought a V8!


Top
 Profile  
 
 Post subject: Re: Twisty Puzzle Maths
PostPosted: Wed Jan 29, 2014 8:25 pm 
Offline
User avatar

Joined: Thu Jan 06, 2005 8:53 pm
Location: Los Angeles
Yeah, the big one is group theory.
Then you can use combinatorics to count permutations.
And, of course, there's geometry.


Top
 Profile  
 
 Post subject: Re: Twisty Puzzle Maths
PostPosted: Wed Jan 29, 2014 8:44 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
You should check out some of Jaap's writings:
Useful Mathematics
Group Theory for puzzles

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: Twisty Puzzle Maths
PostPosted: Thu Jan 30, 2014 4:35 pm 
Offline

Joined: Wed Apr 17, 2013 5:44 pm
Can someone give me an example of for instance, how many permutations are in a Super Teraminx? How would one even begin to calculate that? Thank you all for your nice feedback


Top
 Profile  
 
 Post subject: Re: Twisty Puzzle Maths
PostPosted: Thu Jan 30, 2014 6:39 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
[][][][][][][][][] wrote:
Can someone give me an example of for instance, how many permutations are in a Super Teraminx? How would one even begin to calculate that? Thank you all for your nice feedback

I don't have the time to spell out all of the details for you but fortunately super-puzzles are usually easier to calculate and the Teraminx pieces are always in even-permutations and you don't have to worry about permutation parity relationships between pieces.

Quick enumeration of pieces and piece behavior:
  • 12 centers, single-center twists possible: 5^12
  • 20 corners, total twist fixed: ((20! / 2) * (3^20 / 3))
  • 30 middle-edges, total twist fixed: ((30! / 2) * (2^30 / 2))
  • Two sets of 60 edge-wings, no twist: (60! / 2)^2
  • Six different sets of 60 center pieces, no twist: (60! / 2)^6

So:
(5^12) * ((20! / 2) * (3^20 / 3)) * ((30! / 2) * (2^30 / 2)) * (60! / 2)^2 * (60! / 2)^6 =
22064662873908651767402119110980799209149681176052756686366892533021
89173858220522520767613669283627882973260519615451839792034893696222
05050680542340021240753027051708573027773967706527470422973428088272
94438278051535067821951669479931630273571366358375901707321264534663
63630000240162481650731685934773624446197330165970877233759397934457
85112449675355332238403396271284758939734541143326252167909536267759
45236502041577043261296634687612807982204635842449371900474493567719
48325552267355784531968464873287605120582116370215163298191598332989
87086609033911184397073751650533199882837514466099200000000000000000
00000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000

Or 2.2 * 10^729

Most puzzles are harder to calculate than that so don't take this as a very good example of twisty puzzles in general.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: Twisty Puzzle Maths
PostPosted: Thu Jan 30, 2014 7:19 pm 
Offline

Joined: Tue Jun 11, 2013 12:48 pm
Brandon Enright wrote:

So:
(5^12) * ((20! / 2) * (3^20 / 3)) * ((30! / 2) * (2^30 / 2)) * (60! / 2)^2 * (60! / 2)^6 =
22064662873908651767402119110980799209149681176052756686366892533021
89173858220522520767613669283627882973260519615451839792034893696222
05050680542340021240753027051708573027773967706527470422973428088272
94438278051535067821951669479931630273571366358375901707321264534663
63630000240162481650731685934773624446197330165970877233759397934457
85112449675355332238403396271284758939734541143326252167909536267759
45236502041577043261296634687612807982204635842449371900474493567719
48325552267355784531968464873287605120582116370215163298191598332989
87086609033911184397073751650533199882837514466099200000000000000000
00000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000

Or 2.2 * 10^729

Most puzzles are harder to calculate than that so don't take this as a very good example of twisty puzzles in general.


Wow! What an amazing coincidence :shock: That´s exact the amount of money which I planned to spent in twisty puzzles :lol:


Top
 Profile  
 
 Post subject: Re: Twisty Puzzle Maths
PostPosted: Thu Jan 30, 2014 7:26 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
doctor twist wrote:
Brandon Enright wrote:
Or 2.2 * 10^729


Wow! What an amazing coincidence :shock: That´s exact the amount of money which I planned to spent in twisty puzzles :lol:

Well if you're spending ZWD you could probably buy a puzzle or two with that.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: Twisty Puzzle Maths
PostPosted: Thu Jan 30, 2014 7:53 pm 
Offline

Joined: Sun Oct 08, 2006 1:47 pm
Location: Houston/San Antonio, Texas
Darn, beaten to the punch :lol: At least we can see that Brandon is justified in saying he didn't have time for a full explanation - it DID take awhile. THIS is the full explanation...

There's a lot of factors that can come into play when calculating the number of configurations of a particular puzzle. Different puzzles have different properties that can introduce new concepts so I doubt anyone can present an exhaustive list of all of the types of calculations and situations, but here's a start:

Permutations of a single orbit Consider the Rainbow Cube. This puzzle has 8 triangular centers and 12 "edges". The centers never move relative to the core and the edges CANNOT be flipped in place; their orientation is determined by their location. Since the triangles never move, you can tell what orientation the puzzle is in (i.e. even if the edges are fully scrambled you can tell if the puzzle is "upside-down"). As a single move creates a 3-cycle, which is an even permutation, only even permutations are possible. Therefore a rainbow cube has 12!/2 = 239500800 configurations. Usually, if both even and odd permutations of a single orbit of pieces are achievable, there are n! permutations, and n!/2 permutations if only even permutations are achievable.

Global orientation Now consider the Dino Cube. This puzzle only has 12 edge pieces and in fact they behave exactly the way the 12 "edge" pieces of the Rainbow Cube behave. However the calculation is different because on the Dino Cube, you cannot tell which way the "core" is facing. So using the calculation for the Rainbow Cube here will overcount the number of configurations. Why? Because the Rainbow cube calculation counts "white on top face, red on front face" as a different configuration than "white on front face, red on bottom face" (ok there is no white on Rainbow Cube - pretend they have the same coloring). This is appropriate for the Rainbow Cube because the two configurations will look DIFFERENT: the triangular center pieces will not match. On a Dino Cube there are no "triangular center" pieces and so these two configurations will look identical. (Side note: in reality the core of the Dino Cube will really be rotated in a different position relative to the other pieces between these two configurations, but since you cannot determine this without ripping the puzzle apart, they are considered to be the same configuration There are two ways of dealing with this mathematically: 1) arbitrarily call one piece that fully determines the orientation of the puzzle correct and count the number of ways the rest of the pieces can be configured. In this case, call one Dino edge correct and then the other 11 can reach 11!/2 = 19958400 configurations. -OR- 2) calculate all configurations as normal and divide by the number of reachable global orientations. Although a cube has 24 possible orientations, the pieces of the Dino Cube can only reach 12 of them (edges cannot flip in place) so we get (12!/2)/12 =19958400 configurations. Both approaches are valid and produce the same number, but on some puzzles one approach is more difficult or in fact impossible altogether (if no single fixed piece can fully determine the global orientation i.e. A dodecahedral Big Chop).

Orientations within an orbit Now consider a standard 2x2x2 Rubik's Cube. This puzzle has 8 corner pieces. The global orientation is not visible and all 24 orientations of the cube relative to the core are reachable (in this case the core is physically fixed to a corner, but the mathematics operate independent of how the puzzle is constructed). However this puzzle introduces multiple orientations of a single piece. Each corner piece can be in one of 3 orientations, but not all independently of each other. As you may already know, the sum of the orientations of the corners must be 0 mod 3. Another way of saying this is the first 7 pieces can be in any orientation but the orientation of the 8th corner is determined by the other 7. This raises the issue of "How do you define orientation of a piece in the wrong position?". The answer is that the definition is merely an opinion and any consistent definition will suffice. Regardless of how you define orientation you will find a single move on a 2x2x2 will always keep the overall sum of the orientation of the pieces 0 mod 3. Usually, if an orbit has n pieces that can each reach m orientations, the total number of possible orientations on those pieces for a given permutation is (n-1)^m. Thus putting the above three concepts together (and noting that both even AND odd permutations are reachable, a 2x2x2 has (8!*3^7)/24 = 3674160 (dividing by number of reachable global orientations last) -OR- 7!*3^6 = 3674160 (fixing one corner to define the global orientation.

Multiple orbits Now consider a Megaminx. This puzzle has 12 centers, 30 edges, and 20 corners. The centers cannot move and do define the global orientation, so we needn't factor in a global orientation figure. The edges can be in two orientations each, and the corners can be in 3 orientations each. Only even permutations are reachable for both edges and corners. The permutation and orientations of the edges has no affect on the permutation and orientations of the corners so we can simply multiply these together: 30!/2*2^29 * 20!/2*3^19 = 1.0067*10^68. Easy right?

Parity dependencies among multiple orbits Not always. Consider now a standard 3x3x3 Rubik's Cube. We have 6 centers that do not move but do define the global orientation, 12 edges that can be in 2 orientations each, and 8 corners that can be in 3 orientations each. Both even and odd parities are reachable for both corners and edges but they are NOT independent. There is only one type of move possible without affecting the global orientation of the puzzle - a face turn. If we rotate a single face of a 3x3x3 a quarter-turn, we have produced an odd permutation of edges and an odd permutations of corners. This means that for ever quarter turn we toggle the parity of the edges and corners TOGETHER (note a half turn is simply two quarters so a half turn toggles the parities of both edges and corners together, and then toggles them back together, resulting in no overall change in either parity). The important point to realize is that the corner permutation can have even parity while the edge permutation has even parity or the edge permutation can have odd parity while the corner permutation has odd parity, but NEVER one odd and the other even. All permutations of the edges and corners are achievable but not simultaneously; the parity of the two permutations must match. So, you can think of this as either the edges can reach both even and odd permutations, but the corners can only reach permutations of the same parity -OR- the corners can reach both even and odd permutations, but the edges can only reach permutations of the same parity. The number of configurations then, for a 3x3x3 Rubik's Cube, is 12!*2^11 * 8!/2*3^7 = 4.3*10^19 (edges both parities, corners only one) or 12!/2*2^11 * 8!*3^7 = 4.3*10^19 (corners both parities, edges only one). Either way we get the same result and also note that although I calculated edges first and corners second in both cases, I can easily flip these as multiplication is commutative.

Multiple orbits of a single piece-type Consider a Helicopter Cube, which we will scramble and solve using only half-turns (no jumbling). This puzzle has 8 corners and 24 "face" pieces. Global orientation is not visible, and while fixing a face piece will NOT work because a single face piece only narrows the 24 possible global orientations to 4, fixing a corner WILL work because a fixed corner guarantees a unique global orientation, so no big issues there. However, here we run into something we haven't seen before: not every face piece can reach the spot of every other face piece. You can determine this by tracking a single face piece and finding all of the locations that single piece can reach. Out of 24, it can only reach 6, including the one it started in. This is called a piece's orbit and in fact all pieces within an orbit share the same orbit, so we might as well just look at how many orbits exist among the 24 pieces. In the case of the Helicopter Cube, there are 4 orbits of 6 locations each. The math here would be exactly the same as if each orbit actually had a different type of piece, i.e. there are 6 "faceA" pieces, 6 "faceB" pieces, 6 "faceC" pieces, and 6 "faceD" pieces. Also note that within a single orbit, each piece is a different color, that is, each piece is unique (I'll get to identical pieces in a bit). The tricky thing here is the parity dependencies. A single 180 move on a Helicopter Cube produces an odd parity on the corner orbit and 2 of the 4 face orbits. So on every move, the parity of the permutation of the corners is toggled, as is the parity of the permutation of 2 of the 4 face orbits. Which 2 depends on which move, although there is at least one move for any set of 2 of the 4 face orbits. Clearly, both odd and even permutations of each orbit are possible, but what parities can occur simultaneously? This is actually related to the linear algebra concept of linear independence although instead of vectors we are working in parities. It turns out that either 0, 2, or all 4 of the face orbits can be in odd parities and the corners can be in either an even or odd parity independent of the face orbit parities. In other words, any parity of the corners and the first 3 face orbits are possible simultaneously, but the parity of the 4th face orbit is determined by the previous 3. To test yourself, the total number of configurations for a Helicopter Cube without the use of jumbling moves is 7!*3^6 * 6! * 6! * 6! * 6!/2 = 4.9*10^17 -OR- (8!*3^7 * (6!^4)/2)/24 = 4.9*10^17

Identical pieces Ok what if we have a puzzle like a 5x5x5 (non-super) that has some identical pieces? Each face has 4 inner edges and 4 inner corners that are indistinguishable . This means if we perform the usual n! calculation we are overcounting the number of visually distinct configurations because some of those will look identical to others (the difference being two identical pieces have been swapped). The easiest way of accounting for this is to perform the calculation as normal but then divide by the number of ways the identical pieces could have been rearranged among themselves. This works because ever permutation of say, 1 blue piece, 1 red piece, and 4 green pieces puts the 4 green pieces somewhere, and for each distinct way of arranging these 6 pieces, the simple calculation of 6! will produce the same number of permutations that have the 4 greens in the same places. In this case, 6! will produce 4! different configurations that all have the 4 green pieces in the first 4 spots even though that should have only been counted once. The other potential issue with this is figuring out how parity applies to these kind of situations, but fortunately, having at least one pair of identical pieces in an orbit means we can swap those two, toggling the parity, and opening up the possibility of reaching states that appear to be in an unreachable parity. In other words, even if only even parities are reachable, both even and odd parities of the distinct pieces is always reachable so we can always assume both parities are reachable and the division by the permutation of identical pieces will take care of parity. So, the 24 inner-edges of a 5x5x5, which includes 6 sets of 4 identical pieces, can reach 24!/(4!)^6 distinct configurations. The 24 outer-edges can reach the same number of distinct configurations. There are two independent types of moves on a 5x5x5 that don't affect the global orientation given by the centers: a single layer face turn, and a slice turn one layer in from the surface (a double layer turn is simply these two combined). The outer face (quarter) turn toggles the parities of the corners, edges, inner edges, and inner corners, but not the wings - although the parity of the inner edges and inner corners is indistinguishable anyway so we don't really care about that. The slice (quarter) turn toggles the parity of the wings, inner edges, and inner corners - but again we don't care about the parity of the inner edges and inner corners due to the presence of identical pieces in those orbits. From this we see that the corner parity can be even or odd but must match the edge parity, and the wing parity can freely switch between even or odd independent of the corners and edges. Accounting for everything: the 5x5x5 can reach 12!*2^11 * 8!/2*3^7 * 24! * 24!/(4^6) * 24!/(4^6) = 6.157*10^83 configurations (that was edges -> corners -> wings -> inner edges -> inner corners, centers provided the global orientation)

Moves that orient a single piece I mentioned before that the orientation of the nth piece in an orbit of n pieces is usually completely determined by the orientation of the other (n-1) pieces. Sometimes this is not true. If a move exists that involves changing the orientation of a single piece without moving it, then the sum of the orientations of that type of piece is not restricted by the orientations of the other pieces of the same type in the same orbit. Instead, any orientation of all of these types of pieces are possible, but they might be linked to the parities of some set of permutations on the puzzle. Let's consider a Super Rubik's Cube. Here the locations of the centers still give global orientation, but the centers themselves also have distinguishable orientations. Note that a single face move rotates a single center all by itself so clearly any orientation of the 6 centers is possible. However notice that every time you rotate a corner you ALSO toggle the parity of both the edges and the corners. So if you have rotated centers (in quarter turns) an odd number of times from solved, then the edges and corners must be in an odd parity. Or viewing the dependency from the other side: if the edges and corners are in an even/odd parity, then the centers must be in a set of orientations that is reachable in an even/odd number of quarter turns from solved. Of the four orientations of a square, only half are reachable in an even number of turns and the other half are reachable in an odd number of turns. Now we can trade off which center is receiving these twists but the overall twist of the centers must "match" the parity of the edges and corners. Thus, given a configuration of edges and corners, the first 5 centers can be in any orientation, but the 6th can only be in 2 of the 4 possible orientations. Likewise you can also account for centers first, in which case all 4^6 orientations are reachable, but then the parity of the edges and corners are both determined. In either case, this gives 12!*2^11 * 8!/2*3^7 * 4^5 * 2 =8.858*10^22 (centers last) -OR- 4^6 * 12!/2*2^11 * 8!/2*3^7 = 8.858*10^22 (centers first) configurations.

Further permutation restrictions In the very first topic in this post, I said permutations are USUALLY either n! or n!/2 depending on whether or not there's a parity restriction. This is not true for all puzzles and to me the most interesting puzzles are those that take exception to this rule. This calculation assumes a 3-cycle exists that doesn't restrict any pieces not yet accounted for. While this does seem to hold for "large enough" puzzles , there are many known examples where it does not hold. The most familiar of these is the Skewb. If you correctly identify that the corners come in two orbits, and one orbit can be used to determine the global orientation, following what I have said so far, you would calculate that the Skewb has 3^4 * 6!/2 * 4!/2*3^3 = 9447840 configurations. This calculation intends to account for the orientations of one orbit of corners (using their permutation as global orientation), followed by the permutation of the centers,and finally the permutation and then orientation of the other orbit of corners. However, the underlined portion is incorrect. Not all 4!/2 even permutations of the second orbit of corners is achievable. No pure 3-cycle of the second orbit of corners exists, and in fact, the only permutations that are achievable without affecting the other pieces is a double swap. Double swaps on 4 elements only produce 4 distinct permutations in a Klein-4 group relationship instead of the expected 4!/2=12. The proper calculation is 3^4 * 6!/2 * 4*3^3 = 3149280. A half-turn only Rubik's Cube has a similar phenomenon with its two orbits of corners. I do not know a good way of identifying these puzzles, I only know a good way of proving they do NOT fall in this category and that is to produce a pure 3-cycle of the pieces of the orbit in question.

These concepts form the basis of counting configurations, though the introduction of other elements can muddy the calculation further. Some examples include orbits where some pieces have orientation while others do not, any situation in which some moves are blocked, and the existence of more than one solved state - depending on what you want to compute. Now for your specific example, a Super Teraminx can only reach even permutation for all piece types and pure 3-cycles of every piece are possible. No two pieces are identical and the centers give global orientation though each center can attain any orientation independent of the rest of the puzzle. There are:
5^12 * 30!/2*2^29 * 20!/2*3^19 * (60!/2)^8 = 2.206*10^729 configurations for a Super Teraminx

...*pant* *pant* *pant*...


Peace,
Matt Galla

Edit: added links for some puzzles


Last edited by Allagem on Thu Jan 30, 2014 9:24 pm, edited 4 times in total.

Top
 Profile  
 
 Post subject: Re: Twisty Puzzle Maths
PostPosted: Thu Jan 30, 2014 7:59 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
Allagem wrote:
Edit: Darn, beaten to the punch :lol: At least we can see that Brandon is justified in saying he didn't have time for a full explanation - it DID take awhile. THIS is the full explanation [...] *pant* *pant* *pant*...
Holy crap that's an epic post! I sure wish I'd had such an amazing reference when I was figuring this stuff out a few years back!

It's so much information that I don't even have the time to READ it all right now but rest assured, I will! If I spot any mistakes or things I think you should mention but left out I'll let you know :-)

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: Twisty Puzzle Maths
PostPosted: Sat Feb 01, 2014 5:13 pm 
Offline
User avatar

Joined: Thu Dec 02, 2004 12:09 pm
Location: Missouri
Brandon Enright wrote:
Allagem wrote:
THIS is the full explanation [...] *pant* *pant* *pant*...
Holy crap that's an epic post!
Agreed!! Matt, Brandon, and I may not have the most posts on the TwistyPuzzles forums but if I had to guess I suspect one of us has the longest post. Great post Matt. I've read it once but this is one of those posts that needs to be read a few times to make make sure its all sunk in. It does touch on something I've thought about before. You talk about the half-turn only Helicopter Cube. Is it possible to count the number of configurations of the full Helicopter Cube including jumbling? Counting the number of cubic configurations that are reachable I suspect is doable but I have no clue how to deal with all the other shapes possible.

Carl

_________________
-
Image

Image


Top
 Profile  
 
 Post subject: Re: Twisty Puzzle Maths
PostPosted: Sat Feb 01, 2014 5:23 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
wwwmwww wrote:
You talk about the half-turn only Helicopter Cube. Is it possible to count the number of configurations of the full Helicopter Cube including jumbling? Counting the number of cubic configurations that are reachable I suspect is doable but I have no clue how to deal with all the other shapes possible.
I think counting all of the shapes is doable. There can't be that many, maybe up to a few thousand but probably only hundreds. If somebody implemented the various geometry and handled floating point roundoff and such I'm sure a computer could easily enumerate them all.

I think there are some other issues that involve symmetry of the various shapes but I think the 3-sticker corners might actually eliminate the issues I'm thinking about.

I will elaborate on the issues of symmetrical states and counting total positions in a later post.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 12 posts ] 

All times are UTC - 5 hours


Who is online

Users browsing this forum: No registered users and 2 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  

Forum powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group