Dodecahedron (and other) God's Numbers

[MaximalMegaminx]

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 one or both 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+:
Master Kilominx's number of 94 was wrong, it's 95. I double-checked after 3 years. It was nothing more than a manual error.

 

[baseballjello67]

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]

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

 

[Herbert Kociemba]

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.

I just wrote a general framework in Mathematica which generates the number of "canonical sequences" for any arbitrary undirected graph. For Gigaminx the graph has 24 vertices (one for each face or slice) and 120 edges and can be easily derived from the graph for the Megaminx which is the same as the vertex-edge graph of the icosahedron (which is the dual of the dodecahedron). The number of possible turns of each face/vertex has to be the same for each face/vertex in the framework and it is 4 for *minx puzzles.
I checked my computations for the Megaminx I did here before and the results match perfectly. For Gigaminx there is also a is a linear reccurence relation which allows to compute the number of canonical sequences of arbitrary length in a "relative" simple way:

mmx[0]=1;mmx[1]=96;mmx[2]=6336;mmx[3]=372736;mmx[4]=21037056;mmx[5]=1168097280;mmx[6]=64426639360;
mmx[n_]:= mmx[n]= 72*mmx[n-1] - 816*mmx[n-2] - 6400*mmx[n-3 ]- 19200*mmx[n-4] - 30720*mmx[n-5] - 20480*mmx[n-6]

If you sum up the first 151 terms with Sum[mmx[n], {n, 0, 151}] you get exactly

111026643104289634539950090374653124677929116219003169901032706559568542711409411180895048718483139272297695465583952863631201683827701595586859002336282851327194207622832295941808252752293012783447753294100991344145915061110652997812102919669501945340395538549025

canonical sequences which is about 1.11027*10^263 in coincidence with the results already given by MaximalMegaminx.

 

[MaximalMegaminx]

I just wrote a general framework in Mathematica which generates the number of "canonical sequences" for any arbitrary undirected graph. For Gigaminx the graph has 24 vertices (one for each face or slice) and 120 edges and can be easily derived from the graph for the Megaminx which is the same as the vertex-edge graph of the icosahedron (which is the dual of the dodecahedron). The number of possible turns of each face/vertex has to be the same for each face/vertex in the framework and it is 4 for *minx puzzles.

if I understand this correctly... you have the tool to compute, say, tuttminx's and futtminx's lower bound easier? it's notoriously hard to do using this method, I counted 104 different categories before I gave up cataloguing them by hand, which would've later involved checking through how they map, like your 4 recursive equations for Megaminx, and how about bigger regular mixes too? that'd be nice to know

 

[Herbert Kociemba]

if I understand this correctly... you have the tool to compute, say, tuttminx's and futtminx's lower bound easier?

Yes and no. The program has no symmetry reduction implemented, that's why already for Teraminx the program is too slow to give results within a reasonable time. Teraminx has 8708 different "categories", up to 9 moves may commutate with each other. Gigaminx has "only" 900 categories which of course is still much more than with your manual approach which exploits the symmetries.

 

[MaximalMegaminx]

Anyway, I just calculated the lower bound for God's number for the Tuttminx. For those unfamiliar Tuttminx is a puzzle similar in spirit to the Megaminx but which has 32 faces, 12 pentagonal and 20 hexagonal, its shape is called in math the truncated icosahedron and is the pattern visible on soccer balls. Tuttminx's pentagonal faces can turn freely at 72 degrees however its hexagonal faces only turn at 120 degree angles, to see why turning at 60 degrees would be problematic just find the tuttminx on Google Image.

Using the canonical sequence counting method, I was trying to enumerate all the 'categories' by hand, but I gave up when I catalogues the 135 first categories, the map for this puzzle is immense. Instead I wrote a program in C++ with my minimal coding abilities, that did this for me. It turns out the Tuttminx has a whopping 697 categories, including category 0, so 696 recursive equations in total, I'm really glad I stopped doing it by hand. After they were catalogued, I then wrote another piece of code that mapped out how they all relate to each other, getting the 696 recursive equations I was talking about. I plugged them in to a spreadsheet and did the thing, the lower bound is... 151 moves. Yay. That's assuming Wikipedia's number of combinations of 1.23*10^204 is accurate. I'll share the code if anybody asks.

Some funfacts, all 12 pentagonal faces are independent from each other, up to 8 out of the 20 hexagonal faces can be independent from each other. A grand total of 81 categories are with just pentagonal faces used, 79 with just hexagonal faces, and 536 with a mix of both. I named each case ApBhC where A represented the number of used pentagonal faces, B the hexagonal faces, and C and the index of all the different patterns they make to be counted as separate categories, by far the largest of them is 2p3hX which has 45 variants (categories).

 

[MaximalMegaminx]

For Gigaminx there is also a is a linear reccurence relation which allows to compute the number of canonical sequences of arbitrary length in a "relative" simple way:

