# Decadecaflexagon and Group theory



## Solve (Oct 2, 2012)

I have been trying to find a puzzle with the largest number of permutations without being massive, like a petaminx. The most "efficient" way to get a large number of permutations. One of the things I have been looking at is types of turning. There are skewb puzzles, face-turning puzzles, corner turning puzzles, and edge turning puzzles. From here, I used process of elimination. The skewb doesn't have a whole lot of permutations (so it seems), so I cut that one out. Same thing with the dino cube.

Here is where I have some questions. I was going to compare the curvy copter cube (edge turning) to the rubik's cube (face turning) because it appears to be the 3x3 equivalent of the helicopter cube. However, the curvy copter cube jumbles while the rubik's cube does not. So, to fix this problem, I decided to only allow 180 degree moves on the curvy copter. This way, it wouldn't be able to go into other "orbits" or jumble. However, I cannot find the number of permutations using this guideline. Can anyone help me with this?

Okay, so after that, I had more questions. What about sliding puzzles? If you were to have a sliding puzzle that was the equivalent size to a 2x2 Rubik's cube, which would have more permutations? This concept has been demonstrated by Oskar's sliding cube, shown here:

http://www.youtube.com/watch?v=S9HH2FlOmv0

And, if it did have more permutations, then why? Is it because you can move each piece individually, not dependent on which face or edge it is on?

Which brings me to a new question I had, which is what about these:

http://www.twistypuzzles.com/forum/viewtopic.php?f=15&t=15126

In this video:

http://www.youtube.com/watch?feature=player_embedded&v=COtfw9-UvJY

the creator demonstrates how you can flip one piece at a time. Does this mean that this puzzle can switch "orbits?" (or "universes?")

Do these flexagon puzzles have more permutations than other puzzles?

Thank you if you've read this whole post, I'm looking forwards to what discussion may come of it.


----------



## ben1996123 (Oct 2, 2012)




----------



## Solve (Oct 2, 2012)

Yeah, that is where I got it. Vihart is one of my favorite youtubers. She makes amazing videos.


----------



## qqwref (Oct 2, 2012)

Solve said:


> I have been trying to find a puzzle with the largest number of permutations without being massive, like a petaminx. The most "efficient" way to get a large number of permutations.


Um, what? Do you mean the largest number of permutations with a limited number of pieces? If that's the case, I'd like to suggest a good candidate: a dihedral puzzle, in the shape of a prism, where you can turn the top layer to any position or rotate half of the puzzle by 180 degrees, kinda like the Rubik's UFO (http://www.jaapsch.net/puzzles/rubufo.htm) but with any number of pieces. You can construct a puzzle like this with n pieces as long as n is divisible by 4, and there will be (n-1)! possible positions as long as the pieces are all marked separately. Even better would be a puzzle where pieces have orientation, like a version of the above puzzle where instead of rotating half the puzzle about 180 degrees you'd rotate four pieces (two on each layer) by 90 degrees. For larger n this would probably have to be in a ring instead of a solid disk. Then each piece would have 3 orientations, with a parity constraint, so there would be (n-1)! * 3^(n-1) positions. The 2x2x2 is actually the 8-piece version of this second puzzle. Of course, you could push the definitions a bit and make a puzzle with "trivial tip" type protrusions that can be rotated to, say, 1000 distinct positions each... but that's kind of cheating.




Solve said:


> Here is where I have some questions. I was going to compare the curvy copter cube (edge turning) to the rubik's cube (face turning) because it appears to be the 3x3 equivalent of the helicopter cube. However, the curvy copter cube jumbles while the rubik's cube does not. So, to fix this problem, I decided to only allow 180 degree moves on the curvy copter. This way, it wouldn't be able to go into other "orbits" or jumble. However, I cannot find the number of permutations using this guideline. Can anyone help me with this?


