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

TwistyPuzzles.com Forum

It is currently Sat Apr 19, 2014 8:22 pm

All times are UTC - 5 hours



Post new topic Reply to topic  [ 15 posts ] 
Author Message
 Post subject: Puzzle Theory: How many ways can one bandage a Rubik's Cube?
PostPosted: Mon Nov 05, 2012 12:59 pm 
Offline
User avatar

Joined: Thu Dec 02, 2004 12:09 pm
Location: Missouri
All,

Back in June, Oskar, Andreas, and myself had an email exchange on this topic. It came to me today there might actually be a way to come up with a finite answer to that question.

Think of the following types of bandaging:

Glue cubies together: http://www.twistypuzzles.com/cgi-bin/puzzle.cgi?pkey=613
Tom's Constrained Cube: http://twistypuzzles.com/forum/viewtopic.php?f=15&t=18922
Oskar's Half Turn Cube: http://www.twistypuzzles.com/cgi-bin/puzzle.cgi?pkey=1518
Latch Cube: http://twistypuzzles.com/cgi-bin/puzzle.cgi?pkey=1752
Slice Cube: Half of this puzzle http://twistypuzzles.com/cgi-bin/puzzle.cgi?pkey=1564
Oskar's Geary Cube: http://twistypuzzles.com/cgi-bin/puzzle.cgi?pkey=1503
My Multi Gear Cube Kit: http://twistypuzzles.com/cgi-bin/puzzle.cgi?pkey=3509
Oskar's Nightmare 3x3x3 idea: http://twistypuzzles.com/forum/viewtopic.php?f=9&t=23903
Ropes can be used to bandage a 3x3x3: http://twistypuzzles.com/cgi-bin/puzzle.cgi?pkey=3030
Arch Wolf's 3³ concept: http://twistypuzzles.com/forum/viewtopic.php?f=9&t=18667
Hooks can be used: http://twistypuzzles.com/cgi-bin/puzzle.cgi?pkey=1122
Oskar's Cube Bouchon: http://www.shapeways.com/model/612583/cube-bouchon.html
Oskar's Variomatic Cube: http://www.shapeways.com/model/585543/variomatic-cube.html
Oskar's Polo Gears: http://twistypuzzles.com/cgi-bin/puzzle.cgi?pkey=2581
Oskar's Good Neighbor Cube: http://www.shapeways.com/model/612844
Oskar's Opposition Cube: http://www.shapeways.com/model/626112
Oskar's Enabler Cube: http://www.shapeways.com/model/676938
Compass Cube: http://twistypuzzles.com/forum/viewtopic.php?f=15&t=23891
Mayan Cube: http://twistypuzzles.com/cgi-bin/puzzle.cgi?pkey=3507
Wolf & Sheep cube: http://www.twistypuzzles.com/forum/viewtopic.php?f=15&t=24571
Jailbreak Cube (or Latch III Cube): http://www.twistypuzzles.com/forum/viewtopic.php?f=15&t=24259
Bingo cube: http://twistypuzzles.com/forum/viewtopic.php?f=8&t=24137
Limitation Cube: http://twistypuzzles.com/cgi-bin/puzzle.cgi?pkey=3620

Gluing cubies together would include gluing face centers to the core and bridge bandaging: http://twistypuzzles.com/cgi-bin/puzzle.cgi?pkey=1947
Ropes could also be used inside the 3x3x3: http://twistypuzzles.com/forum/viewtopic.php?f=15&t=13524
Extentions could also be added to further hinder the ropes: http://twistypuzzles.com/cgi-bin/puzzle.cgi?pkey=2975

What wouldn't be included as a Bandaged Rubiks Cube:
The Button Cube: http://twistypuzzles.com/cgi-bin/puzzle.cgi?pkey=2039 as it intruduces new pieces to solve and additional types of turns.
The Gear Cube, Anisotropic Cube, and Even Less Gears as the gears themselves are introduced as new parts to solve. Take the stickers (and orientation information) off the grears and they'd be included (as in the Multi Gear Cube Kit).

And I'm sure there are other types of bandaging that I've skipped. So how can one realistically be expected to count the number of possible ways a Rubik's Cube can be bandaged. Here is the idea that came to me today. Lets look at the number of states the Super Rubik's Cube has:

88,580,102,706,155,225,088,000 states or nodes

Now lets think of these as nodes on a graph where each state is connected to the other states which can be reached with a single turn. Each of these connections (lines on this graph) can be bandaged or removed from the graph. In cases like the Geary Cube where the L and R faces turn at the same time you can think of this as starting at state X and going to state Y where just the R face has been turn and then the only line out of state Y would be to state Z where the L face was turned in the appropraite direction. So ALL the above bandaged puzzles can be viewed as a subset of this connectivity graph of the Rubik's Cube. So how many connections are there in the graph? I think its 6 times the number of states above. Each state should have 12 lines coming out of it leading to another state as each of 6 faces can be turned clockwise or counter-clockwise.

So lets look at the set of these connections. How many subsets does this set have? The subset with no connections blocked is the Rubik's Cube. The subset with all connections blocked is the 1x1x1. I was VERY tempted to say this was the number we are after however I think this is just an upper limit as I see one problem. I believe certain subsets could break this graph into 2 or more disjoint graphs. Only the portion of the graph which still contains the solution state is the puzzle in question. Removing or blocking more connections in a disjointed portion not connected to the solution state doesn't increase the number of bandaged Rubik's Cube's which could be made.

I believe the number of subsets is 2^(6*88,580,102,706,155,225,088,000) which I can't perform at the moment. So any ideas on how to get a good lower bound on the number of possible Rubik's Cube bandagings possible? Or can perform the above operation?

Thanks,
Carl

P.S. Maybe this is obvious and no value added but its something that just popped into my head today.

_________________
-
Image

Image


Last edited by wwwmwww on Tue Nov 06, 2012 3:45 pm, edited 3 times in total.

Top
 Profile  
 
 Post subject: Re: Puzzle Theory: How many ways can one bandage a Rubik's C
PostPosted: Mon Nov 05, 2012 1:21 pm 
Offline
User avatar

Joined: Mon Mar 30, 2009 5:13 pm
Surely the number of potential ways to bandage a 3x3x3 is given by the number of potential combinations of combinations = 2^(4.3*10^19)

This would include all means of virtual bandaging, which may not be physically possible, but would be possible on a computer to disallow any combination of specific combinations.

_________________
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: Puzzle Theory: How many ways can one bandage a Rubik's C
PostPosted: Mon Nov 05, 2012 1:39 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
wwwmwww wrote:
[...]I believe the number of subsets is 2^(6*88,580,102,706,155,225,088,000) which I can't perform at the moment. So any ideas on how to get a good lower bound on the number of possible Rubik's Cube bandagings possible? Or can perform the above operation?


I don't see where the extra factor of of 6 comes from.

But you're right that the total number of subset is 2^|total elements in group|

No computer can perform 2^(6 * 88,580,102,706,155,225,088,000) because the resulting number would need 6*88,580,102,706,155,225,088,000 bits to represent. Just 2^88,580,102,706,155,225,088,000 needs 9604 Exabytes. See https://en.wikipedia.org/wiki/Exabyte#Practical_comparisons.

I think 2^your number is a big overestimate. Most subsets can't be reached because you still need a connected graph as the result. How many connected graph subsets can you make from this? I dunno how to get a handle on that but it's tiny compared to the number of subsets.

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


Top
 Profile  
 
 Post subject: Re: Puzzle Theory: How many ways can one bandage a Rubik's C
PostPosted: Mon Nov 05, 2012 3:12 pm 
Offline
User avatar

