# Decadecaflexagon and Group theory

#### Solve

##### Member
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:

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:

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

##### Banned

Last edited by a moderator:

#### Solve

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

#### qqwref

##### Member
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.

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.

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.

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

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

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

##### Member
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

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

#### Solve

##### Member
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

##### Member
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).

#### stannic

##### Member
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

Last edited:

#### Ickathu

##### Member
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

##### Member
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

##### Member
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

##### Member
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

Last edited:

#### Stefan

##### Member
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

##### Member
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).
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)).
Code:
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

Last edited: