Megaminx needs at least 45 moves
Submitted by Herbert Kociemba on Tue, 02/28/2012 - 17:56.
Surprisingly, nobody seems to have done anything else as a rough analysis of the number of moves to solve the Megaminx puzzle, especially no analysis which includes the commutativity of some moves. To do so, we use the concept of syllables, as it already is successfully applied to Rubik's cube. Here we define a syllable as a subsequence of moves which commute. Different to Rubik's cube, these moves do not lie on the same axis, but just on different faces of the Megaminx, which have no pieces in common.
Let's denote a(n) the number of generic move sequences of depth n, n>=3. To compute a(n+1) we
1. We append a single move which does not commute with with the last move of a(n). Then this move has to be on one of the 5 faces adjacent to the face which is used in the last move of a(n). Because there are 4 possible turns of this face, this gives 5*4*a(n) possibilities.
2. Or we append a two move syllable to a(n-1). Again, the first move may not commute with the last move of a(n-1), so again we have only five possible faces for this. The second move of the syllable must commute with the first one. If have counted right, there are 25 pairs of faces which have this property, and we have 4^2 possibilities for moves on each pair. This gives the term 25*4^2*a(n-1).
3. Or we append a three move syllable to a(n-2). Here I counted 15 triples and for each of the triples we have 4^3 possibilities. This gives 15*4^3*a(n-2).
There are no syllables of length 4 on Megaminx.
So we have
a(n+1)= 20a(n)+ 400a(n-1)+ 960a(n-2) (n>=3)
Because we can attach a syllable of length 1 to the identity position in 12 and not only in 5 ways, we must use a(0)=12/5, a(n)=0 for n<0, if we want to use the above recursion also for n<=2. We get:
length count 1 48 2 1920 3 59904 4 2012160 5 66048000 6 2183331840 7 72017510400 8 2377089024000 9 78444783206400 10 2588868083712000
It would be interesting to know, for what depth on the number of positions is less than the number of generic move seuqences above.
Megaminx has 1.01*10^68 positions. Using the above recursion we see, that the summed up numbers of move sequences for 44 moves is less than this number, while a(45)=3.64745*10^68. So we need at least 45 moves to solve any position.
The asymptotic branching factor for the number of generic sequences is 33.0019 . This is considerably better than the rough estimate 44 which you get under the simple assumption that two consecutive moves are not on the same face. p