Joined: Thu Dec 02, 2004 12:09 pm
Location: Missouri
KelvinS wrote:
Surely the number of potential ways to bandage a 3x3x3 is given by the number of potential combinations of combinations = 2^(4.3*10^19)
The problem with 4.3*10^19 is this number doesn't include face center orientation information which can play a role in bandaging.
bmenrigh wrote:
I don't see where the extra factor of of 6 comes from.
The 6 comes about as I'm counting connections and not states/nodes. There is probably a graph theory term for what I'm calling connections but I'm thinking of it as a line which contects any two states which are only 1 turn apart. The way I see it, each each node should have 12 connections as each of 6 faces can be turned and each face can be turned either clockwise or counter-clockwise. The 12 gets reduced back down to 6 because if you just took number of nodes times the number of connections at each you'd be double counting the connestions as each connection is shared between two nodes. Make sense? Keep in mind my background is physics and NOT math so I could certainly be doing something stupid.
bmenrigh wrote:
But you're right that the total number of subset is 2^|total elements in group|
Yes, I googled that before my first post. In hind sight it's obvious but I didn't know that before looking it up.
bmenrigh wrote:
No computer can perform 2^(6 * 88,580,102,706,155,225,088,000) because the resulting number would need 6*88,580,102,706,155,225,088,000 bits to represent. Just 2^88,580,102,706,155,225,088,000 needs 9604 Exabytes. See https://en.wikipedia.org/wiki/Exabyte#Practical_comparisons.
Aren't their programs like Mathematica which can deal with these very large numbers? Ok... maybe I've jumped into a realm of numbers even bigger then the stuff I've seen Mathematica deal with.
bmenrigh wrote:
I think 2^your number is a big overestimate. Most subsets can't be reached because you still need a connected graph as the result. How many connected graph subsets can you make from this? I dunno how to get a handle on that but it's tiny compared to the number of subsets.
By connected you mean all the nodes are still a part (i.e. connected) to one graph... correct? If yes, I agree. That is what I meant by talking about disjoint graphs above. As my background isn't math I'm sure my terminology isn't the most standard. To explain what I mean above let me give you an example. Let's consider the set of all connections of the super Rubik's Cube. All (6*88,580,102,706,155,225,088,000) of them if my counting is correct. From this set I could remove the 12 connections leading away from the solution node. If I did that my puzzle would become a 1x1x1 as I'd have no possible way to scramble it. If I continued to remove more then these 12 connections I still have the same 1x1x1 puzzle. So ALL subsets which contains these 12 connections should be counded JUST as one possible bandaging. So yes, I'm sure this is an over estimate. Actually even the set of all possible connected graphs (if I'm understanding your meaning correctly) may still actually be an over estimate. In my mind the final connected graph STILL needs to contain the solution node. I believe you could obtain a connected graph that had this point cut out but in that case what you have should be a copy of another net/graph where one of the points left could be mapped 1-to-1 with a net/graph which DID contain the solution node.

Heck, even in the subset of connected nets/graphs that contain the solution node you would end up with many copies (ok... Battle Star Galatica just popped into me head) where the only difference between them would be which node you considered the solution node. Think of a bandaged cube which has been scrambled and re-stickered with a new solution state. Should this be considered as a new way to bandage a Rubik's Cube? I'm honestly not sure.

So yes, I'm sure this is a very large over estimate. I'm just not sure how to work this problem from the other direction. How do I go about coming up with a lower bound that means something?

Carl

_________________
-
Image

Image


Last edited by wwwmwww on Mon Nov 05, 2012 3:36 pm, edited 1 time in total.

Top
 Profile  
 
 Post subject: Re: Puzzle Theory: How many ways can one bandage a Rubik's C
PostPosted: Mon Nov 05, 2012 3:28 pm 
Offline
User avatar

Joined: Fri Feb 08, 2008 1:47 am
Location: near Utrecht, Netherlands
The actual outcome of the 2^88,580,102,706,155,225,088,000 computation is entirely uninteresting. It's just a freaking large number. You could never represent it exactly, only using scientific notation or something like that.
For the record, it has on the order 10^22 DIGITS, so the number itself is of the order 10^(10^22) (give or take a few powers of ten).

Surprise: The binary representation is an 1 followed by 88,580,102,706,155,225,088,000 zeroes.

The "line" you are referring to is called "edge".

_________________
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: Puzzle Theory: How many ways can one bandage a Rubik's C
PostPosted: Mon Nov 05, 2012 3:34 pm 
Offline
User avatar

