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

TwistyPuzzles.com Forum

It is currently Mon Apr 21, 2014 10:36 am

All times are UTC - 5 hours



Post new topic Reply to topic  [ 11 posts ] 
Author Message
 Post subject: Number of (different) bandaged 3x3x3s
PostPosted: Fri Oct 29, 2004 3:03 am 
Offline
User avatar

Joined: Mon Aug 02, 2004 7:03 am
Location: Koblenz, Germany
After I came up with my collection of bandaged cubes in another thread the question came up how many bandaged cubes are possible.

The short answer:
There are 7336 different bandaged cubes.

The long answer:
There are 24 possibilities to glue a corner and a edge cubie together. There are 24 possibilities to glue a edge and a center cubie together. There are 6 possibilities to glue a center and the spindle within the cube together.
That gives us 54 gluable positions and leads to the theoretical number of 2^54=18014398509481984 = 18*10^15 bandaged cubes.
It is obvious that most of this variants are duplicates to others.
Example1: There is no (real) difference between a fused cube where the 2x2x2-Block is placed in the BOY-corner or the RGW-corner.
Example2: The Bandaged Cube from Mefferts has 440 "different" configurations (thanks to Jaap for that analysis) which all belong to the same bandaged cube.

In phase1 have written a program which goes through all possibilities and applies several filtering rules (two were already pointed out). In the end, only 7336 variants survived the massacre. :twisted:

The result of phase1 are looking awful in most cases. Therefore phase2 tries to choose nicer looking variants of each result. The overall number is not altered. Besides that the cubes are sorted: Variants with less glued positions or with greater blocks are preferred... Phase3 gives the user the possibility to view and edit the Variants manually. Some (uncomfortable) methods of searching are included too.

I didn't came up with this until now because I wanted to make a website for the project but puzzling seemed more fun every time. Maybe I should write something for the Articles section?

To satisfy _pink's wish, I will attach phase3, though the GUI is still labeled in my native german.
Try Ctrl+B and then type $33EC01800846 for a test. The program will show you the Mefferts Bandaged Cube.

I will stop here to keep the post short.
Feel free to ask any questions...

Andreas


Last edited by Andreas Nortmann on Fri Jul 15, 2011 11:06 am, edited 2 times in total.

Top
 Profile  
 
 Post subject:
PostPosted: Fri Oct 29, 2004 4:50 pm 
Offline
User avatar

Joined: Sat Jan 11, 2003 9:08 pm
Location: Athens, Georgia USA
Andreas,

Thanks for the app. I haven't played with it yet but I will make some time for it this weekend. I'm sorry if I spoiled your plans for a web site on the subject. Please continue with the site! I'm sure it will be as enjoyable as your work on bandaging has been so far.

Thanks again!
_pink


Top
 Profile  
 
 Post subject:
PostPosted: Fri Oct 29, 2004 11:10 pm 
Offline

Joined: Sat Mar 22, 2003 9:11 am
Location: Marin, CA
That's a lot of variants! Do you think the number can be reduced further to remove 'uninteresting' variants, or are there really over 7000 notably different forms of bandage cube?

Have you thought about bandaged skewbs? How about bandaged rubik's ufo? Or a bandaged hockey puck? I wrote a program to analyze the ufo with three pieces glued together and got some very interesting results (I can't seem to find my post about it in the archives now though).

Gluing face centers in place so they can't rotate is an interesting idea. I think that since gluing two adjacent face centers together is equivalent to gluing their shared edge to both of them, there are really only two variants on that - one where a single face is glued in place, and one where two opposite faces are glued in place, and in both cases the glued centers can't be glued to their adjoining edges. Is that correct?

Bandaged sliding block is of course a whole subgenre unto itself.


Top
 Profile  
 
 Post subject:
PostPosted: Sat Oct 30, 2004 3:18 am 
Offline
User avatar

Joined: Mon Aug 02, 2004 7:03 am
Location: Koblenz, Germany
Bram wrote:
That's a lot of variants!

Do you think so? Maybe this number is high when you have planned to build them all (like I did before starting the calculation :x) but before I came to this number there were other versions without brute force filterung and they produced over 3 million results...

