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

TwistyPuzzles.com Forum

It is currently Fri Apr 18, 2014 11:10 am

All times are UTC - 5 hours



Post new topic Reply to topic  [ 12 posts ] 
Author Message
 Post subject: Analysis of 180 degree only 3x3x3 cube
PostPosted: Tue Nov 26, 2013 6:37 pm 
Offline

Joined: Sun Oct 08, 2006 1:47 pm
Location: Houston/San Antonio, Texas
The 3x3x3 is a puzzle we probably all feel very familiar with, but have you ever tried to scramble and solve it using only half turns (180 degrees)? The feel of the puzzle changes dramatically and several very interesting parities come into play. If you have never tried this before, and are looking for a challenge without spending alot of money, I highly recommend you try solving a cube in this fashion. The corners in particular are surprisingly tricky!

I analyzed this puzzle to an extent and wanted to share results as well as some of my thoughts. One very rare property in particular occurs on this puzzle and I must admit its occurrence is not something I fully understand.

For starters, let's assume the center orientations are not visible. Then, leaving the core fixed, the centers do not move. There are 3 orbits of edges and 2 orbits of corners. The location of a piece uniquely determines its orientation. Each rotation toggles the parity of both corner orbits and 2 out of 3 edge orbits. This means that if you solve corners first, two of the three edge orbits may be in odd parity and if you solve the edges first, both corner orbits may be in odd parity. As I find it more natural to solve the edges first, I run into the second problem quite often. It is a bit surprising that different moves can break and then mend the parities of one type of piece while breaking the parities of a different type of piece. The same phenomenon occurs on a Helicopter Cube where all the entire puzzle can be in a solved state except with two corners swapped WITHOUT JUMBLING! This is a neat and fairly rare property, but it's not the one I referred to before because I understand exactly where this one comes from :wink:

Let's try to calculate the number of configurations:

-Fixing the core, the centers will always be solved (1)

-Rotating the correct face will toggle the parity of one orbit of edges so all permutations of the first orbit of edges is achievable (permutations of this kind are isomorphic to symmetric groups of the appropriate size, in this case S4) (4!)

-There are two faces left that will toggle the parity of the second orbit of edges without affecting the parity of the first so all permutations of the second orbit of edges is again achievable (4!)

-With the permutation of two edges fixed, the parity of the third and final orbit of edges is determined and CANNOT be toggled (i.e. any face that will toggle the parity of the third orbit of edges will also toggle the parity of either the first or second orbit of edges as well). Therefore only even (or odd, if the other orbits so dictate) permutations of the third orbit of edges are possible (permutations of this kind are isomorphic to alternating groups of the appropriate size, in this case A4) (4!/2)

-The first orbit of corners. This is a bit tricky, but with enough experimentation, you will find that in fact all permutations of the first orbit of corners is achievable regardless of the parities of the edges. To see how, note that U2 toggles the parities of both corner orbits, edge orbit A and edge orbit B; R2 toggles the parities of both corner orbits, edge orbit A and edge orbit C; and F2 toggles the parities of both corner orbits, edge orbit B and edge orbit C. Together then, U2 R2 F2 toggles the parities all edge orbits twice, having no affect overall, but toggles the parity of both corner orbits three times, overall toggling the parity. So these three moves together overall toggle the parity of only the two corner orbits, thus making all permutations of the first orbit of corners achievable (4!)

-Here's where it gets really weird. Every move toggles the parity of both corner orbits simultaneously, so it is clear that the parity of the two corner orbits must match, implying that the parity of the first orbit of corners determines the parity of the second orbit of corners making only even (or odd, if the other orbit so dictates) permutations of the second orbit of corners achievable, right? Wrong. Instead of the expected 4!/2 possible configurations for the final orbit of corners given the configuration of the rest of the pieces on the puzzle, only a mere 4 configurations are possible. Upon closer inspection, these four are equivalent to: ABCD, BADC, CDAB, DCBA which is isomorphic to the Klein Four-Group, a group interesting enough to have its own name! (4)


Multiplying the above options together we find the total number of states to a 3x3x3 using 180 degree turns only:
(4!)(4!)(4!/2)(4!)(4) = 663552