Joined: Thu Dec 02, 2004 12:09 pm
Location: Missouri
And if anyone can think of a type of bandaging I left out above or a good example of a specific type that I failed to mention please feel free to mention them here. Reading my own list where I mention Latch Cube and the Latch III Cube I figured I better check and see if there was a Latch II Cube and in that seach I also found a Latch IV Cube.

Crossroad Cube (or Latch IV Cube) appears to be just an new presentation of Glue bandaging.
Okamoto & Haseda Quarter Cube from Japan (Latch cube II) appears to be a subset of Tom's Constrained Cube.

Carl

_________________
-
Image

Image


Last edited by wwwmwww on Mon Nov 05, 2012 3:50 pm, edited 2 times in total.

Top
 Profile  
 
 Post subject: Re: Puzzle Theory: How many ways can one bandage a Rubik's C
PostPosted: Mon Nov 05, 2012 3:38 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
Carl my math is terrible too. Even though computer science is a branch of math I was more exposed to calculus and linear algebra than to graph theory :(

I think the graph you're envisioning has states as nodes / vertices and the moves that take you from state to state are edges.

These graphs are a special type of graph called a Caley graph (a graph that represents a group is a Caley graph) https://en.wikipedia.org/wiki/Cayley_graph

Not surprisingly, Jaap has already thought a lot about the Caley graphs for twisty puzzles and written some of that material up here:
http://www.jaapsch.net/puzzles/cayley.htm

These articles won't answer your question but at least should provide a supporting framework for you to better frame your question.

Also, if you want to properly represent the latch cube as a graph, it must be a directed graph. It's probably better to leave out the latch cube and other bandaging techniques that force the graph to be directed rather than undirected.

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


Top
 Profile  
 
 Post subject: Re: Puzzle Theory: How many ways can one bandage a Rubik's C
PostPosted: Mon Nov 05, 2012 4:19 pm 
Offline
User avatar

Joined: Thu Dec 02, 2004 12:09 pm
Location: Missouri
TomZ wrote:
The actual outcome of the 2^88,580,102,706,155,225,088,000 computation is entirely uninteresting. It's just a freaking large number.
Its interest to me solely is its the most meaninful upper bound of the number of ways to bandage a Rubik's Cube that I have seen. I'm sure its possible to do better. That is in part why I started this thread. I have yet to see a meaningful lower bound.
TomZ wrote:
The "line" you are referring to is called "edge".
Thanks for the info on the correct terminology.
bmenrigh wrote:
Carl my math is terrible too.
Thanks for the links. They were very informative and certainly point out my sloppy use of terminology. ;)
bmenrigh wrote:
These articles won't answer your question but at least should provide a supporting framework for you to better frame your question.
The ultimate question is simply "How many ways are there to bandage a Rubik's Cube?" I may be approacing this from the totally wrong (or at least inefficient) direction so I'm curious what other ways there are to approach this question.
bmenrigh wrote:
Also, if you want to properly represent the latch cube as a graph, it must be a directed graph. It's probably better to leave out the latch cube and other bandaging techniques that force the graph to be directed rather than undirected.
Arg... good point. Another can of worms I hadn't seen. But I do consider the Latch Cube a valid bandaging of the Rubik's Cube. So I guess I should just double the number of edges in my graph. In the Super Rubik's Cube each node then has 24 edges. 12 would be directed toward it and 12 would be directed away from it. So this means the upperbound is then 2^(12 * 88,580,102,706,155,225,088,000). Just another step in the wrong direction but at least its a real upper bound that I understand where it comes from. I'm hoping others can do better or have an idea how to even approach this from the lower bound side of things.

Carl

P.S. Maybe the question that should be asked first is how many ways are there to bandage a 2x2x2? Maybe there is something to be learned there that would make it easier to approach the 3x3x3 problem.

_________________
-
Image

Image


Top
 Profile  
 
 Post subject: Re: Puzzle Theory: How many ways can one bandage a Rubik's C
PostPosted: Tue Nov 06, 2012 1:56 pm 
Offline
User avatar

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

I am afraid you missed the recently added "Limitation":
http://twistypuzzles.com/cgi-bin/puzzle.cgi?pkey=3620