Bram wrote:
Do you think the number can be reduced further to remove 'uninteresting' variants, or are there really over 7000 notably different forms of bandage cube?

The described filtering was based on "equality of syntax": Every variant missing in the list has an equivalent still in this list. The only exception is the fully bandaged cube where no face can be twisted.
Besides that: The number can easily be reduced. The GUI was built for this purpose, so you can get rid of all variants you don't like. Try the backspace key when navigating...
A filtering based on being "semantically uninteresting" is no problem from the technical aspect. But who am I to judge what means uninteresting? The Special 2x2x2 (in the GUI with signature $1E8400F43FF7A1) for example could have been filtered because its to simple but it is here in the database...

Bram wrote:
Gluing face centers in place so they can't rotate is an interesting idea. I think that since gluing two adjacent face centers together is equivalent to gluing their shared edge to both of them, there are really only two variants on that - one where a single face is glued in place, and one where two opposite faces are glued in place, and in both cases the glued centers can't be glued to their adjoining edges. Is that correct?

Yes. Any other form of glued centers can be realised by gluing specific centers to their neighboring edges.
BTW: The first and most important filtering criterion works with a generalized form of that principle.

Bram wrote:
Have you thought about bandaged skewbs? How about bandaged rubik's ufo? Or a bandaged hockey puck? I wrote a program to analyze the ufo with three pieces glued together and got some very interesting results (I can't seem to find my post about it in the archives now though).

I have thought about bandaged Skewbs and bandaged Pyraminxs / Tetraminxs. See the attachements.
The UFO seems interesting. I placed it on the list with the Rainbow Cube and the Megaminx...

In this moment, my notebook is crunching its way through the possibilities of the Master Cube. It is now working for more than 3 weeks and there is no light at the end of the tunnel...

Andreas

Edit: Deleted the old iles. There are newer version on the forum.


Last edited by Andreas Nortmann on Fri Jul 15, 2011 11:06 am, edited 1 time in total.

Top
 Profile  
 
 Post subject:
PostPosted: Sat Oct 30, 2004 11:47 am 
Offline
User avatar

Joined: Sat Jan 11, 2003 9:08 pm
Location: Athens, Georgia USA
Andreas

Excellent work my friend! Can you give me any insight and direction on using it... as I don't speak German it's kinda funny to see what happens when I select different options... :wink:

Keep up the most excellent work!
_pink


Top
 Profile  
 
 Post subject:
PostPosted: Sat Oct 30, 2004 10:49 pm 
Offline

Joined: Sat Mar 22, 2003 9:11 am
Location: Marin, CA
Wow, the skewb sure has a lot less bandaged versions than the cube. Although that does make sense - in deep cut puzzles everything can be moved around, so a kind of bandaging in one place can probably be moved to any other place, rendering a lot more things equivalent.

What does the yellow highlighting signify?

The UFO has an even smaller number of variants. If a single group of three is bandaged then bandaging another group of three results in a trivial puzzle, so really the only variants are no bandaging, a single group of 3 bandaged with between 1 and 3 groups of 2 bandaged, and no group of 3 with between 1 and 4 groups of 2 bandaged, and some of those more bandaged variants might also be trivial.

As I see it, if two puzzles only vary in that one can do a few dead end moves that the other can't, then the extra moves add nothing to it as a puzzle. For example, if you have one face center glued to two opposite edges and both of those edges glued to the face centers they touch on the other side, then have the 2x2x3 block of pieces on one of the two sides of that region all glued together to form another piece, then every time you rotate that 2x2x3 block you'll immediately have to rotate it right back in place again because all other moves will be blocked, so you might as well glue those two groups together.

Also, I think than any puzzle which either is all dead ends or only has a single non-dead-end sequence which is a single loop (like the morph heead) is trivial and therefore uninteresting, although others might not share that opinion.

I find the bandaging applet hard to use, by the way, because it's far from obvious which faces from the back are opposite which faces from the front.

It would be nice if the groupings were sorted based on how the face centers are glued first, followed by how everything else is glued. That would (I think) put more related things closer to each other.


Top
 Profile  
 
 Post subject:
