View unanswered posts  View active topics

Page 1 of 1

[ 15 posts ] 

Author 
Message 
Aurum

Post subject: Floppy Cube Permutations? Posted: Wed May 06, 2009 7:28 am 

Joined: Tue Mar 10, 2009 7:54 am Location: Thailand

Does anyone know that how many combinations that a floppy cube can make? And the minimum moves to solve it is less than how many moves? (Is it 6 moves.)
sorry for my English.
_________________ Aurum  Thanawit Prasongpongchai WCA ID : 2009PRAS01 3x3x3  PB 10.27 sec, AVG(10/12) 16.61
Youtube channel : http://www.youtube.com/user/AurumThailandcube


Top 


TomZ

Post subject: Re: Floppy Cube Permutations? Posted: Wed May 06, 2009 8:02 am 

Joined: Fri Feb 08, 2008 1:47 am Location: near Utrecht, Netherlands


Top 


jaap

Post subject: Re: Floppy Cube Permutations? Posted: Wed May 06, 2009 8:16 am 

Joined: Wed Mar 15, 2000 9:11 pm Location: Delft, the Netherlands

Aurum wrote: Does anyone know that how many combinations that a floppy cube can make? 192. The edges can be flipped or not, giving 2^4=16 possibilities. The corners can be in any of the 4!=24 permutations. There is a parity constraint (the parity of the corner permutation is the same as the parity of the number of flipped edges). The total is therefore 16*24/2 = 192. Aurum wrote: And the minimum moves to solve it is less than how many moves? (Is it 6 moves.) 0: 1 1: 4 2: 10 3: 24 4: 53 5: 64 6: 31 7: 4 8: 1 That single position that needs 8 moves to solve is the 'superflip', the position with 4 flipped edges. Edited to add: Here's something amusing. Let P be the move sequence: L FRFRFRFRFRF L FRFRFRFR L RFRFRFRFRFR L RFRFRFRFRFR L R Then the move sequence PFPB PFPB is 192 moves long, and visits all possible positions exactly once, returning it to how it was at the beginning. So a blind person can always solve it by doing this sequence as long as there is someone there to say 'stop' when it is solved.
_________________ Jaap
Jaap's Puzzle Page: http://www.jaapsch.net/puzzles/


Top 


Garrett

Post subject: Re: Floppy Cube Permutations? Posted: Wed May 06, 2009 5:28 pm 

Joined: Wed Aug 01, 2007 3:14 pm Location: Orange County, CA

Then that would be God's Algorithm, correct?
_________________ Garrett


Top 


Blazemann

Post subject: Re: Floppy Cube Permutations? Posted: Wed May 06, 2009 5:29 pm 

Joined: Fri Nov 28, 2008 1:23 am

jaap wrote: Here's something amusing. Let P be the move sequence: L FRFRFRFRFRF L FRFRFRFR L RFRFRFRFRFR L RFRFRFRFRFR L R
Then the move sequence PFPB PFPB is 192 moves long, and visits all possible positions exactly once, returning it to how it was at the beginning. So a blind person can always solve it by doing this sequence as long as there is someone there to say 'stop' when it is solved. That is amazing. Though quite long to memorize, still amazing.


Top 


Alex

Post subject: Re: Floppy Cube Permutations? Posted: Thu May 07, 2009 12:30 am 

Joined: Sat Jan 14, 2006 9:36 am Location: Europe

Garrett wrote: Then that would be God's Algorithm, correct? If you're refering to the 192moves sequence, then no. That sequence places all possible positions in a cycle and it can take a huge number of moves (huge = more than 8) to get from a chosen state to the solved state. God's algorithm would give you a tree with the solved state on top (level 1) and superflip on the bottom (level 8). Every move upwards would bring you closer to the solved state. To solve the cube in the optimal way you'd just have to find your position in the tree and follow the path up. Actually, I don't think constructing this tree for the floppy cube would be that difficult or time consuming. Would it?