You entered the same link for
Tom's Constrained Cube and Oskar's Half Turn Cube
which are #2 and #3 on your list.

The "Slice Cube" is one of the bandaged puzzles implementable by the bridges you mention later. Therefore it is mentioned twice.

Those were the easy things:
I see another problem with your number 6 in 2^(6*88*10^21)
You explained where do you get the number 6 from and thereby explained that your posting is based on a QuarterTurnMetric.
All nodes which remain in the HalfTurnsCube have a distance of 2 in the original graph. The HalfTurnCubes introduces some kinds of "jumps" in your QuarterTurnMetric-graph.
Switching over to FaceTurnMetric does not solves this problem because of things like the GearCube. There each "move" still consists of two moves of the FaceTurnMetric Rubiks Cube.

Andreas


Top
 Profile  
 
 Post subject: Re: Puzzle Theory: How many ways can one bandage a Rubik's C
PostPosted: Tue Nov 06, 2012 3:39 pm 
Offline
User avatar

Joined: Sat Sep 15, 2012 7:42 am
The word "bandaged" is fine for cubes that are actually bandaged together [= proper bandaging]. It's easy enough to extend this to situations where the pieces to be joined are not adjacent [= virtual / disjoint bandaging]. This concept makes sense. However, some of these other situations seem like different concepts entirely.

With a bandaged cube, vertices / nodes are removed from the Cayley graph in addition to edges. With some of these other types of bandaging, it's possible that only edges are removed. To me, this is not the same thing and allows for some completely trivial [and therefore uninteresting] situations. For instance, suppose you designed a cube with the most trivial of "bandaging": a cube which cannot make a U turn from the solved state. You have removed exactly one edge from the Cayley graph. If you allow things like this, the number will be absurdly large and therefore meaningless as TomZ stated. Even restricting ourselves to connected subgraphs would be insane.

I think the more meaningful idea is to talk about proper bandaging and it's extension to virtual / disjoint bandaging. Then you can look at the number of ways of bandaging 2 pieces, 3 pieces, 4 pieces, etc. It reminds me of the partition function from discrete mathematics.

_________________
Call me Seth :)

Crazy2Face & Crazy3Face Puzzle Spreadsheet
Named 3x3x3 Bandaging Patterns


Top
 Profile  
 
 Post subject: Re: Puzzle Theory: How many ways can one bandage a Rubik's C
PostPosted: Tue Nov 06, 2012 4:16 pm 
Offline
User avatar

Joined: Thu Dec 02, 2004 12:09 pm
Location: Missouri
Andreas Nortmann wrote:
I am afraid you missed the recently added "Limitation":
http://twistypuzzles.com/cgi-bin/puzzle.cgi?pkey=3620
Thanks. This has now been added.
Andreas Nortmann wrote:
You entered the same link for
Tom's Constrained Cube and Oskar's Half Turn Cube
which are #2 and #3 on your list.
Thanks again. I've now corrected this.
Andreas Nortmann wrote:
The "Slice Cube" is one of the bandaged puzzles implementable by the bridges you mention later. Therefore it is mentioned twice.
Agreed. However its a nice specific example people are familiar with. One could also say the Bingo Cube is a subset of the Enabler Cube yet I mention both of those on the list.
Andreas Nortmann wrote:
Those were the easy things:
I see another problem with your number 6 in 2^(6*88*10^21)
You explained where do you get the number 6 from and thereby explained that your posting is based on a QuarterTurnMetric.
All nodes which remain in the HalfTurnsCube have a distance of 2 in the original graph. The HalfTurnCubes introduces some kinds of "jumps" in your QuarterTurnMetric-graph.
Switching over to FaceTurnMetric does not solves this problem because of things like the GearCube. There each "move" still consists of two moves of the FaceTurnMetric Rubiks Cube.
I tried to address this in my first post. I don't believe the Quarter Turn Metric is a problem here. Allow me to explain way. Let's look at the graph for the full Super Rubik's Cube. Now imagine we are just looking at 3 states. Those being the solved state (lets call this A), the state that differs from the solved state by a clockwise R-turn (lets call this B), and the state that differs from the solved state by a half turn of the R face (lets call this C). In the full cube each state has 12 edges coming out of it. There is one edge between A and B and one edge between B and C but no edges between A and C. For one to view the Half Turn Cube as a subset of these same edges one just removes the 6 counter clock-wise face turns from states A and C so these states now have 6 remaining edges. State B only has one egde coming into it from state A (a clock wise turn of the R face) and it only has one other edge going out of it to state C (another clock wise turn of the R face). In this sense the state B doesn't really exist but is now just part of the edge from A to C. In some sense you could define a state "X" of a normal 3x3x3 which was just a 45 degree turn of the R-face and it would look the same. So I view the Half Turn Cube, and all the Gear Cubes as subsets of this QuarterTurnMetric picture, at least as far as counting bandaged states go.