PostPosted: Sun Oct 31, 2004 2:35 am 
Offline
User avatar

Joined: Mon Aug 02, 2004 7:03 am
Location: Koblenz, Germany
Bram wrote:
Wow, the skewb sure has a lot less bandaged versions than the cube. Although that does make sense - in deep cut puzzles everything can be moved around, so a kind of bandaging in one place can probably be moved to any other place, rendering a lot more things equivalent.

Another explanation could be: Instead of 54 gluable positions the Skewb has only 24 and all the positions are of the same kind instead of the three kinds in the cube.

Bram wrote:
As I see it, if two puzzles only vary in that one can do a few dead end moves that the other can't, then the extra moves add nothing to it as a puzzle.
...

The variant you described is in the list and has the signature $B5A005AD. And you are right. There is almost no difference to variant $B5ADB5AD.
Maybe I should implement an appropriate filter function in the GUI? I still like the Master Boob. :wink:

Bram wrote:
Also, I think than any puzzle which either is all dead ends or only has a single non-dead-end sequence which is a single loop (like the morph heead) is trivial and therefore uninteresting, although others might not share that opinion.

True again. Another filtering function?

Bram wrote:
I find the bandaging applet hard to use, by the way, because it's far from obvious which faces from the back are opposite which faces from the front.


