# Dodecahedron (and other) God's Numbers



## MaximalMegaminx (Jul 14, 2022)

Kilominx and Megaminx God's Number searches are already pretty tight, at 18-34 and 48-194 respectively in terms of their lower and upper bounds verified, but I couldn't find much on other same-shaped puzzles such as Gigaminx or Teraminx, so using the same method as ones used for calculating lower bounds, I wanted to give them justice. (I should say, I'm using HTM and OBTM metrics)

The method, as similar to many before, is based on calculating the number of possible sequences up to length N, and trying to reduce possible duplicates. In this goal sequences are separated into groups, based on what they end, for example, if the two last moves didn't influence each other's pieces, and therefore can be approach from two angles, A B or B A, and because we count all sequences, every such case is repeated twice, and therefore we can half it to get the actual number.

With 3x3 as the simple example, we count sequences of length N and try to reduce any redundancies, in this case (and for the rest of this post) that will be the situation where two opposite faces (which don't have any pieces in common) are turned in succession, each such sequence will naturally have its twin where the order of doing them is reversed. Here's a clever way to counteract them. Divide all sequences into three groups, "0", "1", and "2". "1" is when the last move in a sequence influenced the move previous. "2" is when the last move in a sequence didn't influence the previous move, because they were on opposite sides (think L' and R2 f.x.). And "0" is the original state with no moves made yet. With that out of the way, the next part is to map out sequences of length N.

We start with 1 sequence of length 0, it's this: . Impressive, I know. Anyway, from this moment forward case "0" becomes useless and therefore it's 0 all the way down as we get to higher number of moves. At 1 move, "0"=0, "1"=18, "2"=0. "1"=18 because from a solved state there are 3 different valid turns on 6 faces, so 18. On 2 moves, it's "0"=0, "1"=216, "2"=27. For "1" that's because there are 12 moves to go from the 18 1-movers which end up as another "1" state, you can't go on the face you just turned, that's redundant, and you can't turn the opposite face because that's a "2" case, so you end up with the 4 neighboring faces to turn, in 3 different ways, therefore you multiply that 18 by 12 to get 216. As for "2", for each of those previous 18 "1" cases, you can go only on the opposite face to get a "2", 3 different rotations then gives you... 54, but here's the kicker of doing all this, since it counts *all* sequences, for every sequence like L' R2 there's also R2 L', meaning you get double actual cases because you approach it both ways, therefore we divide by 2 and get 27. There's only one more thing to do.

So what became obvious is that a "1" case can appear 18 times from a "0" case and 12 times from a "1" case itself, and that "2" case can appear 3 times out of "1" cases (divided by 2 to remove redundants), but where can you go from "2"? Well, both sides already last turned can't be moved, that'd just be a "2" case we already accounted for, so the only option is to pick one of the neighboring 4 faces, since they disrupt the previous move, the are "1" cases, multiply by rotations and you get 12, so here's the full map of what leads to what:
"0" -> 18 "1"
"1" -> 12 "1", 3 "2"
"2" -> 12 "1"
We reverse it to get
18 "0" + 12 "1" + 12 "2" -> next "1"s
3 "1" /2 -> next "2"s
And that's it, we get our iterative equations to calculate the number of 'unique' sequences of any length, starting at 0 moves where "0"=1, "1"=0, and "2"=0. And then for next ones "0"=0 and for "1" and "2" we follow the iterative equations. We sum up all the possible sequences up to some length N until it overreaches the actual number of combinations on a 3x3. In our case we can get to as long as 17-moves-long sequences before getting over the 43 quadrillion combinations, but because we counted every unique sequence of length 17, some still need more, and therefore we can set a lower bound at 18, which was in fact the best lower bound approximations until the discovery of the Superflip.

Now we can get to the actual minxes. A very similar method has been used by Kociemba on the Megaminx, but with more groups which I call "0", "1", "2n", "2o", and "3" ("2n" and "2o" are both with last 2 moves unrelated, but the difference is relative position of the faces, next to each other and opposite of each other respectively), doing the map you get:
"0" -> 48 "1"
"1" -> 20 "1", 20 "2n", 4 "2o"
"2n" -> 8 "1", 16 "2n", 8 "2o", 8 "3"
"2o" -> 40 "2n"
"3" -> 6 "2n", 6 "2o", 6 "3"
you then again reverse them to get iterative equations, divide the "2n", "2o", and "3" appropriately to cut the redundant sequences, and do the adding up until you get to the number of combinations, which leads to the lower bound of 48 moves, best so far.

That's all well and good, but I didn't see anyone try to tackle other dodecahedrons, beyond the Kilominx (which is actually way more difficult than what I'll be doing, so props to them). So here I am, I already calculated them and put them on the Wiki, but I wanted to create a valid reference too.

First, the Gigaminx, it has very similar groups, but there's something we need to account for, two moves on the same face of different thickness. The way I tackled with this is by making both turns the same in my eyes, but rather caring if there's 1 or 2 of them made there. (oh also someone might be asking why do I make them the same if a thick move influences the pieces on the thin move, well, I don't think that's a problem, all you need to do is to redefine that "influencing" is relative to the layer below). This made me come up with this naming scheme: "0", "1-o", "1-b", "2n-oo", "2n-bo", "2n-bb", "2o-oo", "2o-bo", "2o-bb", "3-ooo", "3-boo", "3-bbo", and "3-bbb", once again I'm using the same "0", "1", "2n", "2o", and "3" from megaminx, but the letters after the hyphen describe the faces and whether they had *o*ne or *b*oth layers turned. Definitions over, time to tediously map out what goes to what:
"0" -> 96 "1-o"
"1-o" -> 4 "1-b", 40 "1-o", 40 "2n-oo", 8 "2o-oo"
"1-b" -> 40 "1-o", 40 "2n-oo", 8 "2o-oo"
"2n-oo" -> 8 "2n-bo", 16 "1-o", 32 "2n-oo", 16 "2o-oo", 16 "3-ooo"
"2n-bo" -> 4 "2n-bb", 16 "1-o", 16 "2n-oo", 16 "2n-bo", 8 "2o-oo", 8 "2o-bo", 16 "3-boo"
"2n-bb" -> 16 "1-o", 32 "2n-bo", 16 "2o-bo", 16 "3-bbo"
"2o-oo" -> 8 "2o-bo", 80 "2n-oo"
"2o-bo" ->4 "2o-bb", 40 "2n-oo", 40 "2n-bo"
"2o-bb" -> 80 "2n-bo"
"3-ooo" -> 12 "3-boo", 24 "2n-oo", 24 "2o-oo", 24 "3-ooo"
"3-boo" -> 8 "3-bbo", 16 "2n-oo", 8 "2n-bo", 16 "2o-oo", 8 "2o-bo", 16 "3-boo", 8 "3-ooo"
"3-bbo" -> 4 "3-bbb", 16 "2n-bo", 8 "2n-oo", 16 "2o-bo", 8 "2o-oo", 16 "3-boo", 8 "3-bbo"
"3-bbb" -> 24 "2n-bo", 24 "2o-bo", 24 "3-bbo"
Oh btw again to account for redundant sequences after reversing them to get iterative functions you divide them by: 1, 1, 2, 2, 3, 4, 2, 3, 4, 3, 4, 5, and 6 respectively. But yeah, again following the same principle we reach a total sum of all unique sequences up to _151_ moves to be 1.11*10^263, just below the number of combinations of the Gigaminx at 3.64*10^263, meaning God's Number is at least *152*. The full calculation is performed on my spreadsheet here, together with the next one.

As for Teraminx, this time for three layers, it goes thusly:
"0" -> 144 "1-o"
"1-o" -> 8 "1-b", 60 "1-o", 60 "2n-oo", 12 "2o-oo"
"1-b" -> 4 "1-t", 60 "1-o", 60 "2n-bo", 12 "2o-bo"
"1-t" -> 60 "1-o", 60 "2n-to", 12 "2o-to"
"2n-oo" -> 16 "2n-bo", 24 "1-o", 48 "2n-oo", 24 "2o-oo", 24 "3-ooo"
"2n-bo" -> 4 "2n-to", 8 "2n-bb", 24 "1-o", 24 "2n-bo", 24 "2n-oo", 12 "2o-bo", 12 "2o-oo", 24 "3-boo"
"2n-bb" -> 8 "2n-tb", 24 "1-o", 48 "2n-bo", 24 "2o-bo", 24 "3-bbo"
"2n-to" -> 8 "2n-tb", 24 "1-o", 24 "2n-to", 24 "2n-oo", 12 "2o-to", 12 "2o-oo", 24 "3-too"
"2n-tb" -> 4 "2n-tt", 24 "1-o", 24 "2n-to", 24 "2n-bo", 12 "2o-to", 12 "2o-bo", 24 "3-tbo"
"2n-tt" -> 24 "1-o", 48 "2n-to", 24 "2o-to", 24 "3-tto"
"2o-oo" -> 16 "2o-bo", 120 "2n-oo"
"2o-bo" -> 4 "2o-to", 8 "2o-bb", 60 "2n-oo", 60 "2n-bo"
"2o-bb" -> 8 "2o-tb", 120 "2n-bo"
"2o-to" -> 8 "2o-tb", 60 "2n-oo", 60 "2n-to"
"2o-tb" -> 4 "2o-tt", 60 "2n-to", 60 "2n-bo"
"2o-tt" -> 120 "2n-to"
"3-ooo" -> 24 "3-boo", 36 "2n-oo", 36 "2o-oo", 36 "3-ooo"
"3-boo" -> 4 "3-too", 16 "3-bbo", 24 "2n-oo", 12 "2n-bo", 24 "2o-oo", 12 "2o-bo, 24 "3-boo", 12 "3-ooo"
"3-bbo" -> 8 "3-tbo", 8 "3-bbb", 24 "2n-bo", 12 "2n-oo", 24 "2o-bo", 12 "2o-oo", 24 "3-boo", 12 "3-bbo"
"3-bbb" -> 12 "3-tbb", 36 "2n-bo", 36 "2o-bo", 36 "3-bbo"
"3-too" -> 16 "3-tbo", 24 "2n-oo", 12 "2n-to", 24 "2o-oo", 12 "2o-to", 24 "3-too", 12 "3-ooo"
"3-tbo" -> 4 "3-tto", 8 "3-tbb", 12 "2n-to", 12 "2n-bo", 12 "2n-oo", 12 "2n-to", 12 "2n-bo", 12 "2n-oo", 12 "3-tbo", 12 "3-too", 12 "3-boo"
"3-tbb" -> 8 "3-ttb", 24 "2n-bo", 12 "2n-to", 24 "2o-bo", 12 "2o-to", 24 "3-tbo", 12 "3-bbo"
"3-tto" -> 8 "3-ttb", 24 "2n-to" 12 "2n-oo", 24 "2o-to", 12 "2o-oo", 24 "3-too", 12 "3-tto"
"3-ttb" -> 4 "3-ttt", 24 "2n-to", 12 "2n-bo", 24 "2o-to", 12 "2o-bo", 24 "3-tbo", 12 "3-tto"
"3-ttt" -> 36 "2n-to", 36 "2o-to", 36 "3-tto"
There, done. Yes, it was extremely tedious and done by-hand with a minx in hand. Now reverse them to get iterative formulas, and divide them appropriately (by 1, 1, 2, 3, 2, 3, 4, 4, 5, 6, 2, 3, 4, 4, 5, 6, 3, 4, 5, 6, 5, 6, 7, 7, 8, and 9 respectively), and do the same business until the sum of all the sequences up to length N is just at the number of combinations (1.15*10^573) of the Teraminx, which I of course already did on my spreadsheet. However I encountered a difficulty, as the size of the numbers overreached the maximum values on spreadsheets (Google Sheets and Excel alike), so I divided the number up at two point, as to not reduce too much detail from the numbers. At n=_298_, the full number of unique sequences up to n reached 5.63*10^572, below the number of combinations, therefore God's Number for Teraminx is at least *299*.

As for any further comments, I tried to do Pyraminx Crystal and thought I did it, but my result only worked if the puzzle had unmovable centers, which is not the case (however I got lower bound of 41 for anyone curious). I also did multiple Megaminx subsets to check their lower bounds and got: <F, R, U> at 25 moves, <L, U, R> at 27 moves, <F, R, U, L> at 29 moves, <L,F,R,bR> at 33 moves, <F,R,bR,bL,L,U> at 35 moves, <F,R,bR,bL,L> at 42 moves, and a weird one <D, dL, F, R, bR, bL> at 53 moves (the idea behind the last one is that it connects the most faces in a single continuous line with no others connected). Also Ben already checked <R, U> computationally and got a lower bound of 26 for anyone curious, meanwhile I got 21 with this method. Either way, going to the original 152 and 299, it's fairly certain this will be the best those puzzles get for the foreseeable future, due to limitations in computing power to do it any other way. So thank you for reading this, cya.

*EDIT1:*
Also my Pyraminx Crystal result is actually valid, as I wasn't actually doing it with centers implicitly defined, that's because I didn't use the number of combinations for a regular Megaminx, I used it divided by 60 (which is how many different orientations there are). And also the mapping is like this:
"0" -> 48 "1"
"1" -> 40 "1", 4 "2"
"2" -> 40 "1"
pretty simple, reverse it to get the iterative equations, make sure you divide it by 2 for the "2" equation to reduce redundants, and do the same process described in the OP, and you get *41* as the God's Number. If it helps the reader imagine we have a specific corner as a fixed point we solve around, and whenever any move might interfere with it, just do it like _thick._

You can then use the same logic for the Master Kilominx (the 4x4 of minxes) and Elite Kilominx (the 6x6 of minxes) which I have previously neglected because of that lack of centers that confused me as to what to do, but with my new understanding in mind, you can use exactly the same mappings as I did for Gigaminx and Teraminx respectively, but simply look for a lower number to reach (9.14*10^163 and 3.09*10^416), the results are then: *94* for the Master Kilominx, and *217* for Elite Kilominx.

*EDIT2:*
Figured out Pyraminx Crystal QTM (Quarter Turn Metric), the map is like this:
"0" -> 24 "1-o"
"1-o" -> 1 "1-b", 20 "1-o", 2 "2-oo"
"1-b" -> 20 "1-o", 2 "2-bo"
"2-oo" -> 2 "2-bo", 20 "1-o"
"2-bo" -> 1 "2-bb", 20 "1-o"
"2-bb" -> 20 "1-o"
Same process, blah blah blah, I won't repeat it forever, though one difference, this time you actually divide each by 1, 1, 1, 2, 2, 2 respectively, because this time the difference between "o" and "b" is that it's whether you make one or two turns on a face which is different from counting different layers, either way you get lower bound of *50* for Pyraminx Crystal using QTM.

*EDIT3+:*
I decided to use this post to bypass the waiting time and have all my work congregated somewhere as well, the main source of calculations is still found on the same google sheet of course. Now I found that the Face-Turning Octahedron has the God's Number of at least 20.


----------



## baseballjello67 (Jul 14, 2022)

That's a lot of writing and took me 10 minutes to read. R.I.P my brain.

But seriously, this is pretty cool.


----------



## MaximalMegaminx (Jul 14, 2022)

baseballjello67 said:


> That's a lot of writing and took me 10 minutes to read. R.I.P my brain.
> 
> But seriously, this is pretty cool.


yeah, it was overly long looking back at it, I really want to make sure the reader can follow what I'm doing, plus I wanted to explain the idea at first which took a half or more of the actual OP, going through the simple case of 3x3, presenting the idea of mapping last independent face turns, and calculating lower bound with it, then expanding to megaminx, and only then getting to the gist of it


----------