There is a problem here though that didn't hit me till last night. This picture doesn't work with the Rope bandaging. In the above cases if I start with the solved cube and make 4 clockwise turns of the R face I'm back in the solved state. With Rope bandaging these two states may differ as the state of the rope itself could be different. My first thought was you could address this by adding a counter to each face center which counted up for each full clockwise rotation away from the solved state and counted down for each full counter clockwise rotation away from the solved state. This however means we now have an infinite number of states, which means an infinite number of edges, and therefore and infinite number of ways to bandage a Rubik's Cube. However I think its even worse than that. Let's say I know the state of all the cubes/stickers and the value on the counter for each of the face centers... I still don't think one has enough information to determine the state of all the robes. Let's assume there are two ropes and each connects two edges. I believe the cube could get into a specific state (cubie location and orientation AND the same value for each center counter) in multiple ways. If so the state of the ropes depends not just on the current state of the cube but ALSO on the particular path the cube took to get to that state from the solved state.

Carl

_________________
-
Image

Image


Last edited by wwwmwww on Wed Nov 07, 2012 1:30 pm, edited 2 times in total.

Top
 Profile  
 
 Post subject: Re: Puzzle Theory: How many ways can one bandage a Rubik's C
PostPosted: Tue Nov 06, 2012 4:41 pm 
Offline
User avatar

Joined: Thu Dec 02, 2004 12:09 pm
Location: Missouri
themathkid wrote:
The word "bandaged" is fine for cubes that are actually bandaged together [= proper bandaging]. It's easy enough to extend this to situations where the pieces to be joined are not adjacent [= virtual / disjoint bandaging]. This concept makes sense. However, some of these other situations seem like different concepts entirely.
Granted this place has multiple definitions of bandaging floating around (as with most other terms). Some use bandaging to describe what I'd call Glue Bandaging and that appears to be the way you are using it. I'm thinking of it as basically any set or restrictions that can be applied to a Rubik's Cube.
themathkid wrote:
With a bandaged cube, vertices / nodes are removed from the Cayley graph in addition to edges. With some of these other types of bandaging, it's possible that only edges are removed.
Agreed... nodes can be cut out entirely or even absorbed into new edges as I described above. However the Cayley graph of the new bandaged puzzle should still be a subset of the full Cayley graph of the Super Rubik's Cube. If this then becomes part of my definition of bandaging then I guess I shouldn't consider Rope bandaging in this discussion. (see my post above)
themathkid wrote:
To me, this is not the same thing and allows for some completely trivial [and therefore uninteresting] situations. For instance, suppose you designed a cube with the most trivial of "bandaging": a cube which cannot make a U turn from the solved state. You have removed exactly one edge from the Cayley graph. If you allow things like this, the number will be absurdly large and therefore meaningless as TomZ stated.
Yes, that would be a trivial difference but I'd still consider it a valid bandaging and I feel it should be counted. The 1x1x2 is consider a twisty puzzle with 4 states. Just because its trivial doesn't mean it shouldn't be counted as a twisty puzzle. However I do feel the puzzle generated by the removal of just a single edge should be counted just ONCE. Not 6*88*10^21 times. The only difference between each of these puzzles is just the location of the stickers so I don't consider each of them a NEW way to bandage the Rubik's Cube. They are the same puzzle with just a different arangement of the stickers.
themathkid wrote:
Even restricting ourselves to connected subgraphs would be insane.
Yes, but maybe the question is insane that I'm asking in the first place. None the less, its the one I'm asking.
themathkid wrote:
I think the more meaningful idea is to talk about proper bandaging and it's extension to virtual / disjoint bandaging. Then you can look at the number of ways of bandaging 2 pieces, 3 pieces, 4 pieces, etc. It reminds me of the partition function from discrete mathematics.
Actually I think Andreas has already done that. If one just looks at glue (and maybe bridge) bandaging I think I've seen that number before. Andreas... I'm looking at you. If anyone I knows has that number or knows where to find it... its you.