This result was further confirmed by exploring the distribution of states from solved:
0-1
1-6
2-27
3-120
4-519
5-1932
6-6484
7-20310
8-55034
9-113892
10-178495
11-179196
12-89728
13-16176
14-1488
15-144
Total number of elements = 663552

The very interesting part to me is the extreme restriction on the final orbit in this puzzle. Often when we calculate the number of positions of a puzzle, we first ensure that a given piece can visit the locations of all other pieces of the same type, if not, we must group the pieces in their oribts (for example helicopter cube, FTO), then, if both even parities and odd parities are possible, we conclude there are X! possible configurations of that piece-type (and then we calculate the orientations) or, if only even parities are possible, we conclude there are X!/2 possible configurations of that piece-type. Indeed, this strategy results in the correct answer 99.9% of the time, but in THIS case it would provide the wrong answer. This seems to be a very rare property among twisty puzzle groups...

According to Cayley's Theorem,
Quote:
every group G is isomorphic to a subgroup of the symmetric group acting on G
In ENGLISH ( :lol: ) this means that every group is equivalent to the set of all orderings of some numbers using a given set of allowable moves. For example, you may have the numbers 123 and the rules are you may swap whatever is in the first position with whatever is in the second or you may swap whatever is in the second position with whatever is in the third. By performing these actions in different orders, you can produce all 6 permutations: 123 132 213 231 312 321, and in fact the group we have formed is S3. Now what if instead you had the numbers 1234 and the rules were you can swap first location with second location or third location with fourth location. In this case, only 4 permutations are reachable: 1234 1243 2134 2143, not the full 4! permutations of the 4 numbers (in fact the group we have just formed is Z2xZ2, the product of two cyclic groups). "But Matt!", you may say (yes my name is Matt) "of course we didn't get all 4! permutations, you never allowed the numbers in the first half to exchange with numbers in the second half! The 1 and 2 were stuck in the front and the 3 and 4 were stuck in the back!" Ah, yes, of course you are correct! And perhaps now it is becoming clear what I mean about observing the orbits first. In the last example, 1 and 2 were in one orbit while 3 and 4 were in another. Ok fine, how about this one: the numbers 1234. The moves are: A)swapping 1 and 2 while SIMULTANEOUSLY swapping 3 and 4 OR B)swapping 1 and 3 while SIMULTANEOUSLY swapping 2 and 4. There, now all 4 numbers reside in the same orbit, any number can reach any location. Experimenting a little with this we quickly find that the only achievable permutations are: 1234, 2143, 3412, and 4321 - only 4 of the potential 4!=24 permutations. This is the Klein four-group and these are the only achievable permutations of the second orbit of corners on the half turn only 3x3x3. On any given (non-bandaged!) twisty puzzle, the stickers (and/or possibly shape) of the puzzle are analogous to the set of numbers you are working with and the moves made on the puzzle are analogous to the rules used for reordering the stickers. All non-bandaged twisty puzzles are isomorphic to groups (or, dare I say it, all groups are isomorphic to twisty puzzles, perhaps just not to ones that have been invented yet..... :shock: )

Groups of this kind seem to be very rare in the world of twisty puzzles. It has only cropped up a handful of times that I'm aware of: The second orbit of corners on a half-turn 3x3x3, the second orbit of corners on a Skewb, the corners of the Alternating Cube, the permutation of both edges and corners of a 3x3x3 restricted to the moves: U or R'FR, shown to me by Nan Ma (there are 6 edges involved but only 120 achievable permutations instead of the expected 6!=720 and there are 5 corners involved but only 10 of the expected 5!/2=60 are actually achievable). Based on these counter examples, I have a feeling this property is not rare among groups, but rather only rare among twisty puzzles. I must admit I do not fully understand why these instances occur, how to spot them without a rigorous analysis, or how to fully deal with them in a solving scenario. Does anyone have anything to add about these oddball normal groups? :D

Sorry for the wall of text, I really need to practice making my posts look more exciting :? I hope someone gets something out of my jabbering :lol:

Peace,
Matt Galla

PS If we DO take center orientation into account, then the results change slightly. The centers determine the parity of all other orbits. However, the elusive Klein Four Group remains:

Centers: 2^6
Edge Orbit 1: 4!/2
Edge Orbit 2: 4!/2
Edge Orbit 3: 4!/2
Corner Orbit 1: 4!/2
Corner Orbit 2: 4

Total: (2^6)(4!/2)(4!/2)(4!/2)(4!/2)(4) = 5308416


Top
 Profile  
 
 Post subject: Re: Analysis of 180 degree only 3x3x3 cube
PostPosted: Tue Nov 26, 2013 6:57 pm 
Offline
User avatar

Joined: Wed Jun 19, 2013 2:50 pm
Location: Deep in the Heart of Texas
I had a Rubik's Cube mini-course last year and we did this. The trick to solving is to do the corners first and the the edges using commutators and setup moves and such.

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


Top
 Profile  
 
 Post subject: Re: Analysis of 180 degree only 3x3x3 cube
PostPosted: Tue Nov 26, 2013 9:45 pm 
Offline
User avatar

Joined: Fri Nov 05, 2010 2:20 am
Location: Wherever
There is a weird situation that involves a 3-cycle of edges. What is the optimal solution from that?

_________________
A budding puzzle designer!

Check out my Shapeways shop!


Top
 Profile  
 
 Post subject: Re: Analysis of 180 degree only 3x3x3 cube
PostPosted: Tue Nov 26, 2013 10:20 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
rubikcollector123 wrote:
There is a weird situation that involves a 3-cycle of edges. What is the optimal solution from that?

I think the situation you're talking about is generated by [D', U, F'2, U', D, R'2].

I solve it with it with 4 applications of [R2, U2]x3 in different orientations. The full sequence is: [[R2, U2]x3, [F2, U2]x3]x2
No doubt there is a much shorter optimal sequence (since god's number is 15...).

I solve the 180 degree cube corners first and then combinations of [R2, U2]x3 for orbit parity fixing and [L2, B2, F2, R2, F2, B2] for an in-orbit 2-2 swap.

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


Top
 Profile  
 
 Post subject: Re: Analysis of 180 degree only 3x3x3 cube
PostPosted: Tue Nov 26, 2013 10:35 pm 
Offline
User avatar

Joined: Mon Dec 08, 2008 1:45 am
Location: New Zealand
I always enjoy trying different sorts of scrambles/solves on puzzles, such as 180 degree only turns, and slice only turns. (Slice only helicopter cube was quite fun!)

When I've done 180 degree only 3x3x3 solves before, I'd often run into the 3-cycle of edges mentioned above.

Starting with a cube generated by [D', U, F'2, U', D, R'2] as Brandon stated, I would then solve that with:
[[R2, U2]x3 (B2 L2 B2) [R2, U2]x3 (B2 L2 B2)]
Again, there is probably a much shorter sequence, but nothing I could come up with intuitively.

-Mark- :)

_________________
My Shapeways Shop!
Tony Fisher wrote:
A rare puzzle is one that is only lightly cooked.

Kelvin Stott wrote:
Squiggle is such a funny word to say out loud. Squiggle! :lol:

I am with Frank's Family


Top
 Profile  
 
 Post subject: Re: Analysis of 180 degree only 3x3x3 cube
PostPosted: Tue Nov 26, 2013 10:39 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
Allagem wrote:
Here's where it gets really weird. Every move toggles the parity of both corner orbits simultaneously, so it is clear that the parity of the two corner orbits must match, implying that the parity of the first orbit of corners determines the parity of the second orbit of corners making only even (or odd, if the other orbit so dictates) permutations of the second orbit of corners achievable, right? Wrong. Instead of the expected 4!/2 possible configurations for the final orbit of corners given the configuration of the rest of the pieces on the puzzle, only a mere 4 configurations are possible.
[...]
Groups of this kind seem to be very rare in the world of twisty puzzles. It has only cropped up a handful of times that I'm aware of: The second orbit of corners on a half-turn 3x3x3, the second orbit of corners on a Skewb, the corners of the Alternating Cube, the permutation of both edges and corners of a 3x3x3 restricted to the moves: U or R'FR, shown to me by Nan Ma (there are 6 edges involved but only 120 achievable permutations instead of the expected 6!=720 and there are 5 corners involved but only 10 of the expected 5!/2=60 are actually achievable). Based on these counter examples, I have a feeling this property is not rare among groups, but rather only rare among twisty puzzles. I must admit I do not fully understand why these instances occur, how to spot them without a rigorous analysis, or how to fully deal with them in a solving scenario. Does anyone have anything to add about these oddball normal groups? :D