mmx[0]=1;mmx[1]=96;mmx[2]=6336;mmx[3]=372736;mmx[4]=21037056;mmx[5]=1168097280;mmx[6]=64426639360;
mmx[n_]:= mmx[n]= 72*mmx[n-1] - 816*mmx[n-2] - 6400*mmx[n-3 ]- 19200*mmx[n-4] - 30720*mmx[n-5] - 20480*mmx[n-6]

How do you calculate the recurrence relation? that result for the Megaminx seemed like magic, I get the result for 3x3 (f(n)=12*f(n-1)+18*f(n-2) for n>=3)and the big cubes (f_m(n) = sigma m-1 p=1 (m-1)!/(p!(m-1-p)!)*2*3^p*f(n-p) for mxmxm and n<=m), it makes logical sense, but it was a little harder to understand the result for Megaminx for which you can't just backtrack by a constant amount to when you can get back to category 1, since you could just swap endlessly between categories 2o, 2a, and 3 (hopefully what I said was intelligible).

 

[JDCubing1]

Lord have mercy this is a very long post and idek what it means

 

[Herbert Kociemba]

How do you calculate the recurrence relation? that result for the Megaminx seemed like magic, I get the result for 3x3 (f(n)=12*f(n-1)+18*f(n-2) for n>=3)and the big cubes (f_m(n) = sigma m-1 p=1 (m-1)!/(p!(m-1-p)!)*2*3^p*f(n-p) for mxmxm and n<=m), it makes logical sense, but it was a little harder to understand the result for Megaminx for which you can't just backtrack by a constant amount to when you can get back to category 1, since you could just swap endlessly between categories 2o, 2a, and 3 (hopefully what I said was intelligible).

You can compute it online for example , for GigaMinx here.

The degree of the reccurence relation is the maximal number of commuting faces which is 3 for MegaMinx and 6 for GigaMinx. So such a relation exists and can be determined uniquely. But indeed I let the software do the job for me in this case. But you also can solve this manually of course - by solving a linear equation system. For example for the MegaMinx the number of canonical sequences starts

48, 1536, 43520, 1182720, 31641600, 841318400,...

Then you can put up this linear equation system where you just plug in these number

Solve[{{48, 1536, 43520},{1536, 43520, 1182720},{43520, 1182720, 31641600}}.{c1,c2,c3}=={1182720, 31641600, 841318400},{c1,c2,c3}]

with the solution {c1->-320,c2->-240,c3->36} so we have

-320*a(n) - 240*a(n+1) + 36*a(n+2)= a(n+3)

You see that you exactly need the the first 6 values of the sequence to uniquely determine c1, c2 and c3. For GigaMinx you need the first 12 values to solve the system with 6 variables.

 

[MaximalMegaminx]

So another insight. I decided to stop using Google Sheets spreadsheets for doing these tables, all of only have precision up to 15 digits and I wanted to be sure my numbers were actually correct, I don't think I had much to worry about, I would later compare the results for Megaminx and they were similar, but why not be extra careful, right? Instead I just learned a little Python because it can handle arbitrarily large numbers. I wrote a piece of C code, language I'm familiar with, that calculated the necessary iterative equations for any big minx and wrote Python code I could copy-paste to run it in Python. Kind of roundabout I'm assuming but again, I'm an amateur, I tried to use GMP library for C but I ran into some problems I didn't know how to fix.

A bit of math, for a big minx NxNxN, where M=floor(N/2), the number of categories is 1 + M + M(M+1) + M(M+1)(M+2)/6, or in shorter form M*(M+2)*(M+7)/6 + 1, that's including category 0. Excluding category 0, that's 4 for kilominx and megaminx, 12 for master kilominx and gigaminx, 25 for elite kilominx and teraminx, 44 for royal kilominx and petaminx, 70 for emperor kilominx and examinx, etc.