Carl

_________________
-
Image

Image


Top
 Profile  
 
 Post subject: Re: Puzzle Theory: How many ways can one bandage a Rubik's C
PostPosted: Wed Nov 07, 2012 12:53 pm 
Offline
User avatar

Joined: Mon Aug 02, 2004 7:03 am
Location: Koblenz, Germany
About the HalfTurnsCube:
I understand now what you want to say.
It is very abstract but it works for your original argument.
For counting permutations it creates wrong results but that was not your original topic. Okay.

About the variant with ropes:
At least some of the cubes "bandaged" with ropes can still be simulated because in most cases the ropes do "nothing more" than ensure the connected pieces have a defined distance from each other.
wwwmwww wrote:
themathkid wrote:
I think the more meaningful idea is to talk about proper bandaging and it's extension to virtual / disjoint bandaging. Then you can look at the number of ways of bandaging 2 pieces, 3 pieces, 4 pieces, etc. It reminds me of the partition function from discrete mathematics.
Actually I think Andreas has already done that. If one just looks at glue (and maybe bridge) bandaging I think I've seen that number before. Andreas... I'm looking at you. If anyone I knows has that number or knows where to find it... its you.

I feel ignored. :(
Both of you please take another look here:
viewtopic.php?f=1&t=24406

The program includes
the complete lists for the "traditionally" bandaged 3x3x3. These variants are shown after startup.
the complete lists for the "bandaged with bridges" 3x3x3. Choose "3x3x3 with bridges" in the menu Puzzles.
Both lists are ordered by the number of bonds (or bridges)

Using the program correctly tells you that there are
1 traditionally bandaged 3x3x3 with 0 bonds
3 traditionally bandaged 3x3x3 with 1 bond
10 traditionally bandaged 3x3x3 with 2 bonds
22 traditionally bandaged 3x3x3 with 3 bonds
48 traditionally bandaged 3x3x3 with 4 bonds
...
1 traditionally bandaged 3x3x3 with 0 bonds excluding face-core-bonds
2 traditionally bandaged 3x3x3 with 1 bond excluding face-core-bonds
6 traditionally bandaged 3x3x3 with 2 bonds excluding face-core-bonds
11 traditionally bandaged 3x3x3 with 3 bonds excluding face-core-bonds
23 traditionally bandaged 3x3x3 with 4 bonds excluding face-core-bonds
...


Top
 Profile  
 
 Post subject: Re: Puzzle Theory: How many ways can one bandage a Rubik's C
PostPosted: Wed Nov 07, 2012 1:45 pm 
Offline
User avatar

Joined: Thu Dec 02, 2004 12:09 pm
Location: Missouri
Andreas Nortmann wrote:
I feel ignored. :(
Both of you please take another look here:
http://twistypuzzles.com/forum/viewtopi ... =1&t=24406
Not ignored... just missed. With my move I haven't been on as much and when I was I rarely got past the new puzzle section. Sorry. I knew you worked on this question specifically so I'll have to check out your program. Thanks for the link.
Andreas Nortmann wrote:
All the 5844 bandaged 3x3x3s presented here are meaningful solvable bandaged 3x3x3.
All the other possible 18 quintillion variants are identical (in this case a very complicated definition) to one of these 5844 variants.
Oh... I for one would love to see your definition of "identical". I assume its something along the lines of these other 18 quintillion are just scrambled and re-stickered variants of these 5844 variants/puzzles. Correct?
Andreas Nortmann wrote:
The most important thing is this:
I suceeded in generalizing the algorithm for "dead ends" for all puzzles and therefore the number of essentially different 3x3x3 is now 5844 of which 5705 are non-trivial of which 3563 can be implemented with the 3X3X3 DIY Bandaged Cubes.
Oh and what is your definition of trivial? I have a hard time seeing 139 DIFFERENT trivial glue/bridge bandaged 3x3x3's. I assume the variants where nothing turns is one. The variant where just a single face turns is another (not counted 6 times). And the variant where just two opposite faces turn is another. I'm up to 3. I can see a few others where adjacent faces can turn but only when the other is in the solved state. But I don't think I can get to 139 variants.

Carl

_________________
-
Image

Image


Top
 Profile  
 
 Post subject: Re: Puzzle Theory: How many ways can one bandage a Rubik's C
PostPosted: Thu Nov 08, 2012 12:41 am 
Offline
User avatar

Joined: Mon Aug 02, 2004 7:03 am
Location: Koblenz, Germany
At first: There are 18 quadrillion variants. I corrected the mistake in the original text as well.
wwwmwww wrote:
Andreas Nortmann wrote:
All the 5844 bandaged 3x3x3s presented here are meaningful solvable bandaged 3x3x3.
All the other possible 18 quintillion variants are identical (in this case a very complicated definition) to one of these 5844 variants.
Oh... I for one would love to see your definition of "identical". I assume its something along the lines of these other 18 quintillion are just scrambled and re-stickered variants of these 5844 variants/puzzles. Correct?
Regarding your question:
Download the program, open the help-file and read the topic "completion".
There you find descriptions and examples for "additional bonds", "implicit bonds" and the newly generalized "dead ends".
None of the remaining bandagings on the list contain any of these three properties. All the variants deleted because of these tests are considered "identical" to one of the remaining variants on the list.
In addition "scrambling and restickering" is used for filtering and "making up symmetries and restickering" as well.
Please note: The filtering process itself is way more complicated and has some intermediate steps and other properties which are necessary to deal with such a big number as 18 quadrillions in a reasonable timeframe.

As a general approach to all puzzles there are another two conditions used for filtering:
1. The bandaging must not be implementable with a "smaller" puzzle => Bandaging a 4x4x4 into the equivalent of a 3x3x3 is not considered as a meaningful of the 4x4x4 and therefore deleted.
2. The bandaging does not split up the puzzle in two or more completely seperate puzzle. This can happen in some bandagings of the megaminx.
For the 3x3x3 these conditions are almost irrelevant since they delete only the 1x1x3.
wwwmwww wrote:
Andreas Nortmann wrote:
The most important thing is this:
I suceeded in generalizing the algorithm for "dead ends" for all puzzles and therefore the number of essentially different 3x3x3 is now 5844 of which 5705 are non-trivial of which 3563 can be implemented with the 3X3X3 DIY Bandaged Cubes.
Oh and what is your definition of trivial? I have a hard time seeing 139 DIFFERENT trivial glue/bridge bandaged 3x3x3's. I assume the variants where nothing turns is one. The variant where just a single face turns is another (not counted 6 times). And the variant where just two opposite faces turn is another. I'm up to 3. I can see a few others where adjacent faces can turn but only when the other is in the solved state. But I don't think I can get to 139 variants.
The state-of-the-art-definition of triviality says:
The variants is detected by at least one of the two tests included to the 3x3x3.
Please look into the help-file. Choose the topic "Puzzle". Scroll down to the section of the 3x3x3.
I am speaking about the tests "Filter permutation-free variants" and "Filter for trivial paths".
So far I was not able to generalize these tests to all puzzles covered in the program. Therefore these tests are only available for the 3x3x3 and the 139 variants which fall to these test are still included.

The same general approach is used for the "3x3x3 with bridges" although I have to make two remarks:
-The bandagings implementable without bridges are still included but can be filtered. See the "Edit"-Menu.
-There are not functions implemented which can filter the trivial variants.


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: Pouring Bees 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