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

TwistyPuzzles.com Forum

It is currently Mon Apr 21, 2014 8:00 am

All times are UTC - 5 hours



Post new topic Reply to topic  [ 15 posts ] 
Author Message
 Post subject: Floppy Cube Permutations?
PostPosted: Wed May 06, 2009 7:28 am 
Offline
User avatar

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
Image
Youtube channel : http://www.youtube.com/user/AurumThailandcube


Top
 Profile  
 
 Post subject: Re: Floppy Cube Permutations?
PostPosted: Wed May 06, 2009 8:02 am 
Offline
User avatar

Joined: Fri Feb 08, 2008 1:47 am
Location: near Utrecht, Netherlands
Combinations: 4!*2^3=192

God's Algorithm: I have no clue

_________________
Tom's Shapeways Puzzle Shop - your order from my shop includes free stickers!
Tom's Puzzle Website


Buy my mass produced puzzles at Mefferts:
- 4x4x6 Cuboid for just $38
- Curvy Copter for just $18
- 3x4x5 Cuboid for just $34


Top
 Profile  
 
 Post subject: Re: Floppy Cube Permutations?
PostPosted: Wed May 06, 2009 8:16 am 
Offline
User avatar

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
 Profile  
 
 Post subject: Re: Floppy Cube Permutations?
PostPosted: Wed May 06, 2009 5:28 pm 
Offline
User avatar

Joined: Wed Aug 01, 2007 3:14 pm
Location: Orange County, CA
Then that would be God's Algorithm, correct?

_________________
-Garrett


Top
 Profile  
 
 Post subject: Re: Floppy Cube Permutations?
PostPosted: Wed May 06, 2009 5:29 pm 
Offline
User avatar

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
 Profile  
 
 Post subject: Re: Floppy Cube Permutations?
PostPosted: Thu May 07, 2009 12:30 am 
Offline
User avatar

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 192-moves 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? :D


Top
 Profile  
 
 Post subject: Re: Floppy Cube Permutations?
PostPosted: Thu May 07, 2009 3:04 am 
Offline

Joined: Sat Jan 22, 2005 12:12 pm
Location: NY, USA
Yeah, I've been wondering, how did you find a Devil's Algorithm, jaap?

_________________
My official times
My youtube
Puzzle Solving Service! - a puzzle that has never been scrambled and solved has been wasted.


Top
 Profile  
 
 Post subject: Re: Floppy Cube Permutations?
PostPosted: Thu May 07, 2009 4:56 am 
Offline
User avatar

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 96-move 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 191-move 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 96-node 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
 Profile  
 
 Post subject: Re: Floppy Cube Permutations?
PostPosted: Thu May 07, 2009 5:24 am 
Offline
User avatar

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. :shock:

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
 Profile  
 
 Post subject: Re: Floppy Cube Permutations?
PostPosted: Fri May 08, 2009 10:09 am 
Offline
User avatar

Joined: Mon Aug 02, 2004 7:03 am
Location: Koblenz, Germany
Jaap kind of quoted here from his own page:
http://www.jaapsch.net/puzzles/subgroup.htm
The Floppy cube is a physical implementation of subgroup 4a of the 3x3x3.


Top
 Profile  
 
 Post subject: Re: Floppy Cube Permutations?
PostPosted: Fri May 08, 2009 4:16 pm 
Offline

Joined: Sat Jan 22, 2005 12:12 pm
Location: NY, USA
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.png

_________________
My official times
My youtube
Puzzle Solving Service! - a puzzle that has never been scrambled and solved has been wasted.


Top
 Profile  
 
 Post subject: Re: Floppy Cube Permutations?
PostPosted: Sat May 09, 2009 2:00 am 
Offline

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.png



That's pwetty...... :shock:
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. :lol: I gues I don't realize how big 192 still is, despite looking so small for a puzzle


Top
 Profile  
 
 Post subject: Re: Floppy Cube Permutations?
PostPosted: Sat May 09, 2009 4:07 am 
Offline
User avatar

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.htm
Such 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. :lol: 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
 Profile  
 
 Post subject: Re: Floppy Cube Permutations?
PostPosted: Sat May 09, 2009 5:12 am 
Offline

Joined: Sat Jan 22, 2005 12:12 pm
Location: NY, USA
Allagem wrote:
That's pwetty...... :shock:
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 graph-theoretic 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
 Profile  
 
 Post subject: Re: Floppy Cube Permutations?
PostPosted: Thu Jul 21, 2011 2:33 pm 
Offline

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
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 15 posts ] 

All times are UTC - 5 hours


Who is online

Users browsing this forum: Google Adsense [Bot] and 5 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