Excellent analysis. I immediately thought of the Skewb corners but you've already mentioned those. One other interesting thing to mention about Skewb corners is that the total twist of the corners in one orbit is tied to the permutation of the corners in the other orbit. Twisty puzzles do have a lot of orientation of one type of pieces tied to the permutation (or sometimes just parity) of another type of piece.

I believe these restrictions only occur when there are orbits involved. Different pieces == different orbits. When you have one piece type split into multiple orbits as is the case in your above example (and some other puzzles) you have much more opportunity for intra-orbit dependence. The Complex 3x3x3 has some interesting parity, permutation, and orientation linkages among pieces.

Of particular note for the absence of strange phenomena is the permutation of pieces on the Complex Face Turning Dodecahedron. With 82 piece types (chiral == same piece type) I thought for sure there would be all sorts of really crazy permutation restrictions. After some GAP analysis we determined that beyond just the obvious linkages among the center-like and core-like pieces there are NO OTHER SURPRISES. Read from this post down for details.

Somewhere (I can't find a link) GuiltyBystander and I did some analysis of various geometries and found the edge-turning (modulo 2) geometries exhibit much more variation in terms of chiral piece types, total number of piece types, and orbits per piece. My bet is that a complex edge-turning-cube would have some really exotic intra-piece and intra-orbit relationships.

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


Top
 Profile  
 
 Post subject: Re: Analysis of 180 degree only 3x3x3 cube
PostPosted: Tue Nov 26, 2013 10:46 pm 
Offline
User avatar

Joined: Wed Jun 19, 2013 2:50 pm
Location: Deep in the Heart of Texas
Door wrote:
I always enjoy trying different sorts of scrambles/solves on puzzles, such as 180 degree only turns, and slice only turns. (Slice only helicopter cube was quite fun!)

When I've done 180 degree only 3x3x3 solves before, I'd often run into the 3-cycle of edges mentioned above.

Starting with a cube generated by [D', U, F'2, U', D, R'2] as Brandon stated, I would then solve that with:
[[R2, U2]x3 (B2 L2 B2) [R2, U2]x3 (B2 L2 B2)]
Again, there is probably a much shorter sequence, but nothing I could come up with intuitively.

-Mark- :)

That's exactly the algorithm I used to solve this type of scramble with. It ended up getting me to the first one to finish when I finally figured it out. I won a set of 3x3x3 stickers because Dr. Burridge, who competed in 1982 or 1983 (I forgot), knew I needed some for my old Rubik's brand.

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


Top
 Profile  
 
 Post subject: Re: Analysis of 180 degree only 3x3x3 cube
PostPosted: Tue Nov 26, 2013 10:49 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
Door wrote:
I always enjoy trying different sorts of scrambles/solves on puzzles, such as 180 degree only turns

Speaking of interesting ways to solve, when I'm looking for a fun way to solve a 3x3x3 I'll spend time reducing a scramble to what looks like a 180-degree scramble. That means only yellow-touching-white, green-touching-blue, and red-touching-orange. Then I solve the reduced puzzle using only 180 degree turns.

If the reduced puzzle isn't in the 180-degree subgroup then the only "parity" issue can be fixed with [U, F2, R2, U2, R2, U', R2, F2, U2, F2, U', R2, U2, F2] and I usually solve the puzzle such that the only messed up pieces are exactly solved by this sequence.

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


Top
 Profile  
 
 Post subject: Re: Analysis of 180 degree only 3x3x3 cube
PostPosted: Wed Nov 27, 2013 3:58 am 
Offline