I've confirmed each lower bound using canonical sequence counting for the big minxes:
- 95 for Master Kilominx [4x4] (I originally wrote 94 in the post, that seems to have been a manual mistake)
- 152 for Gigaminx [5x5]
- 217 for Elite Kilominx [6x6]
- 299 for Teraminx [7x7]
as for the larger minxes I haven't done before:
- 383 for Royal Kilominx [8x8]
- 487 for Petaminx [9x9]
- 589 for Emperor Kilominx [10x10] (by Jacob Cubing, named after the Emperor Pyraminx equivalent in size)
- 715 for Examinx [11x11]
- 892 for 12x12 Kilominx (even minxes past Emperor Kilominx haven't been named or constructed yet)
- 982 for Zettaminx [13x13]
- 1119 for 14x14 Kilominx
- 1286 for Yottaminx [15x15]
- 1440 for 16x16 Kilominx
- 1628 for Ronnaminx [17x17] (one was produced by Diansheng, presented 7 months ago, called Ronnaminx by users, I know that follows modern SI prefixes but later names are kind of funny so I wasn't sure)
- 1799 for 18x18 Kilominx
- 2006 for Atlasminx [19x19] (yes, Atlasminx, quetta- was not a standardized SI prefix at the time of Atlasminx's creation by corenpuzzle 4 years ago, so it wasn't called the Quettaminx, before Ronnaminx's creation of course as well)
- 2193 for 20x20 Kilominx
- 2420 for Minx of Madness [21x21] (again, by corenpuzzle)
I also double-checked my result for Tuttminx of 151. So yeah that's it. Again if anyone wants to double check me too, I'll share my code if somebody asks.

 

[Herbert Kociemba]

A bit of math, for a big minx NxNxN, where M=floor(N/2), the number of categories is 1 + M + M(M+1) + M(M+1)(M+2)/6, or in shorter form M*(M+2)*(M+7)/6 + 1,

I agree with these numbers of cases. Took me some time to write a program which generate the corresponding equation systems, wonder how you manged to do this so fast.

My results for Teraminx gave for the coefficients for the linear recursion
{108, -1728, -25344, -161280, -645120, -1720320, -2949120, -2949120, -1310720}, which means

a(n)=108*a(n-1) + ... -1310720*a(n-9)

The biggest zero of the corresponding characteristic polynomial

0 = 1310720+2949120 x+2949120 x^2+1720320 x^3+645120 x^4+161280 x^5+25344 x^6+1728 x^7-108 x^8+x^9

gives the asymtotic growth factor for the number of canonical sequences and is about b=83.315908 .

This means that even b^n alone gives a fairly good approximation for the order of magnitude for the number of canonical sequences with n moves or less. The number of positions of Teraminx is about 1.1512973*10^573, which is more than b^298 but less than b^299. This confirms the God's number result you already gave above.

 

[MaximalMegaminx]

I agree with these numbers of cases. Took me some time to write a program which generate the corresponding equation systems, wonder how you manged to do this so fast.

My program creates a list of all the categories. For big minxes it’s not so bad. There’s still four categories from Megaminx, of 1, 2a, 2o, and 3, it’s just that now you also have to take how many layers were turned. So say for teraminx, category 3 where one face had 1 layer turned, second had 2, and the third had 2 layers turned. Call it category 3-1,2,2 if you want (what I called 3-obb in my original post from 2022).

I number each face on the dodecahedron from 1 to 12 and note the category by the number of rotated layers. So category 1-1 is 1,0,0,0,0,0,0,0,0,0,0,0, category 1-2 is 2,0,0,0,0,0,0,0,0,0,0,0, category 3-1,2,2 is 1,0,0,0,0,0,2,0,2,0,0,0, etc.

I then take each category at a time and apply an extra turn on every face, unless there are no more layers yet unturned on that face then I skip it. I check which adjacent faces it cancels, and see what category it becomes.

So say it’s category 3-1,2,2, and I’m testing the turn of the 2nd face, the 2nd face is adjacent to the 1st and 7th face (along the others that don’t matter here), so it cancels them

The category becomes 0,1,0,0,0,0,0,0,2,0,0,0. When you check this through all the symmetries (rotations and their mirrors), you find this is the same as 1,0,0,0,0,0,2,0,0,0,0,0 on our list, which is category 2a-1,2.

Then you note this in a 2D array map. That with this face turn, category 3-1,2,2 becomes 2a-1,2… in 12 different ways, so you add 12 (3 layers to turn on 2nd face, in 4 possible turns).

Once you go through every category and every face to turn, you have the complete map, which when you read it, gives you the iterative equations you need. I hope that made sense.

 

[Herbert Kociemba]

I think I did it in a similar way. For Gigaminx for example I used the 12 variables m1(1), m1(2), m2a(1,1), m2a(1,2), m2a(2,2), m2b(1,1), m2b(1,2), m2b(2,2), m3(1,1,1), m3(1,1,2), m3(1,2,2), m3(2,2,2).

 

[rokicki]

This is all very fascinating and I wish I had seen it earlier.

The twsearch program has this sort of computation built-in for general puzzles. For instance if I run

build/bin/twsearch -C teraminx.tws

I get

Found 901 canonical move states.
D 0 this 1 total 1
D 1 this 144 total 145 br 144
D 2 this 14400 total 14545 br 100
D 3 this 1.2864e+06 total 1.30094e+06 br 89.3333
D 4 this 1.10269e+08 total 1.1157e+08 br 85.7194
D 5 this 9.29751e+09 total 9.40908e+09 br 84.3163
D 6 this 7.78566e+11 total 7.87975e+11 br 83.7392
...
D 86 this 3.55771e+165 total 3.60093e+165 br 83.3159

I could (and probably should) make the program calculate and print the recurrence relation too.

My number of states is larger than yours; there is likely some equivalence that my algorithm isn't automatically picking up.

The code also supports the quarter-turn metric and arbitrary move subsets.

 

[MaximalMegaminx]

This is all very fascinating and I wish I had seen it earlier.My number of states is larger than yours; there is likely some equivalence that my algorithm isn't automatically picking up.

For the record, I'm using the number of positions as calculated by Christopher Mowla in 2014. Here in 2021 he shared a concise WolframAlpha equation for it for any big minx.