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

TwistyPuzzles.com Forum
 It is currently Sat Apr 19, 2014 5:13 am

 All times are UTC - 5 hours

 Page 2 of 2 [ 82 posts ] Go to page Previous  1, 2
 Print view Previous topic | Next topic
Author Message
 Post subject: Re: How to visualize pieces of a complex puzzlePosted: Sun Dec 09, 2012 11:59 am

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
Hi schuma, great programming work. I looked through your code and that must have taken quite a while. I was thinking of doing something similar for generating the reorientation table for my commutator-finding program for each of the platonic solids. I'm probably going to end up re-using some of your ideas when I resume work on my program.

I've been trying to find the GAP documentation that describes the algorithm and expected runtime for the Size() function. GAP isn't multi-threaded (or at least Size() can't make use of more than one CPU) which means all of the beefy machines I have access to aren't much better than my laptop. I have the complex edge-turning-cube and complex face-turning-dodecahedron running but I have no way to estimate how long they'll take.

One thing I'm very interested in is the relationship between pieces. For example, the edges can be in 12! positions and the corners in 8! positions but if you fix the edges (or corners) in place (Stabilizer?) then they are reduced by a factor of 2 because of the parity linkage between the two pieces.

Is there an easy way to enumerate all restrictions / relationships between pieces? If GAP can't spit that out, can you write code to check the size of all 2^10 subsets of pieces to see which ones are smaller than expected? That would tell us what's linked. We'd need something smarter for all of the other complex puzzles due to the number of piece types.

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

Top

 Post subject: Re: How to visualize pieces of a complex puzzlePosted: Sun Dec 09, 2012 3:23 pm

Joined: Thu Jul 23, 2009 5:06 pm
Location: Berkeley, CA, USA
Hi Brandon,

I added some comments and did some refactoring so that the code is more readable. I think the words "reorientation table" are better than "muliplication table" because it's not multiplication. So I also changed this word. The code is basically not changed functionally. So the code you are running is still generating consistent output.

Your suggestion of running the code 2^10 times to find out the dependency between piece sounds reasonable. But it's not that trivial because in the current version, partitioning all the pieces into piece types is not that automated. For complex 3x3x3, I need to go to the output of GAP to copy the 10 types back to ruby code. For vertex turning cube, the situation is more complicated. For example, all eight corners should be counted as one type, but the current code divide them into two types because they belong to two orbits according to vertex turning group (which is subgroup of the symmetry of cube). I'll think about it.

Top

 Post subject: Re: How to visualize pieces of a complex puzzlePosted: Mon Dec 10, 2012 2:03 am

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
schuma wrote:
Your suggestion of running the code 2^10 times to find out the dependency between piece sounds reasonable. But it's not that trivial because in the current version, partitioning all the pieces into piece types is not that automated. For complex 3x3x3, I need to go to the output of GAP to copy the 10 types back to ruby code. For vertex turning cube, the situation is more complicated. For example, all eight corners should be counted as one type, but the current code divide them into two types because they belong to two orbits according to vertex turning group (which is subgroup of the symmetry of cube). I'll think about it.
Your approach to piece type counting took me by surprise. My code implements the re-orientation table and piece finding itself so it's aware of every piece type. The advantage is that you offload more work onto GAP instead of implementing it yourself.

I've tried manually calculating the size of the Complex 3x3x3 group but I always get 2x the number provide by GAP. There is an additional restriction reducing the state by a factor of 2 that I don't know about. I'd really like to know what it is...

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

Top

 Post subject: Re: How to visualize pieces of a complex puzzlePosted: Mon Dec 10, 2012 2:37 am

Joined: Thu Jul 23, 2009 5:06 pm
Location: Berkeley, CA, USA
bmenrigh wrote:
I've tried manually calculating the size of the Complex 3x3x3 group but I always get 2x the number provide by GAP. There is an additional restriction reducing the state by a factor of 2 that I don't know about. I'd really like to know what it is...

Interesting. Have you written your calculation down anywhere? I'd like to see it actually.

Edit: I also did the calculation. Me, too, got twice the number. But the good thing about using GAP is that I can check step by step on which piece type my calculation went wrong. Here's my corrected calculation:

Face centers: 6 pieces, each has four directions: 4^6
Edges: even permutations: 12!/2. Orientations: 2^12/2
Corners: even permutations: 8!/2. Orientations: 3^8/3
Inverted core, relative to core: 24/2 orientations
Inverted face: only five pieces can rotate freely. (Unlike the super 3x3x3, one piece cannot be turned by 180 degrees. This is where I went wrong. I still don't quite understand why this is forbidden. See the discussion below) 4^6/4
[UDF]: 12 pieces, even perm: 12!/2. Orientations: 2^12/2
Inverted edges: even perm: 12!/2. Orientations: 2^12/2

Total Perm:

4^6 * Factorial(12)/2 * 2^12/2 * Factorial(8)/2 * 3^8/3 * 24/2 * 4^6/4 * Factorial(12)/2 * 2^12/2 * Factorial(12)/2 * 2^12/2
=
261873301579133051001433349178932006108528640000000

I did some extra calculation:
(1) If there's only the core and inverted core, there are 24 permutations. That's the symmetry of cube.
(2) If there are the faces (determining the core) and the inverted core, there are 4^6 * 24/2 perms. This factor of 2 is understandable. After faces are solved, there must be a even number of quarter turns. This is the common parity of permutation on the Rubik's cube.
(3) If there's only the core and the inverted faces (which determines the inverted core), there are 4^6 * 24/2 perms, as same as case (2). The reason should be similar to the one in (2). But is this 2 the same 2 as there? I'm not sure.
(4) If there are the face and the inverted face, the number is 4^6 * 4^6 * 12 /4. Is this 4 the product of the factor of 2 from case (2) and the 2 from case (3)? I'm not sure. But obviously it depends on and only on the presence of faces and inverted faces. We need a proof and a better understanding of this parity. Does anyone have an idea here?

Top

 Post subject: Re: How to visualize pieces of a complex puzzlePosted: Mon Dec 10, 2012 11:07 am

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
We performed the calculation the same way and went wrong in the same place.

I did some more experimenting and it seems like whenever you put a half-turn in an inverted center you also always put a half turn in a center. I can't figure out why this is. I've tried lots of ways to twist an inverted center by 180 and they all affect the face centers too. I'm struggling to find the insight to explain this.

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

Top

 Post subject: Re: How to visualize pieces of a complex puzzlePosted: Mon Dec 10, 2012 11:19 am

Joined: Fri Jan 29, 2010 2:34 pm
Location: Scotland, UK
bmenrigh wrote:
We performed the calculation the same way and went wrong in the same place.

I did some more experimenting and it seems like whenever you put a half-turn in an inverted center you also always put a half turn in a center. I can't figure out why this is. I've tried lots of ways to twist an inverted center by 180 and they all affect the face centers too. I'm struggling to find the insight to explain this.

Label the orientations of the [U] pieces relative to [] and the [UDRLF] pieces relative to [UDRLFB], and they take the values 0 through 3 with 0=solved, 1=90 degrees clockwise from solved etc. (I hope what I mean by this makes sense, an example will follow which might help).

A move will change the orientation of one of each type of piece, by the same amount (e.g. a U twist changes the orientation of U by +1 and the piece in the URLFB position by +1), so the sum of these values over each set of pieces will always be the same value modulo 4.

P.S. I didn't know this before, I've been making the same mistake when trying to do the calculation by hand! Luckily I managed to figure it out once I knew what to look for.

Top

 Post subject: Re: How to visualize pieces of a complex puzzlePosted: Mon Dec 10, 2012 2:53 pm

Joined: Thu Jul 23, 2009 5:06 pm
Location: Berkeley, CA, USA
bobthegiraffemonkey wrote:
A move will change the orientation of one of each type of piece, by the same amount (e.g. a U twist changes the orientation of U by +1 and the piece in the URLFB position by +1), so the sum of these values over each set of pieces will always be the same value modulo 4.

This argument is interesting. I've never seen it before. The most interesting thing is that, the piece in [U] is always the same piece ---- it never moves. But the piece in the ULRFB position is changing because this type of pieces move. Never the less, the sum of values across all the [ULRFB] type must be consistent with the value of the sum. Congrats on this finding!

Top

 Post subject: Re: How to visualize pieces of a complex puzzlePosted: Fri Dec 21, 2012 4:17 pm

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
schuma wrote:
For larger puzzles like edge-turning cube and face-turning dodecahedron, GAP cannot quickly do it (I gave up on edge-turning cube after waiting for an hour). Does anyone know of some access of powerful machine on which I may have permission to install GAP?
The edge-turning-cube doesn't just take time. After about 260 CPU-hours on my laptop, GAP finally started using more than 6GB of RAM causing my machine to page to disk like crazy.

I've looked through a lot of the GAP code to try to understand the algorithm it uses. To find the order of the group with Size() it first has to create a stabilizer chain (which I think basically just means in has to find the relationship between the pieces). It uses a random algorithm (non-deterministic) to do this (randomized Schreier-Sims). See stbcrand.gi for implementation details.

The reason I mention this is that I was periodically looking at the stack trace for the computation and at around the 255 hour mark GAP was only using about 2GB of memory and was still in the SCRMakeStabStrong() recursion. When it got out of this recursion I think it had found a stabilizer which I think is the bulk of the computation. Unfortunately memory usage ballooned.

I have restarted the Complex Edge-Turning-Cube and Complex Face-Turning-Dodecahedron on a machine with a lot more memory and slightly faster CPUs. It will be about 12 days before I catch up to where I was on my laptop.

http://www.gap-system.org/Manuals/doc/ref/chap43.html

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

Top

 Post subject: Re: How to visualize pieces of a complex puzzlePosted: Tue Jan 08, 2013 3:23 am

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
EDIT: Due to human error I left off a trailing zero, making the number 10 times too small. I have fixed it. This explains the "extra factor of 6" which is actually an "extra factor of 60".

After a bit more than 300 CPU-hours and a peak memory usage of 22 GB, GAP reports that the Complex Face-Turning-Dodecahedron has

901748746885298046197743925828017453625990405162084380148726687722446910271
793881902830657781052943961337432784436438047589042692555841011247593700242
725177737189269642780961673454383600303453568990125394834437758480770269376
970502502330414325876021910186031116751659248691402461514448651926618828705
182960050355609021270743491215368430496612356329886572916670542021339529381
205433327032111147156333018423049718921361295588992565008183391929353009701
581429247177690403285502938854159140929028987203847669903293873047919943185
140324735040928695576919585472644122231226761120801706885447521611080484169
371579636732654259889947295236852887839108701294997567199206933314296563512
913318399301429081565421736821742618503740224904462794217778703250309377740
195772695590165554753411538698150957653062268051820557520222380610084487827
055693449748075510017496521947129060146381232683128295364475595601805256184
177288013140516232579594312922010011173217199479161805849894957311252513430
250135518734837408934501202572618957596009054172248906476202927379674292880
383045936908305501404734783763231947201553704670739948779817865038912959425
733870506042754227160365433285210047685434911007378613809977152105818681472
110701226786096255144883630223047427395070293857501047723078924296439140196
871478033005505277273771555967628304518568281002951081079790778015011591091
201590062725973246528830361377833025222312035463265114401448446129431762234
316385555325966911988706534008715104404126293081667547384274722544115776836
353905301629163023816078514067875742169633497220078070493998865391143272925
341337492693108908983630211648861403252689298309427332687433573750885832949
174135677937427259444279404670040568537124600730885113848293522337752857509
633798153586471604794295089478668261750013149805036873840216769703222402881
481865810482791978514335861459073957626302591033335894895760290013190901025
150216730087711861835771330419367825775327983815116455445742754554378419452
513061522038896020760868836518863978871368058622736836389446034655661223974
483661906104261342097068695663882699793913325208405764800195652927892655351
955902475141324301981237162410648304880983932835846735286451668674229911953
980142937411112767112271989576647435868683272981729470882900046520732845231
502232833043813783697596626776669997363773873297949256350301379480109695969
744319302159046162854686538239573946568447241486834372664715908413972577721
549093112225040340615733789672160195507428978533038091849422175528288444683
730057466097593687755315155289284437831304276731763868565801180838047923181
757005826017388657024398246778115830462720743277745745061896766507931146753
188617027482792325988869366487809325379033652341978264873227877072887471357
726678511318171420008873418684052569615462710379469740926468492395079561364
784676475284438245459673138040622855856532826476622433269801116628985602909
052974920440805556614745108662281461423189201497204005994882994415030029292
188507082482772254331883489285849584962358113942512371196694105550002228871
449465245892898530963792022817280357657199827226867888669004560935865270018
586137032960813297716751955264547079940113255428598470120727403005273147586
952348499451378528250404438193058405802707576999282285803301334140257485856
211920970443097589693380435111196026928219120478143825869363570635710160694
736569094392063927810235175617541904262648590563301150810090405659712805630
303427538562511509121469277419895542653294804614314657794206509101844450827
471207289036229711505901745962039532126124858648481283529096791338261709954
899615358051330107780099176063945893092234487464470033660738906068121709912
931461318717888153596987640642154618902396604168403843917810905063842711650
220196742693051205055296746368948028038986051797944864359977270988092744929
014393569752968300799224181690670014757121415868152579766412812028152202820
527578314313700290020492194289386795170228876668252406505797059644520422847
489522763096703889788078801273904432527430019605013268555342145040335387629
525018767391597236979499144451983719028315969698118618579515099977888560222
670098215037014235911249090600960676464306413522686308293295975168673670008
711502781058052203220645113583271141525492856196992530255965055251964193635
354312268989371088355099805018698547200000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000

Positions (ignoring orientation).

This factors to:

2^3606 * 3^1866 * 5^932 * 7^583 * 11^317 * 13^264 * 17^186 * 19^186 * 23^128 * 29^128 * 31^52 * 37^52 * 41^52 * 43^52 * 47^52 * 53^52 * 59^52

Which suggests (I think) there are 52 independent sets of 60 pieces and 24 independent sets of 30 pieces and 6 independent sets of 20 pieces and 2 independent sets of 15 pieces and 1 independent set of 12 pieces and 2 independent sets of 10 pieces and another factor of 6 somewhere.

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

Last edited by Brandon Enright on Thu Jan 10, 2013 1:35 am, edited 1 time in total.

Top

 Post subject: Re: How to visualize pieces of a complex puzzlePosted: Tue Jan 08, 2013 3:56 pm

Joined: Thu Jul 23, 2009 5:06 pm
Location: Berkeley, CA, USA
bmenrigh wrote:
This factors to:

2^3606 * 3^1866 * 5^932 * 7^583 * 11^317 * 13^264 * 17^186 * 19^186 * 23^128 * 29^128 * 31^52 * 37^52 * 41^52 * 43^52 * 47^52 * 53^52 * 59^52

Which suggests (I think) there are 52 independent sets of 60 pieces and 24 independent sets of 30 pieces and 6 independent sets of 20 pieces and 2 independent sets of 15 pieces and 1 independent set of 12 pieces and 2 independent sets of 10 pieces and another factor of 6 somewhere.

I didn't expect that the computation would be completed. Congrats!

The deduction based on factorization is amazing. Brandon was saying that the huge number is equal to:

(60!/2)^52 * (30!/2)^24 * (20!/2)^6 * (15!/2)^2 * (12!/2) * (10!/2)^2 * 6

Each factorial is divided by two because only even permutations are allowed. This conjecture is probably mostly correct.

Top

 Post subject: Re: How to visualize pieces of a complex puzzlePosted: Tue Jan 08, 2013 5:07 pm

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
I wrote some code to enumerate all of the pieces and types which yields:

Code:
Found 1 pieces of type 0 ( ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ) with twist freedom 60
Found 12 pieces of type 1 (A,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ) with twist freedom 5
Found 30 pieces of type 2 (A, B,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ) with twist freedom 2
Found 20 pieces of type 3 (A, B, C,  ,  ,  ,  ,  ,  ,  ,  ,  ) with twist freedom 3
Found 30 pieces of type 4 ( , B,  , D,  ,  ,  ,  ,  ,  ,  ,  ) with twist freedom 2
Found 60 pieces of type 5 (A, B,  , D,  ,  ,  ,  ,  ,  ,  ,  ) with twist freedom 1
Found 30 pieces of type 6 (A, B, C, D,  ,  ,  ,  ,  ,  ,  ,  ) with twist freedom 2
Found 60 pieces of type 7 ( , B, C,  , E,  ,  ,  ,  ,  ,  ,  ) with twist freedom 1
Found 60 pieces of type 8 (A, B, C,  , E,  ,  ,  ,  ,  ,  ,  ) with twist freedom 1
Found 60 pieces of type 9 ( , B, C, D, E,  ,  ,  ,  ,  ,  ,  ) with twist freedom 1
Found 60 pieces of type 10 (A, B, C, D, E,  ,  ,  ,  ,  ,  ,  ) with twist freedom 1
Found 12 pieces of type 11 ( , B, C, D, E, F,  ,  ,  ,  ,  ,  ) with twist freedom 5
Found 12 pieces of type 12 (A, B, C, D, E, F,  ,  ,  ,  ,  ,  ) with twist freedom 5
Found 6 pieces of type 13 ( ,  ,  ,  , E,  , G,  ,  ,  ,  ,  ) with twist freedom 10
Found 60 pieces of type 14 (A,  ,  ,  , E,  , G,  ,  ,  ,  ,  ) with twist freedom 1
Found 30 pieces of type 15 (A, B,  ,  , E,  , G,  ,  ,  ,  ,  ) with twist freedom 2
Found 30 pieces of type 16 (A,  , C,  , E,  , G,  ,  ,  ,  ,  ) with twist freedom 2
Found 60 pieces of type 17 ( , B, C,  , E,  , G,  ,  ,  ,  ,  ) with twist freedom 1
Found 60 pieces of type 18 (A, B, C,  , E,  , G,  ,  ,  ,  ,  ) with twist freedom 1
Found 30 pieces of type 19 ( , B,  , D, E,  , G,  ,  ,  ,  ,  ) with twist freedom 2
Found 60 pieces of type 20 (A, B,  , D, E,  , G,  ,  ,  ,  ,  ) with twist freedom 1
Found 30 pieces of type 21 (A, B, C, D, E,  , G,  ,  ,  ,  ,  ) with twist freedom 2
Found 20 pieces of type 22 ( ,  ,  , D,  , F, G,  ,  ,  ,  ,  ) with twist freedom 3
Found 60 pieces of type 23 (A,  ,  , D,  , F, G,  ,  ,  ,  ,  ) with twist freedom 1
Found 60 pieces of type 24 (A, B,  , D,  , F, G,  ,  ,  ,  ,  ) with twist freedom 1
Found 20 pieces of type 25 (A, B, C, D,  , F, G,  ,  ,  ,  ,  ) with twist freedom 3
Found 30 pieces of type 26 ( ,  , C,  , E, F, G,  ,  ,  ,  ,  ) with twist freedom 2
Found 60 pieces of type 27 (A,  , C,  , E, F, G,  ,  ,  ,  ,  ) with twist freedom 1
Found 30 pieces of type 28 (A, B, C,  , E, F, G,  ,  ,  ,  ,  ) with twist freedom 2
Found 60 pieces of type 29 ( ,  ,  , D, E, F, G,  ,  ,  ,  ,  ) with twist freedom 1
Found 60 pieces of type 30 (A,  ,  , D, E, F, G,  ,  ,  ,  ,  ) with twist freedom 1
Found 60 pieces of type 31 ( , B,  , D, E, F, G,  ,  ,  ,  ,  ) with twist freedom 1
Found 60 pieces of type 32 (A, B,  , D, E, F, G,  ,  ,  ,  ,  ) with twist freedom 1
Found 60 pieces of type 33 ( ,  , C, D, E, F, G,  ,  ,  ,  ,  ) with twist freedom 1
Found 60 pieces of type 34 (A,  , C, D, E, F, G,  ,  ,  ,  ,  ) with twist freedom 1
Found 60 pieces of type 35 ( , B, C, D, E, F, G,  ,  ,  ,  ,  ) with twist freedom 1
Found 60 pieces of type 36 (A, B, C, D, E, F, G,  ,  ,  ,  ,  ) with twist freedom 1
Found 15 pieces of type 37 ( ,  ,  ,  , E, F, G, H,  ,  ,  ,  ) with twist freedom 4
Found 60 pieces of type 38 (A,  ,  ,  , E, F, G, H,  ,  ,  ,  ) with twist freedom 1
Found 60 pieces of type 39 ( , B,  ,  , E, F, G, H,  ,  ,  ,  ) with twist freedom 1
Found 60 pieces of type 40 (A, B,  ,  , E, F, G, H,  ,  ,  ,  ) with twist freedom 1
Found 30 pieces of type 41 (A,  , C,  , E, F, G, H,  ,  ,  ,  ) with twist freedom 2
Found 60 pieces of type 42 ( , B, C,  , E, F, G, H,  ,  ,  ,  ) with twist freedom 1
Found 60 pieces of type 43 (A, B, C,  , E, F, G, H,  ,  ,  ,  ) with twist freedom 1
Found 30 pieces of type 44 ( , B,  , D, E, F, G, H,  ,  ,  ,  ) with twist freedom 2
Found 60 pieces of type 45 (A, B,  , D, E, F, G, H,  ,  ,  ,  ) with twist freedom 1
Found 30 pieces of type 46 (A, B, C, D, E, F, G, H,  ,  ,  ,  ) with twist freedom 2
Found 30 pieces of type 47 (A,  ,  ,  ,  , F, G,  , I,  ,  ,  ) with twist freedom 2
Found 60 pieces of type 48 (A, B,  ,  ,  , F, G,  , I,  ,  ,  ) with twist freedom 1
Found 60 pieces of type 49 (A,  , C,  ,  , F, G,  , I,  ,  ,  ) with twist freedom 1
Found 60 pieces of type 50 (A, B, C,  ,  , F, G,  , I,  ,  ,  ) with twist freedom 1
Found 60 pieces of type 51 ( , B,  , D,  , F, G,  , I,  ,  ,  ) with twist freedom 1
Found 60 pieces of type 52 (A, B,  , D,  , F, G,  , I,  ,  ,  ) with twist freedom 1
Found 20 pieces of type 53 (A,  , C, D,  , F, G,  , I,  ,  ,  ) with twist freedom 3
Found 60 pieces of type 54 ( , B, C, D,  , F, G,  , I,  ,  ,  ) with twist freedom 1
Found 60 pieces of type 55 (A, B, C, D,  , F, G,  , I,  ,  ,  ) with twist freedom 1
Found 30 pieces of type 56 (A, B,  ,  , E, F, G,  , I,  ,  ,  ) with twist freedom 2
Found 60 pieces of type 57 ( , B, C,  , E, F, G,  , I,  ,  ,  ) with twist freedom 1
Found 60 pieces of type 58 (A, B, C,  , E, F, G,  , I,  ,  ,  ) with twist freedom 1
Found 60 pieces of type 59 ( , B,  , D, E, F, G,  , I,  ,  ,  ) with twist freedom 1
Found 60 pieces of type 60 (A, B,  , D, E, F, G,  , I,  ,  ,  ) with twist freedom 1
Found 60 pieces of type 61 ( , B, C, D, E, F, G,  , I,  ,  ,  ) with twist freedom 1
Found 60 pieces of type 62 (A, B, C, D, E, F, G,  , I,  ,  ,  ) with twist freedom 1
Found 10 pieces of type 63 ( , B,  ,  , E, F, G, H, I,  ,  ,  ) with twist freedom 6
Found 60 pieces of type 64 (A, B,  ,  , E, F, G, H, I,  ,  ,  ) with twist freedom 1
Found 60 pieces of type 65 (A, B, C,  , E, F, G, H, I,  ,  ,  ) with twist freedom 1
Found 20 pieces of type 66 (A, B, C, D, E, F, G, H, I,  ,  ,  ) with twist freedom 3
Found 12 pieces of type 67 (A, B,  , D,  ,  , G, H,  , J,  ,  ) with twist freedom 5
Found 12 pieces of type 68 (A, B, C, D,  ,  , G, H,  , J,  ,  ) with twist freedom 5
Found 30 pieces of type 69 (A, B,  ,  , E,  , G, H,  , J,  ,  ) with twist freedom 2
Found 30 pieces of type 70 ( , B, C,  , E,  , G, H,  , J,  ,  ) with twist freedom 2
Found 60 pieces of type 71 (A, B, C,  , E,  , G, H,  , J,  ,  ) with twist freedom 1
Found 30 pieces of type 72 ( , B,  , D, E,  , G, H,  , J,  ,  ) with twist freedom 2
Found 60 pieces of type 73 (A, B,  , D, E,  , G, H,  , J,  ,  ) with twist freedom 1
Found 60 pieces of type 74 ( , B, C, D, E,  , G, H,  , J,  ,  ) with twist freedom 1
Found 60 pieces of type 75 (A, B, C, D, E,  , G, H,  , J,  ,  ) with twist freedom 1
Found 10 pieces of type 76 ( ,  , C,  , E, F, G, H,  , J,  ,  ) with twist freedom 6
Found 60 pieces of type 77 (A,  , C,  , E, F, G, H,  , J,  ,  ) with twist freedom 1
Found 30 pieces of type 78 (A, B, C,  , E, F, G, H,  , J,  ,  ) with twist freedom 2
Found 60 pieces of type 79 ( , B,  , D, E, F, G, H,  , J,  ,  ) with twist freedom 1
Found 60 pieces of type 80 (A, B,  , D, E, F, G, H,  , J,  ,  ) with twist freedom 1
Found 30 pieces of type 81 (A,  , C, D, E, F, G, H,  , J,  ,  ) with twist freedom 2
Found 60 pieces of type 82 ( , B, C, D, E, F, G, H,  , J,  ,  ) with twist freedom 1
Found 60 pieces of type 83 (A, B, C, D, E, F, G, H,  , J,  ,  ) with twist freedom 1
Found 30 pieces of type 84 (A, B, C,  ,  , F, G, H, I, J,  ,  ) with twist freedom 2
Found 30 pieces of type 85 (A, B,  , D,  , F, G, H, I, J,  ,  ) with twist freedom 2
Found 30 pieces of type 86 ( , B, C, D,  , F, G, H, I, J,  ,  ) with twist freedom 2
Found 60 pieces of type 87 (A, B, C, D,  , F, G, H, I, J,  ,  ) with twist freedom 1
Found 15 pieces of type 88 ( , B, C,  , E, F, G, H, I, J,  ,  ) with twist freedom 4
Found 60 pieces of type 89 (A, B, C,  , E, F, G, H, I, J,  ,  ) with twist freedom 1
Found 30 pieces of type 90 (A, B, C, D, E, F, G, H, I, J,  ,  ) with twist freedom 2
Found 20 pieces of type 91 (A, B, C,  , E,  , G, H, I, J, K,  ) with twist freedom 3
Found 30 pieces of type 92 (A, B, C, D, E,  , G, H, I, J, K,  ) with twist freedom 2
Found 6 pieces of type 93 ( , B, C, D, E, F, G, H, I, J, K,  ) with twist freedom 10
Found 12 pieces of type 94 (A, B, C, D, E, F, G, H, I, J, K,  ) with twist freedom 5
Found 1 pieces of type 95 (A, B, C, D, E, F, G, H, I, J, K, L) with twist freedom 60

If you break that down there are:
• 2 sets of 1 piece (core and inverse core)
• 2 sets of 6 pieces (analogous to center-bars?)
• 2 sets of 10 pieces (analogous to corner-bars?)
• 6 sets of 12 pieces (these are analogous to centers)
• 2 sets of 15 pieces (analogous to edge-bars?)
• 6 sets of 20 pieces (these are analogous to corners)
• 24 sets of 30 pieces (these are analogous to edges)
• 52 sets of 60 pieces (triangles, trapezoids, kites, chiral pieces, other face pieces)

So it seems none of the (52) face pieces, (24) edges, (6) corners, (2) edge-bars, and (2) corner-bars are redundant for permutation. Only one set of centers can be permuted relative to the other pieces. All of the center bars seem to be redundant for permutation and the cores obviously can't be permuted.

This allows us to put an upper bound on the possible number of states as the above number times (2^30)^24 * (3^20)^6 * (4^15)^2 * (5^12)^6 * (6^10)^2 * (10^6)^2 * 60
=
53084013935909414754519815682804339400213964099936730708205235842213229
55927614776786429496297417082007699144157982133295053640906023848486302
02517609321396789784130117396806277764196050265583129033185907648980376
90267449964429089792769703616777613163932164098550164496331591985225793
53600000000000000000000000000000000000000000000000000000000000000000000
00000000000000000

This is actually a significant overestimate since most pieces have an overall twist restriction and many pieces have unreachable orientations or their orientation is tied to the orientation / permutation of another set of pieces.

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

Top

 Post subject: Re: How to visualize pieces of a complex puzzlePosted: Tue Jan 08, 2013 5:25 pm

Joined: Mon Aug 02, 2004 7:03 am
Location: Koblenz, Germany
Brandon, you are to quick!
I wanted to post the results of my own analysis 14 minutes after you posted yours. Argh!

bmenrigh wrote:
Which suggests (I think) there are 52 independent sets of 60 pieces and 24 independent sets of 30 pieces and 6 independent sets of 20 pieces and 2 independent sets of 15 pieces and 1 independent set of 12 pieces and 2 independent sets of 10 pieces and another factor of 6 somewhere.
10^5169 ?
Ouch!
I see how you got your additional result from that awfully BIG number.
You assumed that every "piece type" has a parity restriction of 2 with respect to its permutations.

You mean there are 87 piece types plus that factor 6?
That means you count chiral partners as different piece types.

Burnsides Lemma tells me there are 82 pieces types.
2 types with 1 sample each.
2 types with 6 samples each.
2 types with 10 samples each.
6 types with 12 samples each.
2 types with 15 samples each.
6 types with 20 samples each.
12 types with 30 samples each.
42 types with 60 samples each. 6 types are split in two chiral sets.
8 types with 120 samples each. All 8 types are split in two chiral sets.

If we consider chiral pieces as of different type there are 96 types.
87 are really independent and one is somewhat dependent. Is that what you want to say?

Top

 Post subject: Re: How to visualize pieces of a complex puzzlePosted: Tue Jan 08, 2013 6:10 pm

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
Andreas Nortmann wrote:
Brandon, you are to quick!
I wanted to post the results of my own analysis 14 minutes after you posted yours. Argh!
Additional work and a different perspective is always welcome! To be fair, I adapted some existing code of mine which is why my response was quick.

Andreas Nortmann wrote:
bmenrigh wrote:
Which suggests (I think) there are 52 independent sets of 60 pieces and 24 independent sets of 30 pieces and 6 independent sets of 20 pieces and 2 independent sets of 15 pieces and 1 independent set of 12 pieces and 2 independent sets of 10 pieces and another factor of 6 somewhere.
10^5169 ?
Ouch!
I see how you got your additional result from that awfully BIG number.
You assumed that every "piece type" has a parity restriction of 2 with respect to its permutations.

You mean there are 87 piece types plus that factor 6?
That means you count chiral partners as different piece types.

I should clarify what I mean here. When I mean "independent sets of pieces" I mean a group of pieces in the same orbit. So one of your chiral set of 120 pieces would be two independent sets of 60 pieces. There are 52 of those.

Mathematically I think you're absolutely right that a chiral pair is the "same piece type" but I didn't implement mirroring in my code so my program sees that as two different piece types. This is why my program counts 96 when there are really only 82 if you collapse chiral pairs into a single piece type.

When you add my numbers 52 + 24 + 6 + 2 + 1 + 2 = 87 what I'm trying to say is that there are 87 orbits that don't affect each other. They can be in any even permutation independent of whatever permutation the others are in. The "additional factor of 6" is that of the remaining 96 - 87 = 9 orbits (pieces types), all together those can only be in 6 states independent of the other 87. Figuring out the details of this extra factor of 6 and how the remaining 9 pieces are restricted based on the other 87 would be really interesting but seems hard. It's probably that there is one piece type of the remaining 9 that is "somewhat independent" and the other 8 are totally dependent.

I know how to use Burnside's lemma (thanks to Jaap) to count either 96 or 82 however I don't know how to use it to get the breakdown you've listed below. Perhaps you can describe (or point me to where I can read) how to do that?

Andreas Nortmann wrote:
Burnsides Lemma tells me there are 82 pieces types.
2 types with 1 sample each.
2 types with 6 samples each.
2 types with 10 samples each.
6 types with 12 samples each.
2 types with 15 samples each.
6 types with 20 samples each.
12 types with 30 samples each.
42 types with 60 samples each. 6 types are split in two chiral sets.
8 types with 120 samples each. All 8 types are split in two chiral sets.

If we consider chiral pieces as of different type there are 96 types.
87 are really independent and one is somewhat dependent. Is that what you want to say?

Our tables are in agreement up until the edges, corners, and face pieces.
I count 24 types of pieces with 30 samples. You count 12. That would imply that 12 I counted are not chiral and 6 pairs are.

For the 60 samples, the 6 chiral sets account for the 6 chiral pieces with 30 samples, leaving 36 non-chiral face pieces and 8 chiral pairs.

So to better state my table:
• 2 sets of 1 piece
• 2 sets of 6 pieces
• 2 sets of 10 pieces
• 6 sets of 12 pieces
• 2 sets of 15 pieces
• 6 sets of 20 pieces
• 12 + 6 chiral pair (12) sets of 30 pieces
• 36 + 8 chiral pair (16) sets of 60 pieces

And then it's obvious why my count adds up to 96 instead of the more accurate 82.

I know what a chiral pair of face pieces looks like. Many of Gelatinbrain's puzzles have them. I'm trying to imagine what a chiral pair of edge pieces looks like though. I don't think any of Gelatinbrain's face-turning-dodecahedrons have chiral edge pieces. I wonder if both orientations are available to each chiral edge piece? It seems like that violate 3D geometry.

Schuma, any chance you can code up your program to emit GAP code for just the chiral edges? I'd like to know what orientations are available to them which we should be able to infer from the size of the group(s).

EDIT: it seems Gelatinbrain's 1.1.59 has chiral edges. It seems like they only have one orientation to them which is half of what the math says they could have (like how UD pieces on the Complex 3x3x3 should have 8 orientations but only 4 are reachable).
EDIT 2: Actually my code treats the 1.1.59 chiral edges as a single piece with 60 copies and only one orientation. I'm still curious what a chiral edge looks like and what orientation restrictions it has (if any).

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

Top

 Post subject: Re: How to visualize pieces of a complex puzzlePosted: Wed Jan 09, 2013 4:45 am

Joined: Mon Jul 21, 2008 4:52 am
Location: Brighton, UK
bmenrigh wrote:
I know what a chiral pair of face pieces looks like. Many of Gelatinbrain's puzzles have them. I'm trying to imagine what a chiral pair of edge pieces looks like though. I don't think any of Gelatinbrain's face-turning-dodecahedrons have chiral edge pieces. I wonder if both orientations are available to each chiral edge piece? It seems like that violate 3D geometry.
Would it be meaningful to view those pairs of edges as "split" edges rather than chiral edges? I am thinking of the peculiar "split" corners we have seen in the Circle Face Turning Octahedron on Gelatinbrain. So, if this applied to some of the sets of edges in the complex dodecahedron, one edge of each pair would moved by one half of a set of available twists/axes, and the other edge would be moved by the other half of available twists/axes. The split corners of the Circle FTO do have two orientations, like the conventional corners of that puzzle, so perhaps such edges of the complex doecahedron can also be re-oriented.

(I rarely contribute to these kinds of discussions because I often struggle to follow them, though I find it is always worth the effort, and I find them fascinating! Many thanks to all of you who contribute to these threads.)

Top

 Post subject: Re: How to visualize pieces of a complex puzzlePosted: Wed Jan 09, 2013 10:54 am

Joined: Mon Aug 02, 2004 7:03 am
Location: Koblenz, Germany
Here I want to use the term "ComplexDF2" as short version of "Complex faceturning dodecahedron with 2 independent layers per axis"

There is no way to use Burnsides Lemma for results like this. Sorry for creating this misunderstanding.
2-3 years ago there was a discussion about how many different CrazyMegaminxPluses are possible.
Back then I came up with a list of 82 variants in viewable form.
I took out those old results und analyzed them by hand.

I wouldn't just focus on what you call edges (chiral or not). I wouldn't call those pieces edges because an edge has 30 samples and these pieces have 60 samples.
In the long term we need a more general approach.
An example: The Complex 3x3x3 knows the piece UL (the wellknown edge) and the piece ULD (a self-invertible non-holding-point piece).
To "flip" the UL-piece you have to rotate the edge of the cube.
To "flip" the ULD-piece you have to rotate the L-side of the cube.
Both piece types have 12 samples but they obey different symmetrys.
Therefore they are of different "symmetry class" (I do not have a better term).
Julian gives an example for a third symmetry class with 12 samples per type.

You see UL and ULD have different symmetry classes but equal number of samples.
The same happens in the ComplexDF2 for the piece types with 60 samples.
Class 1: The T-pieces, X-pieces and W-pieces fall into the same symmetry class. They do not change their position when a reflection on an edge of the dodecahedron is applied to them.
Class 2: The 6 piece types with split up in chiral sets all fall into a second symmetry class. They do not change their position when a rotation on an edge is applied to them.
I tried to visualize the difference between the two classes in the image at the end of my posting.
A third symmetry class for pieces with 60 samples is possible but there is no example in the ComplexDF2.

In the hexahedral world there are
1 different symmetry classes for piece types with 48 samples.
5 different symmetry classes for piece types with 24 samples.
1 different symmetry classes for piece types with 16 samples.
9 different symmetry classes for piece types with 12 samples.
3 different symmetry classes for piece types with 8 samples.
7 different symmetry classes for piece types with 6 samples.
2 different symmetry classes for piece types with 4 samples.
1 different symmetry classes for piece types with 3 samples.
3 different symmetry classes for piece types with 2 samples.
1 different symmetry classes for piece types with 1 samples.
Some of them fall in chiral pairs. Some not.
I discovered some of these more awkward classes when I analyzed the ComplexHF4 (aka Complex5x5x5)

The dodecahedral world it is easier. There are
1 different symmetry classes for piece types with 120 samples.
3 different symmetry classes for piece types with 60 samples.
1 different symmetry classes for piece types with 40 samples.
3 different symmetry classes for piece types with 30 samples.
1 different symmetry classes for piece types with 24 samples.
3 different symmetry classes for piece types with 20 samples.
1 different symmetry classes for piece types with 15 samples.
3 different symmetry classes for piece types with 12 samples.
2 different symmetry classes for piece types with 10 samples.
1 different symmetry classes for piece types with 6 samples.
1 different symmetry classes for piece types with 5 samples.
1 different symmetry classes for piece types with 2 samples.
1 different symmetry classes for piece types with 1 samples.
Some of them fall in chiral pairs. Some not.
In the ComplexDF2 we were "lucky" that there are no pieces with awkward symmetry class except for the edge-rotation piece.

Pieces can have orientation only if their symmetry class contains rotational elements.
Corner pieces can have 3 orientations because they obey the corner-rotational-symmetry.
Edge pieces can have 2 orientations because they obey the edge-rotational-symmetry.
Face pieces (of the dodecahedron) can have 5 orientations because they obey the face-rotational-symmetry of the dodecahedron.
The 8 piece types with 120 samples do not have a rotational symmetry and therefore can't have orientation.
The 36 piece types with 60 samples without chiral sets do not have a rotational symmetry and therefore can't have orientation.
Pieces of the yet undiscovered third type (again with 60 samples) do not have a rotational symmetry and therefore can't have orientation.

 Attachments: sk60.png [ 3.52 KiB | Viewed 3442 times ]
Top

 Post subject: Re: How to visualize pieces of a complex puzzlePosted: Thu Jan 10, 2013 12:59 am

Joined: Thu Jul 23, 2009 5:06 pm
Location: Berkeley, CA, USA
I've been trying to explain the number of permutations given by Brandon, but I'm missing by a factor of 10.

Let me recap the situation:

As Brandon pointed out earlier, there are 52 sets of 60 pieces, 24 sets of 30 pieces, 6 sets of 20 pieces, 2 sets of 15 pieces, 2 sets of 10 pieces. All these pieces are conjectured to behave independently. Each types allows even permutation. 2 sets of 1 pieces are core and anti-core, and they don't move. The only unexplained part is 6 sets of 12 pieces, which are "like centers". In Brandon's notation, they are types #1, #11, #12, #67, #68, and #94. If they contribute (12!/2) * 6, then the numbers match.

The factor (12!/2) suggests that one set of centers must be moving independently with respect to all the other pieces that have been explained.

• The pentultimate centers happen to be such a type. They move to all even permutations. In Brandon's notation, they are type #12. They contribute (12!/2)
Let's look at the other types of centers:
• #1 is Megaminx centers which never move. Redundant.
• #11 is the Circle Pentultimate centers (centers of GB 1.1.35) which are always tied with Pentultimate centers #12. Redundant.
• #68 is anti Circle Pentultimate centers which are also tied with #12. Redundant.
• #67 is the centers of GB 1.1.50 or 1.1.51 which look pretty interesting but are also tied with #12. Redundant.
• The last type of centers is #94, they are the anti-Megaminx centers. They move, and the permutation of them are tied to the orientation of anti-core. If the orientation of anti-core is being considered, they are redundant. But we are ignoring all the orientations including the anti-core's, so type #94 is not redundant. They contribute a factor of 60, the symmetry of a dodecahedron.

So, the contribution of all the centers is (12!/2) * 60, which is ten times larger than the number we need.

There may be two possibilities:
(1) The huge number given by GAP is wrong. Either GAP generated incorrect result after 300 hours, or a digit of zero is lost by copy & paste... I don't think it's likely though.
(2) The permutation of centers is not independent of the permutation of other pieces so that only one tenth of the states is reachable.

I returned to my GAP code and selected a subset of pieces and compute the number of permutations, but I haven't found the missing factor of ten yet. Of course I cannot select all the pieces otherwise it will take another 300 hours. I've verified the following subsets:

(i) If all the types with strictly less than 30 pieces are selected (including all centers, center-bars, corner-bars, edge-bars, corners and similar pieces), the number of permutation is (20!/2)^6 * (15!/2)^2 * (12!/2) * (10!/2)^2 * 60. So the dependency is not between these pieces.

(ii) If all the types with strictly less than 30 pieces are selected, and any one out of 24 types with 30 pieces is also selected, the number of permutation is still as expected. Dependency is not here.

(iii) If all the types with strictly less than 20 pieces are selected, and any one of 52 types with 60 pieces is also selected, the number of permutation is still as expected. Dependency is not here.

But the dependency may still be somewhere. If we can eventually find it, it should be a pretty interesting argument.

In conclusion, assuming all the piece types are independent, we get a number that's ten times larger than the target. And I can't explain the difference.

Top

 Post subject: Re: How to visualize pieces of a complex puzzlePosted: Thu Jan 10, 2013 1:34 am

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
schuma wrote:
or a digit of zero is lost by copy & paste..

Looks like I just wasted a ton of our time on this. I just re-copy-and-pasted the number and factored it and got the missing extra factor of 2 and 5. It looks like somehow I left off a zero the first time I did it. The way GAP prints the number it takes up 68 lines of my terminal which is too tall so I cope-and-pasted in parts. I must have not stitched the parts together correctly.

The mystery is gone. The number makes sense. The one I posted is missing a trailing zero. I'll go fix it right now.

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

Top

 Post subject: Re: How to visualize pieces of a complex puzzlePosted: Thu Jan 10, 2013 1:47 am

Joined: Thu Jul 23, 2009 5:06 pm
Location: Berkeley, CA, USA
Hooray! Mystery is solved in the simplest way... Don't feel bad, we didn't waste much time.

Top

 Post subject: Re: How to visualize pieces of a complex puzzlePosted: Thu Jan 10, 2013 10:54 am

Joined: Mon Aug 02, 2004 7:03 am
Location: Koblenz, Germany
Schuma:
I want to make a minor amendment to your analysis.
If chiral sets are considered as 2 different types, the ComplexDF2 has 96 different types.
Your analysis covers only 94 piece types.
Brandon labeled the two piece types missing as #13 and #93.
These must be redundant too.

Top

 Post subject: Re: How to visualize pieces of a complex puzzlePosted: Thu Jan 10, 2013 11:53 am

Joined: Thu Jul 23, 2009 5:06 pm
Location: Berkeley, CA, USA
Andreas, you are absolutely right. I considered those two types, but forgot to write them down last night. They are tied to megaminx centers and anti megaminx centers, respectively. So they are redundant. Thanks.

Top

 Post subject: Re: How to visualize pieces of a complex puzzlePosted: Sat Jan 12, 2013 9:48 pm

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
Andreas, thank you for your detailed post above. I'm still thinking about all of the things you said.

I do like your term "symmetry class" a lot.

I agree with you that pieces only have orientation if their symmetry class contains a rotation. For the ComplexDF2, pieces with a symmetry class that does not contain any rotational or reflectional elements have 120 copies in two chiral orbits and do not have any orientation. Piece in a symmetry class that only has reflectional symmetry come in 60 samples. They would have orientation if the physical versions of the puzzle supported mirroring as a move but because the ComplexDF2 does not, they don't have any orientation in practice.

The reason I was calling the various pieces "analogous to edges" or corners or centers, etc. is that if the symmetry classes has a rotational element when the dodecahedron is rotated about an edge, or corner, or face, then the resulting pieces will have similar properties to pieces we think of as edges, corners, or face centers.

The pieces I was calling "chiral edge pieces" have a symmetry class that can be rotated about a dodecahedron edge however it can not be mirrored. If you mirror it then the pieces move an this is why there are two chiral orbits and there are 60 samples rather than 30.

Take this piece:
Found 30 pieces of type 19 ( , B, , D, E, , G, , , , , ) with twist freedom 2

It is only one half of a chiral pair of "edge-like" pieces. I took some time to visualize this piece and I think I have a viable representation of it now. The pieces can be thought of as "bars" between two edges:
Attachment:

complex_dodeca_chiral_edge_bars.png [ 22.85 KiB | Viewed 3269 times ]

The black centers mark the "grips" for the pink bar. As you can see, if you mirror the dodecahedron horizontally than the pink grip changes to a the dark blue face and you end up with the blue bar instead.

The bar can be thought of as going between the A edge and B edge which are the two edges between the two adjacent pairs of grips.

I have labeled edge E because this is the edge the dodecahedron must be rotated by to match the symmetry class for the pink bar. Here that is that rotation:
Attachment:

complex_dodeca_chiral_edge_bars_reorient_e.png [ 20.13 KiB | Viewed 3269 times ]

Notice that the pink bar can be rotated about E without changing position, only orientation. These "bars" can be flipped upside down.

I think Gelatinbrain could use a trick with circles like he did on 1.1.82 to show these edges bar pieces. Here is what I think that would look like for the pink bar:
Attachment:

complex_dodeca_chiral_edge_bars_circle_view.png [ 19.55 KiB | Viewed 3269 times ]

For each edge on the dodecahedron there would be 4 of these edge bars touching it. Two of each chirality. I have drawn 4 for an edge here:
Attachment:

complex_dodeca_chiral_edge_bars_4.png [ 151.11 KiB | Viewed 3269 times ]

I still have to do a lot of thinking about some of the other symmetry classes you've pointed out.

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

Top

 Post subject: Re: How to visualize pieces of a complex puzzlePosted: Sun Jan 13, 2013 2:10 am

Joined: Thu Jul 23, 2009 5:06 pm
Location: Berkeley, CA, USA
This afternoon I extended my ruby code that generates GAP code about complex puzzles to support "Complex Polygons". Complex Polygons are essentially 2D versions of the complex puzzles that we've talked about.

For example, Complex Square (4-gon) consists of 2^4=16 squares. On each of the four sides of each of the square, there may or may not be a "dot", or, I'd like to call it as a "knob". When we flip, let's say, the up side of the whole puzzle, we examine all the squares. If a square has a knob on the up side, the square will be flipped; otherwise the square will remain unchanged. This puzzle is a super-set of the 3x3x1 cuboid. The whole puzzle can be simulated by two 3x3x1's, when you turn one layer on the first 3x3x1, you turn two layers on the second 3x3x1. This simulation contains all the non-redundant pieces of the complex square. The redundant pieces are the center-bars. If you don't have two 3x3x1's, you can also do it using two Rubik's Cubes. You turn the first cube by U2, D2, L2, or R2 and the second cube by u2, d2, l2, or r2.

Using my ruby&GAP code, I computed the number of permutations of complex n-gon for n=3,4,5,6,7, and then manually analyzed n = 3~6 to understand what can happen to the pieces. Generally speaking, odd n's (3,5) are kind of boring and nothing special happens. Even n's (4,6) are more complicated and fun to analyze.

For future reference, I attached the numbers below. My analysis can be found in the file named ComplexPolygons.txt in the Github repo.

Complex {3}: 96
Complex {4}: 384
Complex {5}: 603979776000
Complex {6}: 118881339310080000
Complex {7}: 131767294509897456998422461440289444903770642689599429672960000000000

If you have cloned the latest repo, you can run:

Code:
ruby generate.rb n

with n>=3 to generate a GAP code and run the GAP code.

Top

 Post subject: Re: How to visualize pieces of a complex puzzlePosted: Sun Jan 13, 2013 12:02 pm

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

Thank you for explaining your understanding of "chiral edges".
I feel quite ashamed to post only something rather short.
Anyway:
bmenrigh wrote:
Piece in a symmetry class that only has reflectional symmetry come in 60 samples.
I agree but have to add:
Just stating "has reflectional symmetry" is not enough. There are two symmetry classes which piece types have 60 samples. The first obeys the reflection along a plane going throug opposite edges. The second obeys the reflection on the center. This is the yet unknown third class I mentioned above.
In the hexahedral world there are three symmetry classes that only have reflectional symmetry and come in 24 samples => Counting is not enough.

bmenrigh wrote:
The reason I was calling the various pieces "analogous to edges" or corners or centers, etc. is that if the symmetry classes has a rotational element when the dodecahedron is rotated about an edge, or corner, or face, then the resulting pieces will have similar properties to pieces we think of as edges, corners, or face centers.
I understand. My point here is: The "true edges" (those without chiral partners) have additional reflectional symmetry which the "chiral edges" do not have. They are therefore in different symmetry classes. I wanted to prevent a misunderstanding.

bmenrigh wrote:
I still have to do a lot of thinking about some of the other symmetry classes you've pointed out.

Top

 Post subject: Re: How to visualize pieces of a complex puzzlePosted: Sun Jan 13, 2013 2:54 pm

Joined: Thu Dec 02, 2004 12:09 pm
Location: Missouri
Just noticed this thread had jumped back to life yesterday. It took me till now just to catch up. Consider my mind blown... It will take me a while to digest all this new info. For now I'll just ask this:
Andreas Nortmann wrote:
In the hexahedral world there are
1 different symmetry classes for piece types with 48 samples.
5 different symmetry classes for piece types with 24 samples.
1 different symmetry classes for piece types with 16 samples.
9 different symmetry classes for piece types with 12 samples.
3 different symmetry classes for piece types with 8 samples.
7 different symmetry classes for piece types with 6 samples.
2 different symmetry classes for piece types with 4 samples.
1 different symmetry classes for piece types with 3 samples.
3 different symmetry classes for piece types with 2 samples.
1 different symmetry classes for piece types with 1 samples.
Some of them fall in chiral pairs. Some not.
I discovered some of these more awkward classes when I analyzed the ComplexHF4 (aka Complex5x5x5).
So how do you know this list is complete? Couldn't the Complex7x7x7 introduce even more awkward classes? Or is there some proof that this is it?

Great work guys. I wish I could contribute more but its a struggle just to understand all the info that's already been posted.

Thanks,
Carl

_________________
-

Top

 Post subject: Re: How to visualize pieces of a complex puzzlePosted: Mon Jan 14, 2013 11:14 am

Joined: Mon Aug 02, 2004 7:03 am
Location: Koblenz, Germany
wwwmwww wrote:
So how do you know this list is complete? Couldn't the Complex7x7x7 introduce even more awkward classes? Or is there some proof that this is it?
Every piece type of a ComplexNxNxN obeys a subgroup of the hexahedral symmetries. That means you have to find enumerate those subgroups and that it is.
The 33 subgroups are all which is possible. You can either trust me that I prooved it (which I unintentionally did during another analysis) or you can trust Jaap that he knows about what he is talking:
http://www.jaapsch.net/puzzles/symmetr1.htm

Top

 Post subject: Re: How to visualize pieces of a complex puzzlePosted: Mon Jan 14, 2013 11:54 am

Joined: Thu Dec 02, 2004 12:09 pm
Location: Missouri
Andreas Nortmann wrote:
You can either trust me...
I trust you. I was just thinking of how the piece types grow exponentially as one goes to higher N in the Complex NxNxN puzzles. I guess this means we are just getting more and more piece types in each symmetry class. Does symmetry say anything about the number of piece types one should expect in a given symmetry class say for a given order of N?

Thanks,
Carl

_________________
-

Top

 Post subject: Re: How to visualize pieces of a complex puzzlePosted: Mon Jan 14, 2013 12:45 pm

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
Hey Carl this doesn't directly answer you question but counting the unique piece types for a face-turning cube using Burnside's Lemma would be:

? burnside_cube(n) = ((3 * 2) * n^3 + 3 * n^4 + (4 * 2) * n^2 + 6 * n^3 + n^6) / 24
% = (n)->((3*2)*n^3+3*n^4+(4*2)*n^2+6*n^3+n^6)/24
? burnside_cube(2)
% = 10
? burnside_cube(3)
% = 57
? burnside_cube(4)
% = 240
? burnside_cube(5)
% = 800

N is the "number of colors" for each side. For the complex 3x3x3 that's a binary digit, turns or does not turn with a side so N = 2. For the Complex 5x5x5 there are two choices, one per slice on a side so N = 2^2 = 4.

I'm really not sure about the Complex4x4x4 but it might be N=3. For the Comple6x6x6 it's probably N = 7 but again, I'm not sure. It would definitely be N=8 for the Complex 7x7x7 because there are three slices per face and 2^3 = 8.

EDIT: of course this is for only rotations and not mirroring / reflections. I'd love to see how to extend this to handle reflections. It should provide the same answer for N = 2 but different answers for others since Andreas has pointed out there are chiral pieces for some bigger Complex NxNxN puzzles.

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

Top

 Post subject: Re: How to visualize pieces of a complex puzzlePosted: Tue Jan 15, 2013 11:12 am

Joined: Mon Aug 02, 2004 7:03 am
Location: Koblenz, Germany
wwwmwww wrote:
Does symmetry say anything about the number of piece types one should expect in a given symmetry class say for a given order of N?
No, although the more "common" symmetry classes (the ones for F, C, E, X, T, L) will occur way more often than the more awkward ones. But that is more perception than a proovable theorem.

On a sidenote: There are symmetry classes for which I can proove that there will NEVER be piece types with this class in puzzles with axis systems HF, HC, HE and hybrids thereof. I haven't checked that for every symmetry class.

bmenrigh wrote:
I'd love to see how to extend this to handle reflections.
Here comes an untested version with some explanations:

burnside_cube(n) = (
n^6 + //identity
3 * n^4 + //rotation around a face by 180Â°
(3 * 2) * n^3 + //rotation around a face by 90Â°
(4 * 2) * n^2 + //rotation around a corner by 120Â°
6 * n^3 + //rotation around an edge
n^3 + //reflection on the central point
3 * n^5 + //reflection on a parallel plane
6 * n^2 + //rotoreflection (spiral) around a face
8 * n^1 + //rotoreflection (spiral) around a corner by 120Â°
6 * n^4 //reflection on a diagonal plane
) / 48

BTW:
Brandon: If you edit the LATEST posting of a thread I will not be marked as edited. Therefore you do not need to amend your postings or highlight what you edited. Please forgive me if you already knew this.

Top

 Post subject: Re: How to visualize pieces of a complex puzzlePosted: Tue Jan 15, 2013 11:59 am

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
Andreas Nortmann wrote:
burnside_cube(n) = (
n^6 + //identity
3 * n^4 + //rotation around a face by 180Â°
(3 * 2) * n^3 + //rotation around a face by 90Â°
(4 * 2) * n^2 + //rotation around a corner by 120Â°
6 * n^3 + //rotation around an edge
n^3 + //reflection on the central point
3 * n^5 + //reflection on a parallel plane
6 * n^2 + //rotoreflection (spiral) around a face
8 * n^1 + //rotoreflection (spiral) around a corner by 120Â°
6 * n^4 //reflection on a diagonal plane
) / 48

This provides viable numbers so it's probably correct. I completely understanding:
n^3 + //reflection on the central point
3 * n^5 + //reflection on a parallel plane
6 * n^4 //reflection on a diagonal plane

I do not understand:
6 * n^2 + //rotoreflection (spiral) around a face
8 * n^1 + //rotoreflection (spiral) around a corner by 120Â°

I could make sense of both of these if they were reflecting about the plane that bisects the cube like a 2x2x2 cut and the plane like a Skewb cut, respectively. If you follow up that reflection by a rotation than your orbit numbers look just right. I take it that's not the plane though because then the number of reflections would be 3 and 4 respectively, not 6 and 8. These sorts of reflections have been my hangup for calculating burnside's correctly so any pointers would help me a lot.

Andreas Nortmann wrote:
BTW:
Brandon: If you edit the LATEST posting of a thread I will not be marked as edited. Therefore you do not need to amend your postings or highlight what you edited. Please forgive me if you already knew this.
I have certain threads set to notify me when a post is made in the thread. That email goes through a procmail rule that invokes a perl script that summarizes the email, cuts it all down to 140 characters and send my phone a SMS. I normally read posts within 5 minutes of them being made, often just 1 minute.

Because of this I assume that there are plenty of others that will also read my post within a few minutes of making it so I prefer to call out the changes explicitly so that others will notice when I've added or corrected something.

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

Top

 Post subject: Re: How to visualize pieces of a complex puzzlePosted: Wed Jan 16, 2013 11:17 am

Joined: Mon Aug 02, 2004 7:03 am
Location: Koblenz, Germany
bmenrigh wrote:
I do not understand:
6 * n^2 + //rotoreflection (spiral) around a face
8 * n^1 + //rotoreflection (spiral) around a corner by 120Â°
I could make sense of both of these if they were reflecting about the plane that bisects the cube like a 2x2x2 cut and the plane like a Skewb cut, respectively. If you follow up that reflection by a rotation than your orbit numbers look just right. I take it that's not the plane though because then the number of reflections would be 3 and 4 respectively, not 6 and 8. These sorts of reflections have been my hangup for calculating burnside's correctly so any pointers would help me a lot.
Sadly I do not fully understand your problem but I will try it anyway.

I used the term "rotoreflection" because I remembered it from this article:
http://en.wikipedia.org/wiki/Octahedral ... _classes_2
There you can see that it have to be 6 and 8.
Sadly I didn't remember the 60Â°

You are right about the planes, because of the definition of rotoreflection:
Rotoreflection is a rotation about an axis, combined with reflection in a plane perpendicular to that axis.

I has to be 6 because there are rotoreflections by 90Â° in both negative and positive direction for 3 axis.
I has to be 8 because there are rotoreflections by 60Â° in both negative and positive direction for 4 axis.
This is analogous to the rotations which come in negative and positive directions for their axis, too.

Top

 Post subject: Re: How to visualize pieces of a complex puzzlePosted: Sat Mar 09, 2013 2:49 am

Joined: Thu Jul 23, 2009 5:06 pm
Location: Berkeley, CA, USA
The 2D version of Complex puzzles have been implemented. Please see this thread.

Top

 Post subject: Re: How to visualize pieces of a complex puzzlePosted: Mon May 20, 2013 6:25 pm

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
bmenrigh wrote:
I have restarted the Complex Edge-Turning-Cube and Complex Face-Turning-Dodecahedron on a machine with a lot more memory and slightly faster CPUs. It will be about 12 days before I catch up to where I was on my laptop.

After 168680 CPU-minutes (116 days) I needed to re-purpose my machine. The calculation didn't show any signs of making progress. Unless GAP is updated to use multiple CPUs this calculation isn't feasible. Even then it may not be (the calculation may need years).

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

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 2 of 2 [ 82 posts ] Go to page Previous  1, 2

 All times are UTC - 5 hours

#### Who is online

Users browsing this forum: No registered users and 7 guests

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot post attachments in this forum

Search for:
 Jump to:  Select a forum ------------------ Announcements General Puzzle Topics New Puzzles Puzzle Building and Modding Puzzle Collecting Solving Puzzles Marketplace Non-Twisty Puzzles Site Comments, Suggestions & Questions Content Moderators Off Topic