To compete with that matter (and _pink's): Here comes a more detailed description:

As already stated the GUI was made to visualize the results and let the user manipulate and filter them by hand, according to his individual taste.

Yellow highlighting means: The variants have the same blocknumber =
Same number of corners glued to edges
Same number of edges glued to centers
Same number of centers glued to the spindle
Same number of higher-order blocks (Fused blocks, 1x2x2-Blocks, 1x1x3-Block etc... are considered separately)
Included in the blocknumbers is wheather two or more edges glued to centers are placed on opposite or adjacent faces and similar positioning schemes like that.
When two variants have different blocknumbers it is impossible to transform one into the other.

Two variants are shown. The left one works like a cache. See the menu "Visualisierung" for details. The other visualizes the actually choosen signature. An X on a center cubie means in this context that the cubie is glued to spindle.
Blue is opposite to white.
Yellow is opposite to green.
Red is opposite to orange.

The statusbar at the bottom contains four fields:
Einsortiert: number of variants in the left list
Aussortiert: number of variants in the right list
Ebene: number of glued positions (out of 54 possible) in the actual variant?
Geändert: Only visible when changes where made

Menu "Programm"
Speichern: Save the changes you applied to your copy of the list
Beenden: Close the programm

Menu "Bearbeiten"
The Equivalent to the Edit-Menu of most GUI-Applications. The Search-Options do their work for both lists but manipulations will be performed only to entries in the left list.
-Suche Behinderung: Search for a bandaged variant by signature. The exact signature is required! The following option is more tolerant...
-Suche Blockgleiche: Search for a bandaged variant which has the same "blocknumbers" as the one specified. See the explanations above.
-Behinderung Verdrehen: Gives you the possibility to replace the actual variant with one you create from the original by turning the faces (if possible). The buttons twist the following faces (from top to bottom): red, blue, yellow, orange, green, white.
-Bilde Potenzialvarianten: All the variants which could have been made by the before mentioned menu entry are calculated by the program and presented in a list. One can be choosen with or without chossing a symmetrie before; see next point.
-Bilde Symmetrie: Every variant has at most 48 symmetries. With this point you can choose one to replace the variant.

Menu "Visualisierung"
This menu control the behaviour of the left visualization. It was made for comparisons between two variants.
-Vergleich speichern: put the actual variant (right visualization) into the left visualization.
-Vergleich löschen: delete the variant in the left visualization. Some kind of obsolete...
-Verkleben: A feature to test the criterias used for the filtering process. When you entered an "incomplete signature" (see last menu entry) this function will add "derived gluings" between the cubies. Test it with the following examples: $500 $40480 $80008100; This derived gluings are based on shape comparisons which means they are fast to perform but do not cover all possible cases, like $891.
-Funktionale Entsprechung: Like the last entry this is a feature to test a criterion used for the filtering process. The difference is that this method is complete, covers all derivable entries and is way slower. Test it with signatures like this: $891 $2120000100003 $318C018C600C03
-Vergleich eingeben: manual input of a signature for display in the left visualization

manual input:
each variant is represented by a 54-digit binary number. Each digit represents one possible point to glue two cubies together. Enter Hex-numbers $1, $2, $4, $8, $10 etc to see which gluing point ist affected. There is no better system yet, since I use it extensivly.

Last point: A small vocabulary to understand the labeled buttons:
Suche = Search
Abbrechen = Cancel
Schliessen = Close
Behinderung Übernehmen = replace variant

I will answer more questions if necessary and will search in my programming tools for a way to supply the GUI in more than one language...

Andreas


Top
 Profile  
 
 Post subject:
PostPosted: Sun Oct 31, 2004 2:49 pm 
Offline

Joined: Sat Mar 22, 2003 9:11 am
Location: Marin, CA
Ah, I understand how the yellow highlighting works now.

You appear to have done a very good job of finding implicit gluing. I checked for a couple different possible errors, and you got them all right, so it appears that you used some completely automated system for generating these which does everything right, rather than special casing the obvious cases of implicit gluing.

There are some cases of yellow-equivalent positions in which it isn't obvious to me that you can't get from one to the other, but determining that for sure is beyond my ability to visualize, so I assume the the program is right. Perhaps some of those non-obvious cases have the 'only dead ends differ' equivalence.

Optional filtering is a good approach.

Scanning over the different bandaged cubes, I think that even after extremely judicious filtering out of 'uninteresting' variants there will still be thousands left.


Top
 Profile  
 
 Post subject:
PostPosted: Mon Nov 01, 2004 2:01 am 
Offline
User avatar

Joined: Mon Aug 02, 2004 7:03 am
Location: Koblenz, Germany
Bram wrote:
I checked for a couple different possible errors, and you got them all right, so it appears that you used some completely automated system for generating these which does everything right, rather than special casing the obvious cases of implicit gluing.

The system does the following: It takes the original bandaging and one with an additional gluing. Both bandagings are twisted parallel in the same fashion to generate all possible configurations. When a discrepancy is found (one configuration twistable; the other not) the "new" gluing is not applied to the result. When the algorithm can't generate any new configurations and no discrepancy is found the gluing is added to the result. This system is applied for all 54 possible gluings.
You can imagine that this system gets every derived gluing but is far slower than the shape based method.

Bram wrote:
Optional filtering is a good approach.
Scanning over the different bandaged cubes, I think that even after extremely judicious filtering out of 'uninteresting' variants there will still be thousands left.

I think so, too. But I will implement the filtering because I am still interested.

Andreas


Top
 Profile  
 
 Post subject:
PostPosted: Mon Nov 01, 2004 11:46 am 
Offline
User avatar

Joined: Sat Jan 11, 2003 9:08 pm
Location: Athens, Georgia USA
Andreas,

Do you plan on writing apps for other puzzles? Have you considered putting all the puzzles into one app?

_pink


Top
 Profile  
 
 Post subject:
PostPosted: Mon Nov 01, 2004 12:51 pm 
Offline
User avatar

Joined: Mon Aug 02, 2004 7:03 am
Location: Koblenz, Germany
I have updated the app. Now everyone who has not DEU set as active Locale should see english entries. You can download it from the original post.

_pink wrote:
Do you plan on writing apps for other puzzles? Have you considered putting all the puzzles into one app?


The actual plan is to speed up the initial filtering for the 4x4x4. After that... I don't have any specific plans.
I made a list with alle puzzles in the database and all cuboids LxMxN (less or equal 5) where bandagings make (even a bit) sense. The Domino for example is not on the list, because you can think of it as a bandaged 4x4x4 and so all its bandagings will be included there.

But all that are dreams of the future. I cannot start with the 5x5x5 when I need months for the 4x4x4. Some kind of exponential growth in complexity...
Maybe I should quit seti@home and start with filterBandagings@home :roll:

The single GUI is a good idea. I will see what can be done.

Andreas


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

All times are UTC - 5 hours


Who is online

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