Top 


qqwref

Post subject: Re: Floppy Cube Permutations? Posted: Thu May 07, 2009 3:04 am 

Joined: Sat Jan 22, 2005 12:12 pm Location: NY, USA


Top 


jaap

Post subject: Re: Floppy Cube Permutations? Posted: Thu May 07, 2009 4:56 am 

Joined: Wed Mar 15, 2000 9:11 pm Location: Delft, the Netherlands

qqwref wrote: Yeah, I've been wondering, how did you find a Devil's Algorithm, jaap? First I halved the problem by considering the group generated by <F,R,L>. This group generates all positions where the B edges is not flipped. I found (see below) a 96move devil's algorithm for that, say X, which also returns it to its starting state. By cyclicly shifting X, I made sure it started with an F move. Say, X=FY. Then Y is 95 moves long, has the same effect as F, and together with the position you start with it visits all 96 positions. Then YBYB must be a Devil's algorithm for the whole group that returns it to its starting position because the first Y visits all positions with the B edge unflipped, B flips it, the second Y then visits all positions with the B edge flipped, and the final B returns it to the starting position because YBYB=FBFB does nothing. By making sure X started with an F and removing it, the end result of YBYB returns to its starting position. If I had removed an L or R move instead, then YBY would still be a 191move Devil's algorithm but you couldn't follow it by a single move to get it back to start. Now to explain how I found X. In a way I did the same thing. Suppose I don't move L and just use F and R. This affects 3 corners and 2 edges, and there are 12 positions they can be in. There happens to be a nice Devil's algorithm for that small group, namely (FR)6. Any of the 96 positions falls into a set of 12 that are connected by the moves (FR)6, and such a set of 12 positions all have the same corner piece at BL and the same L edge orientation. There are 8 such sets because 96/12=8 and because there are 4 possible corners at BL and 2 orientations for the L edge. This time I remove an F from (FR)6 to get Z = RFRFRFRFRFR. Unfortunately LZ has order 6 because (LZ)6=(LF)6=I. So (LZ)6 visits only 6 of the 8 sets, or 72 of the 96 positions. By replacing two of the R moves by a detour L FRFRFRFRFRF L it manages to visit those two missing sets as well. Note that L FRFRFRFRFRF L has the same effect as R because this time I removed an R from (FR)6, so L FRFRFRFRFRF L = LRL = R. To help me with the last part, I had my computer draw the 96node graph, with edges of different colours between them to represent the moves. By using that I could more easily see what was happening. I also wrote a little program that actually checked whether a move sequence is indeed a Devil's algorithm.
_________________ Jaap
Jaap's Puzzle Page: http://www.jaapsch.net/puzzles/


Top 


KelvinS

Post subject: Re: Floppy Cube Permutations? Posted: Thu May 07, 2009 5:24 am 

Joined: Mon Mar 30, 2009 5:13 pm

Blazemann wrote: jaap wrote: Here's something amusing. Let P be the move sequence: L FRFRFRFRFRF L FRFRFRFR L RFRFRFRFRFR L RFRFRFRFRFR L R
Then the move sequence PFPB PFPB is 192 moves long, and visits all possible positions exactly once, returning it to how it was at the beginning. So a blind person can always solve it by doing this sequence as long as there is someone there to say 'stop' when it is solved. That is amazing. Though quite long to memorize, still amazing. Incredible, I agree. Jaap  shouldn't you be using your obvious talents to develop a solution to the global economic/climate/energy/food crisis, or something ?!!
_________________ If you want something you’ve never had, you’ve got to do something you’ve never done  Thomas Jefferson


Top 


Andreas Nortmann

Post subject: Re: Floppy Cube Permutations? Posted: Fri May 08, 2009 10:09 am 

Joined: Mon Aug 02, 2004 7:03 am Location: Koblenz, Germany


Top 


qqwref

