# Optimal scramble length for N-minx dodecahedrons



## speedcubesite (Oct 27, 2020)

I'm working on adding "dodecaminx" puzzles to the speedcube site, and I need a function to determine the scramble depth of N-layered face turning dodecahedrons. For now, I'm just using the number of layers * 25. This works fine for smaller puzzles, but starts becoming insufficient as the number of layers increases.

If anyone wants to help me figure out a good formula, here is a link to my state modeling sandbox. I'm using a modified version of Pochmann notation to indicate how deep turns should be.
https://twister.speedcube.site/dodecaminx

To execute a scramble, open the dev tools and run

```
dodecaminx.scramble(x)
```
To resize the puzzle, run

```
dodecaminx.options.size = x
```


----------



## Devagio (Oct 27, 2020)

If I’m not mistaken, any upper bound on the gods number for that puzzle would count as sufficient. It wouldn’t be close to random state, but on huge puzzles I don’t think that’s necessary because the number of random moves to reach almost random state would be crazy high.

Upper bound on length of a commutator on these puzzles: 26 (just an estimate, the actual number is most likely much lower; 26 because 16-move pure comm plus 5-move setup)
Upper bound on number of pieces on N-minx: 12*(5/4)*N^2 (again, a crappy upper bound, you could calculate the exact number of you want, but it’s not necessary for our purposes).

Consider a method to solve an N-minx using comms on each piece. So, the upper bound of moves needed to solve an N-minx is
26*12*(5/4)*N^2 = 390N^2

Note that this upper bound holds no matter how large N is. So the gods number function scales slower than O(N^2)

Now, the cringe-worthy assumption:
Suppose we can model an upper bound as a quadratic aN^2 + bN + c
You say 25*N has been “working“ for N=1,2,3. (Alternatively we could use gods number estimates for these puzzles)
So for a=5, b=10, c=10, the whole thing should work.

Don’t exactly have a great justification for what I did at the end except it intuitively seems correct.

So here’s your function: 5N^2+10N+10, which gives reasonable lengths (~500) for even petaminx. 
Play around with the coefficients if you want; because a quadratic should work irrespective of my final assumption. 390N^2 works for sure, just not very practical.


----------



## qwr (Oct 27, 2020)

Devagio said:


> If I’m not mistaken, any upper bound on the gods number for that puzzle would count as sufficient. It wouldn’t be close to random state, but on huge puzzles I don’t think that’s necessary because the number of random moves to reach almost random state would be crazy high.
> 
> Upper bound on length of a commutator on these puzzles: 26 (just an estimate, the actual number is most likely much lower; 26 because 16-move pure comm plus 5-move setup)
> Upper bound on number of pieces on N-minx: 12*(5/4)*N^2 (again, a crappy upper bound, you could calculate the exact number of you want, but it’s not necessary for our purposes).
> ...



nah I think using a puzzle simulator, doing random moves, then checking for some metrics like average piece separation distance is better.


----------



## xyzzy (Oct 27, 2020)

What a good length for a scramble is depends a lot on what you're using the scramble for. Unless you absolutely need the scramble to be done via moves (e.g. a scramble generator so that a human or a robot can apply the moves to a physical puzzle), you could just do random-state scrambling instead, side-stepping the question of how many moves you need at all.



qwr said:


> nah I think using a puzzle simulator, doing random moves, then checking for some metrics like average piece separation distance is better.


If you don't do this carefully enough, you might end up biasing the average piece separation distance to having a distribution with a very tight peak, as opposed to something matching the distribution you'd get with random-state scrambles.

(See also: this thread and my reply there.)



Devagio said:


> So the gods number function scales slower than O(N^2)


Demaine et al's proof of GN being Θ(N^2 / log N) for the cubes should generalise to the minxes as well, I think. (Well, log N grows so slowly it might as well be constant anyway.)



Devagio said:


> If I’m not mistaken, any upper bound on the gods number for that puzzle would count as sufficient. It wouldn’t be close to random state, but on huge puzzles I don’t think that’s necessary because the number of random moves to reach almost random state would be crazy high.


There are actually situations where GN and the number of random moves needed are asymptotically different functions. (I don't know whether this is relevant to big cubes / big minxes; haven't thought much about that.)

Consider for example "scrambling" a deck of N cards where the only "move" you're allowed to make is swapping two adjacent cards. God's number is N(N−1)/2 = Θ(N^2) (this happens exactly when the deck is in reverse order), but the number of random moves you need to make in order for each card to be roughly equally likely to be anywhere in the deck is Θ(N^3 log(1/ε)). (0 < ε < 1 is the amount of relative error you can accept; the less error you want, the more random moves you need to make.)


----------



## abunickabhi (Oct 27, 2020)

I know the number is estimated for cubes, it is x^y and some factorials multiplied with it, No idea for megaminx and its variants. The computation must be different.


----------