The curvy copter has 3 types of pieces: edges, which can't change position but have two orientations each; centers, with no orientation and in four orbits of six pieces each (unless you use jumbling algs, in which case they are all in the same orbit ); and corners, with three orientations each. We'll assume the orientation is fixed, and we don't have to fix any pieces except the edge positions since the orientation is clear from the edge coloring. Every move flips one edge, swaps one pair of corners, and swaps two pairs of centers. So the parity constraints are that the edge flip parity must be the same as the corner flip parity, and the overall center parity must be even.

Then we have 2^12 positions for the edges, 8! * 3^7/2 positions for the corners (that /2 is to make sure the corner parity matches the edge flip parity), and (6!)^4/2 positions for the centers (again the /2 is for parity). So if I didn't make a mistake the total number of positions should be 2^10 * 8! * 3^7 * (6!)^4, or about 2.4266 * 10^22.




Solve said:


> Okay, so after that, I had more questions. What about sliding puzzles? If you were to have a sliding puzzle that was the equivalent size to a 2x2 Rubik's cube, which would have more permutations? And, if it did have more permutations, then why? Is it because you can move each piece individually, not dependent on which face or edge it is on?


Yep. You have 23 pieces here, and if they weren't labeled with their "orientation" you could imagine that any way of placing those 23 pieces on the cube is possible, a sharp contrast to the 2x2 where you can't just put the stickers on there in any way. The number of positions would be 24!/((4!)^5 * (3!)), or about 1.2986 * 10^16.

Oskar's puzzle, of course, has permutation on each piece, which adds a factor of 4 possibilities to each of the 23 pieces. I'm not sure if there is a parity constraint or not (that is, can you change the orientation of one piece without affecting the rest?) but if there isn't the number of possibilities will be multiplied by 4^23, bringing the total all the way to about 9.1385 * 10^29, way more than a Rubik's Cube.



Solve said:


> Which brings me to a new question I had ... In this video ... the creator demonstrates how you can flip one piece at a time. Does this mean that this puzzle can switch "orbits?" (or "universes?")


I'm having a hard time trying to figure out how these guys work, mostly because it seems like there's so many possible moves. Even in the standard decagonal state you may have many different invisible configurations of the paper underneath, which will of course affect the number of moves you can do from that state. I think finding out what sticker positions are possible will be quite difficult, and because this is very different from a twisty puzzle the stuff we've figured out about twisty puzzles probably won't help much.

One idea that might help is to think of the whole thing as a ring of connected pieces - I believe the decadecaflexagon in the video has 50 pieces with a sticker on each side. So then the question is, what rules govern which of the pieces are visible? Do all of the visible pieces on one side of the puzzle have to come from the same side? Can we choose any 10 of the 50 pieces to show, or do they have to be sufficiently far apart? Do the pieces that are shown on the front always determine the pieces that are shown on the back? You'll probably have to answer most of these questions by making one yourself and playing around with it. Good luck, if you are interested


----------



## Solve (Oct 2, 2012)

Wow, what a great reply! That must of taken a lot of time .



qqwref said:


> Um, what? Do you mean the largest number of permutations with a limited number of pieces? If that's the case, I'd like to suggest a good candidate: a dihedral puzzle, in the shape of a prism, where you can turn the top layer to any position or rotate half of the puzzle by 180 degrees, kinda like the Rubik's UFO (http://www.jaapsch.net/puzzles/rubufo.htm) but with any number of pieces.



Thanks for the suggestion! You make a good point, I hadn't really thought of a solid way to quantify that.



> (unless you use jumbling algs, in which case they are all in the same orbit )



Ha!



> Then we have 2^12 positions for the edges, 8! * 3^7/2 positions for the corners (that /2 is to make sure the corner parity matches the edge flip parity), and (6!)^4/2 positions for the centers (again the /2 is for parity). So if I didn't make a mistake the total number of positions should be 2^10 * 8! * 3^7 * (6!)^4, or about 2.4266 * 10^22.



This is just what I was looking for. This is great! Thanks a lot!



> Yep. You have 23 pieces here, and if they weren't labeled with their "orientation" you could imagine that any way of placing those 23 pieces on the cube is possible, a sharp contrast to the 2x2 where you can't just put the stickers on there in any way. The number of positions would be 24!/((4!)^5 * (3!)), or about 1.2986 * 10^16.