Post subject: Re: Floppy Cube Permutations? Posted: Fri May 08, 2009 4:16 pm 

Joined: Sat Jan 22, 2005 12:12 pm Location: NY, USA


Top 


Allagem

Post subject: Re: Floppy Cube Permutations? Posted: Sat May 09, 2009 2:00 am 

Joined: Sun Oct 08, 2006 1:47 pm Location: Houston/San Antonio, Texas

qqwref wrote: I had Mathematica draw a graph of the Floppy Cube positions. Each dot is a position and each line represents a possible move. http://i286.photobucket.com/albums/ll11 ... eGraph.pngThat's pwetty...... Just out of curiosity, how are all the positions organized? What aspect of a given position places it at a specific point around the perimeter? Where is the solved postition and where is the superflip? It looks way to uniform to be random, so you must have used something. Peace, Matt Galla PS I was actually thinking about trying to do this by hand, but I'm glad you did it first. I gues I don't realize how big 192 still is, despite looking so small for a puzzle


Top 


jaap

Post subject: Re: Floppy Cube Permutations? Posted: Sat May 09, 2009 4:07 am 

Joined: Wed Mar 15, 2000 9:11 pm Location: Delft, the Netherlands

Allagem wrote: Just out of curiosity, how are all the positions organized? What aspect of a given position places it at a specific point around the perimeter? Where is the solved postition and where is the superflip? It looks way to uniform to be random, so you must have used something. Read this: http://www.jaapsch.net/puzzles/cayley.htmSuch graphs are always highly symmetric, and by restickering the puzzle any one of those points can represent the starting position. Allagem wrote: PS I was actually thinking about trying to do this by hand, but I'm glad you did it first. I gues I don't realize how big 192 still is, despite looking so small for a puzzle You can reduce the number by identifying those that are merely rotations/reflections of each other. Then there is only 1 position one move from start, and only 2 that are two moves from start (one represents both LR and FB, the other represents FR, FL, RF, RB, BR, BL, LF, LB). Then you only have 37 essentially different positions left, but their graph is not so symmetric any more.
_________________ Jaap
Jaap's Puzzle Page: http://www.jaapsch.net/puzzles/


Top 


qqwref

Post subject: Re: Floppy Cube Permutations? Posted: Sat May 09, 2009 5:12 am 

Joined: Sat Jan 22, 2005 12:12 pm Location: NY, USA

Allagem wrote: That's pwetty...... Just out of curiosity, how are all the positions organized? What aspect of a given position places it at a specific point around the perimeter? Where is the solved postition and where is the superflip? It looks way to uniform to be random, so you must have used something. Surprisingly enough... I don't know. The way I represented the Floppy Cube was as a direct product of the numbers from 0 to 15 (representing edge orientation, (Z2)^4) and the permutations of 4 elements (corner permutation). This gave twice as many elements because of parity, so I just kept one part. The way the vertices are organized is thus somewhat haphazard, although I can tell you that (for instance) all of the vertices with the same edge orientation should be grouped together, if you choose the first one to be the start. There are much more symmetric embeddings of this graph, but I don't know how to find them. Interestingly, now that I have the graph, if I label the vertices I can do things like finding a Hamiltonian Cycle (Devil's Algorithm, like what Jaap posted), and a bunch of other graphtheoretic operations which have interesting consequences for cubing.
_________________ My official times My youtube Puzzle Solving Service!  a puzzle that has never been scrambled and solved has been wasted.


Top 


SamBegley

Post subject: Re: Floppy Cube Permutations? Posted: Thu Jul 21, 2011 2:33 pm 

Joined: Sun Jul 17, 2011 10:50 pm Location: Nebraska

I wrote out God's method, but it's 12 pages of algorithms so I need to write it on less pages before I can put it here.


Top 



Page 1 of 1

[ 15 posts ] 

Who is online 
Users browsing this forum: No registered users and 7 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


