Home »

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

» login or register to post comments | previous forum topic | next forum topic

Comment viewing options

Select your preferred way to display the comments and click 'Save settings' to activate your changes.

My argumentation is flawed

Submitted by Herbert Kociemba on Sun, 08/21/2016 - 02:28.
As Tom Rokicki pointed out recently the syllable approach is to weak and inappropriate in the case of Megaminx. This refers to HTM and QTM. See the Speedsolving Forum for more details.
» login or register to post comments

Upper bound?

Submitted by IAssemble on Mon, 03/12/2012 - 02:45.
Hi Herbert,

Thanks for some interesting information.

Are you also working on an upper bound? The simple table-driven algorithm I use for my Megaminxer robot (http://www.youtube.com/watch?v=Ji7rF7KdmqE) has a worst case of 194 htm moves although this is almost certainly an extremely weak upper bound!

Regards
David Gilday
» login or register to post comments

Computation in qtm

Submitted by Herbert Kociemba on Thu, 03/01/2012 - 10:10.
In htm, a three move syllable always moves three "disjoint" faces, which have no pieces in common. In quarter turn metric, things are more complicated. Here a three move syllable is possible with any of the 15 disjoint triples (e.g. X+ Y- Z+, X+ means a 72 degree turn of face X, Y- a -72 degree turn of face Y etc.) or with any of the 25 disjoint pairs (e.g. X+ X+ Y-). On first sight it seems difficult to enumerate all the possibilities. How many three move syllables are for example on a disjoint face pair, how many 5 move syllables on a disjoint face triple?

On the face pair X Y, we have X+ X+ Y+, X+ X+ Y-, X- X- Y+, X- X- Y-, X+ Y+ Y+, X- Y+ Y+, X+ Y- Y-, X- Y- Y-, which is 8 syllables of length 3. I found an elegant way to find the numbers of syllables without writing them all down, which is quite error-prone.

For a face X, 2 positions can be reached within one move (X+,X-) and 2 within 2 moves (X+ X+, X- X-). This is represented by the polynomial (2x + 2x^2). To get the number of syllables for a face pair, we compute (2x + 2x^2)^2 = 4x^2 + 8x^3 + 4x^4 which tells us, that there are 4 syllables of length 2, 8 of length 3 and 4 of length 4.

(2x + 2x^2)^3= 8x^3 + 24x^4 + 24x^5 + 8x^6 tells us for example, that there are 24 syllables of length 5 on a disjoint face triple. Since syllables can happen on 15 disjoint face triples, 25 disjoint face pairs and on 5 single faces, we just evaluate 5(2x + 2x^2) + 25(2x + 2x^2)^2 + 15(2x + 2x^2)^3, which is

10 x + 110 x^2 + 320 x^3 + 460 x^4 + 360 x^5 + 120 x^6

which directly leads to the recurrence relation for qtm:

a(n+1):= 10a(n)+110a(n-1)+320a(n-2)+460a(n-3)+360a(n-4)+120a(n-5) (n>=6)

We must take a(0)=12/5 and a(n)=0 for n<0 to make the above recursion work correctly for n>=0. We get: 

length                 count
  1                       24
  2                      504
  3                     8448
  4                   148704
  5                  2589504
  6                 45196608             
  7                788467200
  8              13756445760
  9             240004483200
 10            4187303875200
Again, I would be interested to know up to what length the table also represents the true number of positions. For n=55, the summed up count exceeds 1.01*10^68, so Megaminx needs at least 55 moves in qtm.

The above methods allows to quickly find results for other "exotic" metrics. Suppose you allow only 72 degree turns in one direction. Then the corresponding polynomial is

5(x+x^2+x^3+x^4) + 25(x+x^2+x^3+x^4)^2 + 15(x+x^2+x^3+x^4)^3=
5x+30x^2+70x^3+125x^4+190 x^5+225x^6+230x^7+205x^8+150x^9+90x^10+45 x^11+15x^12

The recurrence relations then is
a(n+1)= 5a(n)+........+15a(n-11)

which gives a 70 move lower bound.

» login or register to post comments