Again, perfect.



> I'm having a hard time trying to figure out how these guys work, mostly because it seems like there's so many possible moves. Even in the standard decagonal state you may have many different invisible configurations of the paper underneath, which will of course affect the number of moves you can do from that state. I think finding out what sticker positions are possible will be quite difficult, and because this is very different from a twisty puzzle the stuff we've figured out about twisty puzzles probably won't help much.



Yeah, they do appear to have their own type of movement to them.



> You'll probably have to answer most of these questions by making one yourself and playing around with it. Good luck, if you are interested


I'll print some out tonight!


----------



## Ickathu (Oct 2, 2012)

vihart <3
I've so many hexaflexagons since yesterday morning 

As for the actual question, what about like a jigsaw puzzle? One of those where each piece is shaped exactly the same so any piece can go in any location. Just a 100 piece puzzle of this type would have 9e157 permutations.


----------



## vcuber13 (Oct 3, 2012)

you didnt account for the edges or corners
should be 64!*4!*32!=8.01*10^125


----------



## Solve (Oct 3, 2012)

Ickathu said:


> vihart <3
> I've so many hexaflexagons since yesterday morning
> 
> As for the actual question, what about like a jigsaw puzzle? One of those where each piece is shaped exactly the same so any piece can go in any location. Just a 100 piece puzzle of this type would have 9e157 permutations.



This is a great idea. It's so simple.


----------



## cuBerBruce (Oct 3, 2012)

qqwref said:


> The curvy copter has 3 types of pieces: edges, which can't change position but have two orientations each; centers, with no orientation and in four orbits of six pieces each (unless you use jumbling algs, in which case they are all in the same orbit ); and corners, with three orientations each. We'll assume the orientation is fixed, and we don't have to fix any pieces except the edge positions since the orientation is clear from the edge coloring. Every move flips one edge, swaps one pair of corners, and swaps two pairs of centers. So the parity constraints are that the edge flip parity must be the same as the corner flip parity, and the overall center parity must be even.
> 
> Then we have 2^12 positions for the edges, 8! * 3^7/2 positions for the corners (that /2 is to make sure the corner parity matches the edge flip parity), and (6!)^4/2 positions for the centers (again the /2 is for parity). So if I didn't make a mistake the total number of positions should be 2^10 * 8! * 3^7 * (6!)^4, or about 2.4266 * 10^22.



My GAP model indicates there are only 1/8 as many positions. The reason is that the parity of each face piece orbit is determined by the set of edge pieces that are flipped. If all edges are oriented, then all four face piece orbits must have even parity.

By the way, GAP is a programming language that is great for figuring out the number of positions for lots of twisty puzzles. If you can describe each basic move of the puzzle as a permutation, then it's a simple thing to have GAP calculate the size of the group generated by those basic moves. Of course, you may have to take into account if those moves allow you to reach a position that is a whole puzzle rotation (which you typically don't want to count as separate positions); that each group element represents a distinct puzzle position (not the case if pieces in an orbit are indistinguishable); and that all moves are possible regardless of past moves applied (generally not the case for bandaged type puzzles, for instance). So basically, if a puzzle has N facelets, you number them from 1 to N, and then define the basic moves of the in GAP as permutation on those numbers (facelets) using cycle notation. Then you can use built-in functions to get a group object using those basic moves as the group's generators, and to get the size of that group (and much more).


----------



## Solve (Oct 5, 2012)

I'll look into GAP. It sounds like it could help me.

I had another question though. On this website:

http://www.economist.com/node/3445734?story_id=3445734

It says that there are "dead ends along the way" while solving a puzzle. What does that mean?


----------



## stannic (Oct 6, 2012)

Solve said:


> I had another question though. On this website:
> 
> http://www.economist.com/node/3445734?story_id=3445734
> 
> It says that there are "dead ends along the way" while solving a puzzle. What does that mean?



This applies also to the bandaged Rubik's cube. The moves are often blocked due to glued pieces, and this makes the puzzle harder to solve. Sliding puzzles with tiles other than 1x1 can be viewed as puzzles with glued tiles.