Joined: Sun Oct 08, 2006 1:47 pm
Location: Houston/San Antonio, Texas
rubikcollector123 wrote:
There is a weird situation that involves a 3-cycle of edges. What is the optimal solution from that?
Brandon Enright wrote:
I solve it with it with 4 applications of [R2, U2]x3 in different orientations. The full sequence is: [[R2, U2]x3, [F2, U2]x3]x2
No doubt there is a much shorter optimal sequence (since god's number is 15...).
Door wrote:
Starting with a cube generated by [D', U, F'2, U', D, R'2] as Brandon stated, I would then solve that with:
[[R2, U2]x3 (B2 L2 B2) [R2, U2]x3 (B2 L2 B2)]
Again, there is probably a much shorter sequence, but nothing I could come up with intuitively.

The masses have spoken! There are 16 God's Algorithms for this configuration that can be solved optimally in 8 moves. These are all for one specific orientation (the equivalent of Mark's algorithm, the inverse of Brandon's), so reorienting these or taking the inverse will produce all possible 3-cycles (of course, 12 of these are already the inverse of a reorientation/mirror-image/both of the other 4). Pick your favorite one and have at it!
U² F² U² R² U² F² U² R²
U² F² U² L² D² B² D² L²
U² B² D² R² U² F² D² L²
U² B² D² L² D² B² U² R²
F² U² R² U² F² U² R² U²
F² U² L² D² B² D² L² U²
F² D² R² D² F² D² R² D²
F² D² L² U² B² U² L² D²
B² U² R² D² F² U² L² D²
B² U² L² U² B² D² R² D²
B² D² R² U² F² D² L² U²
B² D² L² D² B² U² R² U²
D² F² D² R² D² F² D² R²
D² F² D² L² U² B² U² L²
D² B² U² R² D² F² U² L²
D² B² U² L² U² B² D² R²
I love the power of a good program 8-) In case no one has noticed from my recent posts, I have written a program that can explore any small group (less than 10M elements if you want results within an hour), and find the number of positions at each distance from solved, finding God's Number in the process. I can also specify any specific configuration and find ALL of the optimal solutions to that configuration. I'd be happy to input any puzzle that someone has specific interest in (should I make a new topic for that?) Probably worth mentioning: Finding an optimal solve does not require exploring the whole group, only up to the depth required for the configuration in question. It also CAN handle indistinguishable pieces and treats them as such.

Peace,
Matt Galla


Top
 Profile  
 
 Post subject: Re: Analysis of 180 degree only 3x3x3 cube
PostPosted: Wed Nov 27, 2013 2:27 pm 
Offline
User avatar

Joined: Thu May 31, 2007 7:13 pm
Location: Bruxelles, Belgium
Allagem wrote:
-Here's where it gets really weird. Every move toggles the parity of both corner orbits simultaneously, so it is clear that the parity of the two corner orbits must match, implying that the parity of the first orbit of corners determines the parity of the second orbit of corners making only even (or odd, if the other orbit so dictates) permutations of the second orbit of corners achievable, right? Wrong. Instead of the expected 4!/2 possible configurations for the final orbit of corners given the configuration of the rest of the pieces on the puzzle, only a mere 4 configurations are possible. Upon closer inspection, these four are equivalent to: ABCD, BADC, CDAB, DCBA which is isomorphic to the Klein Four-Group, a group interesting enough to have its own name! (4)

I did my own calculation using GAP.
* The number of total configurations is 663552 and this coincides with your result.
* The size of edges-only 180°turn cube group is 6912.
* The size of corners-only 180°turn cube group is 96.
Since the first number is the product of the other two,
I guess both corner orbits depend each other but independent of edges.
And both corner orbit can take any value of Sym(4) , but if one is determined, the other can take one of 4 values. So there must be a projection to associate to each member of Sym(4), 4 members including itself. But how?
My guess is that both corner orbit permutations belong to the same equivalence class
induced by (Sym(4) / Klein Four-Group).
Is this what you mean?

_________________
Virtual Magic Polyhedra
Applet(Online)
Executable Jar Installer
Win32 Executable(Download)
troubleshooting


Top
 Profile  
 
 Post subject: Re: Analysis of 180 degree only 3x3x3 cube
PostPosted: Wed Nov 27, 2013 4:25 pm 
Offline

Joined: Mon Aug 18, 2008 10:16 pm
Location: Somewhere Else
(Anyone up for analyzing higher order half turn cubes? I'd love to read more about them.)


Top
 Profile  
 
 Post subject: Re: Analysis of 180 degree only 3x3x3 cube
PostPosted: Wed Nov 27, 2013 4:30 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
Jared wrote:
(Anyone up for analyzing higher order half turn cubes? I'd love to read more about them.)

The group they form is too big for a complete analysis like what Matt has done.

_________________
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: Exabot [Bot] and 4 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