These "Klotski-type" puzzles have less permutations than normal puzzles with 1x1 tiles. However, they often require much more moves to solve.

- stannic


----------



## Ickathu (Oct 6, 2012)

vcuber13 said:


> you didnt account for the edges or corners
> should be 64!*4!*32!=8.01*10^125



That's still a huge number... Not quite as big as a 7x7, but fairly close (relatively speaking) (1.95*10^160)


----------



## Solve (Oct 6, 2012)

stannic said:


> This applies also to the bandaged Rubik's cube. The moves are often blocked due to glued pieces, and this makes the puzzle harder to solve. Sliding puzzles with tiles other than 1x1 can be viewed as puzzles with glued tiles.
> 
> These "Klotski-type" puzzles have less permutations than normal puzzles with 1x1 tiles. However, they often require much more moves to solve.
> 
> - Bulat



So corner-turning puzzles don't intrinsically have more dead ends than say, sliding puzzles? Is there any way that you could come up with the most bandaged (or jumbling, since they are actually very similar) puzzle, similar to the "Quzzle" in the article?

Maze puzzles also interest me. They also include dead ends (although a different type). I will have to do some more research on them.

I am very pleased with the information I have received in this thread. Thank you so much to everyone who has participated.


----------



## vcuber13 (Oct 6, 2012)

Ickathu said:


> That's still a huge number... Not quite as big as a 7x7, but fairly close (relatively speaking) (1.95*10^160)



i didnt say it was small

if 10^126 is huge then 10^34 isnt small


----------



## stannic (Oct 6, 2012)

Solve said:


> So corner-turning puzzles don't intrinsically have more dead ends than say, sliding puzzles? Is there any way that you could come up with the most bandaged (or jumbling, since they are actually very similar) puzzle, similar to the "Quzzle" in the article?
> 
> Maze puzzles also interest me. They also include dead ends (although a different type). I will have to do some more research on them.
> 
> I am very pleased with the information I have received in this thread. Thank you so much to everyone who has participated.



As you're trying to find a puzzle with the largest number of permutations, I do not know if bandaged sliding and/or twisty puzzles are what you're asking for.
However, as for your question about finding the most bandaged puzzle, it depends on definition of the "bandagedness". Basically, more bandaged puzzles have fewer configurations since gluing any two pieces together will always reduce the number of configurations. Also, hard puzzles probably should have many "dead-ends" compared with the total number of configurations. But with this definition, the "most bandaged" is 1x1 sliding puzzle with single tile or 1x1x1 Rubik's cube, which are not very interesting.

Dead-end position is essentially the configuration with the only move from it. The same holds for mazes where dead-end location is surrounded by three walls.

As for maze puzzles, there are some automated methods. However, I do not know about any algorithms to generate the "most bandaged" or interesting sliding or twisty puzzle. It's interesting question, though.
By analogy with mazes, probably most interesting puzzles will have no "loops"; that is, you cannot start from some configuration and return to the same configuration from another path. However, this is just an observation.

I would like to say that it's an art form. For example, take a look at the puzzles from Serhiy Grabarchuk.
Personally, I like design of _The Quadrion Puzzle_ (even though I didn't manage to solve it). Also, pentomino mosaics are very impressive and probably have many dead-ends.

- stannic


----------



## Stefan (Oct 6, 2012)

stannic said:


> Dead-end position is essentially the configuration with the only move from it.



The article uses that term in the context of a "solution tree", though, and the puzzle graph probably isn't a tree. So their dead ends could have more than one move.


----------



## stannic (Oct 6, 2012)

Stefan said:


> The article uses that term in the context of a "solution tree", though, and the puzzle graph probably isn't a tree. So their dead ends could have more than one move.



Probably you're right. I've read sentences "The taller the tree, the more moves are required to get to the solution. The broader the tree, the more dead ends there are along the way." as if Mr Lewis searched for puzzles with both long optimal solution and many actual "dead-end" ways during solution. However, the puzzle graph actually is not a tree in the case of Quzzle puzzle, so maybe dead-ends mentioned in the article are also false paths that bring the solver farther from the goal.

*Edit*: Oops, it seems like I have to verify that. (Done, the version with unmarked tiles has non-trivial loops).


Spoiler: More details



After finding optimal solution in 84 moves to the Quzzle, SBP Solver shows that there are only 881 different reachable (in <= 84 moves) positions, so it seems to be possible to find all existing loops (if any).

*Edit 2*: Well, there are some trivial loops (such as moving two horizontal 2x1 pieces 1st left, 2nd left, 1st right, then 2nd right). I'll try to find at least one non-trivial loop.

*Edit 3*: In Quzzle puzzle, with starting configuration (1122/1134/0034/5667/5889) (where 0 are empty locations), there are 2664 distinct reachable states. If I did the calculations correctly, the God's number is 219 if you're allowed to move only one tile one unit in one direction per move. The only antipode in this metric is (2211/4311/4350/8850/9766).

If you're counting positions with the same "shape" as the same, not looking at the numbers on tiles, then there are only 888 unique reachable configurations. God's number in this case is 121 move; the antipode shape is the same as in first case (up to the permutation: (2211/5411/5430/8830/9766)).


Spoiler: Distributions





```
1. Numbered tiles
   d     count     total
   0         1         1
   1         2         3
   2         2         5
   3         3         8
   4         4        12
   5         6        18
   6         5        23
   7         4        27
   8         4        31
   9         5        36
  10         4        40
  11         3        43
  12         3        46
  13         1        47
  14         1        48
  15         2        50
  16         3        53
  17         3        56
  18         3        59
  19         4        63
  20         5        68
  21         5        73
  22         5        78
  23         5        83
  24         4        87
  25         2        89
  26         1        90
  27         2        92
  28         3        95
  29         3        98
  30         2       100
  31         1       101
  32         2       103
  33         4       107
  34         5       112
  35         4       116
  36         4       120
  37         5       125
  38         8       133
  39         9       142
  40         7       149
  41         9       158
  42        12       170
  43        16       186
  44        15       201
  45        13       214
  46        14       228
  47        15       243
  48        13       256
  49         9       265
  50        11       276
  51        14       290
  52        14       304
  53        16       320
  54        14       334
  55        14       348
  56        12       360
  57        10       370
  58        12       382
  59        15       397
  60        19       416
  61        18       434
  62        14       448
  63        15       463
  64        16       479
  65        15       494
  66        14       508
  67        13       521
  68        14       535
  69        13       548
  70        14       562
  71        14       576
  72        11       587
  73        12       599
  74        15       614
  75        15       629
  76        17       646
  77        16       662
  78        11       673
  79         9       682
  80        10       692
  81        10       702
  82        12       714
  83        14       728
  84        18       746
  85        19       765
  86        17       782
  87        16       798
  88        17       815
  89        20       835
  90        23       858
  91        27       885
  92        26       911
  93        22       933
  94        18       951
  95        13       964
  96        15       979
  97        16       995
  98        18      1013
  99        24      1037
 100        27      1064
 101        24      1088
 102        24      1112
 103        20      1132
 104        16      1148
 105        16      1164
 106        14      1178
 107        14      1192
 108        21      1213
 109        27      1240
 110        30      1270
 111        30      1300
 112        27      1327
 113        22      1349
 114        17      1366
 115        16      1382
 116        15      1397
 117        16      1413
 118        15      1428
 119        16      1444
 120        18      1462
 121        13      1475
 122        12      1487
 123        15      1502
 124        15      1517
 125        17      1534
 126        16      1550
 127        11      1561
 128         9      1570
 129        10      1580
 130        10      1590
 131        12      1602
 132        14      1616
 133        18      1634
 134        19      1653
 135        17      1670
 136        16      1686
 137        17      1703
 138        20      1723
 139        23      1746
 140        27      1773
 141        26      1799
 142        22      1821
 143        18      1839
 144        13      1852
 145        15      1867
 146        16      1883
 147        18      1901
 148        24      1925
 149        27      1952
 150        24      1976
 151        24      2000
 152        20      2020
 153        16      2036
 154        16      2052
 155        14      2066
 156        14      2080
 157        21      2101
 158        27      2128
 159        30      2158
 160        30      2188
 161        27      2215
 162        22      2237
 163        17      2254
 164        16      2270
 165        15      2285
 166        16      2301
 167        15      2316
 168        16      2332
 169        18      2350
 170        13      2363
 171        12      2375
 172        15      2390
 173        15      2405
 174        17      2422
 175        16      2438
 176        11      2449
 177         9      2458
 178        10      2468
 179        10      2478
 180        11      2489
 181        11      2500
 182        13      2513
 183        13      2526
 184        11      2537
 185         9      2546
 186         7      2553
 187         8      2561
 188         8      2569
 189         6      2575
 190         3      2578
 191         2      2580
 192         2      2582
 193         1      2583
 194         2      2585
 195         3      2588
 196         5      2593
 197         7      2600
 198         7      2607
 199         5      2612
 200         4      2616
 201         3      2619
 202         1      2620
 203         2      2622
 204         2      2624
 205         1      2625
 206         3      2628
 207         4      2632
 208         6      2638
 209         8      2646
 210         6      2652
 211         3      2655
 212         1      2656
 213         1      2657
 214         1      2658
 215         1      2659
 216         1      2660
 217         1      2661
 218         2      2663
 219         1      2664

2. Tiles of the same shape and orientation are treated as identical.
   d     count     total
   0         1         1
   1         2         3
   2         2         5
   3         3         8
   4         4        12
   5         6        18
   6         5        23
   7         4        27
   8         4        31
   9         5        36
  10         4        40
  11         3        43
  12         3        46
  13         1        47
  14         1        48
  15         2        50
  16         3        53
  17         3        56
  18         3        59
  19         4        63
  20         5        68
  21         5        73
  22         5        78
  23         5        83
  24         4        87
  25         2        89
  26         1        90
  27         2        92
  28         3        95
  29         3        98
  30         2       100
  31         1       101
  32         2       103
  33         4       107
  34         5       112
  35         4       116
  36         4       120
  37         5       125
  38         8       133
  39         9       142
  40         7       149
  41         9       158
  42        12       170
  43        16       186
  44        15       201
  45        13       214
  46        14       228
  47        15       243
  48        13       256
  49         9       265
  50        11       276
  51        14       290
  52        14       304
  53        16       320
  54        14       334
  55        14       348
  56        12       360
  57        10       370
  58        12       382
  59        15       397
  60        19       416
  61        18       434
  62        14       448
  63        15       463
  64        16       479
  65        15       494
  66        14       508
  67        13       521
  68        14       535
  69        13       548
  70        14       562
  71        14       576
  72        11       587
  73        12       599
  74        15       614
  75        15       629
  76        17       646
  77        16       662
  78        11       673
  79         9       682
  80        10       692
  81        10       702
  82        11       713
  83        11       724
  84        13       737
  85        13       750
  86        11       761
  87         9       770
  88         7       777
  89         8       785
  90         8       793
  91         6       799
  92         3       802
  93         2       804
  94         2       806
  95         1       807
  96         2       809
  97         3       812
  98         5       817
  99         7       824
 100         7       831
 101         5       836
 102         4       840
 103         3       843
 104         1       844
 105         2       846
 106         2       848
 107         1       849
 108         3       852
 109         4       856
 110         6       862
 111         8       870
 112         6       876
 113         3       879
 114         1       880
 115         1       881
 116         1       882
 117         1       883
 118         1       884
 119         1       885
 120         2       887
 121         1       888
```



There are very many trivial loops in various combinations. I have not searched for all loops yet, though.

*Edit 4:* I've finally come up with the non-trivial loop:

This one applies to the variant with unmarked tiles and takes 135 moves to return to essentially the same shape, allowing to slide one tile per move in one direction any number of units.


As for claim in the article, there are actually harder puzzles than Quzzle, so Jim Lewis has not found the most difficult 4x5 puzzle even under his definition of "simplicity". Or maybe his goal was not just longest optimal solution.

- stannic


----------

