Home »

Number of canonical move sequences for nxnxn Rubik's cube in h-w metric

Submitted by kociemba on Sun, 11/20/2011 - 17:22.
In h-w metric, a move of the nxnxn cube is a 90 or 180 degree turn of a face together with 0..n-2 adjacent slices. When counting the canonical move sequences the commutativity of the moves on one axis has to be taken into account. The number of canonical move sequences can be computed quite elegantly using matrices

With
m[n_]:=Table[If[i>j,9,6],{i,1,n-1},{j,1,n-1}]
v[n_]:=Table[9,{i,1,n-1}]

the number of canonical sequences is given by

count[n_, k_] := Total[MatrixPower[m[n], k - 1].v[n]]

If we know the n-1 eigenvalues v_0, v_1... v_(n-2) of this matrix we can write count[n,k] as

count[n,k] = c_0*v_0^k + c_1*v_1^k + ....c_(n-2)*v_(n-2)^k with some constants c_0,....c_(n-2)

Fortunately the characteristic polynomial can be solved in a closed form and we get

ev[n_,k_]:=3/((3/2)^(1/(n-1))Exp[2*I*Pi*k/(n-1)]-1) with k= 0..n-2

ev[n,0] = 3/((3/2)^(1/(n-1))-1) has the biggest absolute value and an analysis shows that for n>2

Abs[ev[n,k]]< 0.08*Abs[ev[n,0]] for all k=1..n-2

So if we define countApprox[n,k]=c_0*ev[n,0]^k the relative error converges quickly to 0.
Determining the constants c_k is not obvious. I explicitly computed the values only up to n=6 solving some linear equation systems, the expressions get very complicated but at least for c_0 a very simple pattern emerged and we get a very simple and nice formula for countApprox[n,k]:

With the branching factor b:= ev[n,0] = 3/((3/2)^(1/(n-1))-1) we get

countApprox[n,k]= (3+b)/(6(n-1))b^k

Here some examples to show the quality of the approximation (values rounded): 

n=3  k          count                    countApprox
     1                        18                       18
     2                       243                      243
     3                      3240                     3240
     4                     43254                    43254
     5                    577368                   577369
     6                   7706988                  7706987
     7                 102876480                102876481
     8                1373243544               1373243542
     9               18330699168              18330699170
    10              244686773808             244686773805
    11             3266193870720            3266193870724
    12            43598688377184           43598688377179
    13           581975750199168          581975750199175
    14          7768485393179328         7768485393179319
    15        103697388221736960       103697388221736972
    16       1384201395738071424      1384201395738071408
    17      18476969736848122368     18476969736848122390
    18     246639261965462754048    246639261965462754018
    19    3292256598848819251200   3292256598848819251240
    20   43946585901564160587264  43946585901564160587210


n=4  k              count                    countApprox
     1                            27                            27             
     2                           567                           567
     3                         11745                         11745
     4                        243486                        243486
     5                       5047596                       5047594
     6                     104639202                     104639206
     7                    2169224064                    2169224058
     8                   44969120244                   44969120250
     9                  932232780756                  932232780754
    10                19325660646240                19325660646230
    11               400630794286320               400630794286353
    12              8305280542211544              8305280542211480
    13            172172698326166032            172172698326166120
    14           3569227782041873232           3569227782041873157
    15          73991910935646107280          73991910935646107253
    16        1533890022781504051296        1533890022781504051563
    17       31798321900822223870976       31798321900822223870315
    18      659195418635526138240672      659195418635526138241779
    19    13665456979314071796134784    13665456979314071796133482
    20   283291887616616103884455104   283291887616616103884455776


n=100  k          count                        countApprox
       1                              891                             903             
       2                           660231                          660286
       3                        482682321                       482664646
       4                     352824725286                    352824551095
       5                  257912294551956                 257912330788002
       6               188532147183012666              188532147681012452
       7            137815709007224518776           137815708929526538671
       8         100742339498179233419136        100742339496834952355085
       9       73641960311376889071476496      73641960311544422584163191
      10    53831768704330235876123007636   53831768704333732711768810851

The relative error for n=3, 4, 100 and k=10 is 1*10^-11, 5*10^-13 and 6*10^-14. With this approximation it is possible to find good lower bounds for God's algorithm in h-w metric. I will work this out later.

» 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.

Formula for number of move seqences

Submitted by kociemba on Wed, 11/23/2011 - 06:06.
I was able to derive a simple non recursive formula, which gives the exact number of canonical move sequences for all n: With

b[n_,j_]:=3/(-1+(3/2)^(1/(n-1))*E^((2*I*Pi*j)/(n-1))) we have

countHW[n_, k_] := Sum[((3 + b[n,j])/(6*n - 6))*b[n,j]^k, {j, 0, n - 2}]

» login or register to post comments

Generating Function

Submitted by kociemba on Sat, 12/10/2011 - 13:11.
The generating function for countHW[n,k] is

gf[x_]:= 3/(6-4(3x+1)^(n-1))- 1/2

The -1/2 is necessary to make the generating function work for k=0. I forgot to mention that countHW[n,k] breaks for k=0 because it gives 3/2 instead of 1.

» login or register to post comments

Lower bounds in h-w metric

Submitted by kociemba on Sat, 11/26/2011 - 20:25.
For the exact number of move sequences summed up to k moves we then have

sumcountHW[n_,k_]:=Sum[(3+b[n,j])/(6n-6) (b[n,j]^(k+1)-1)/(b[n,j]-1),{j,0,n-2}]-1/2

Using only the first term j=0 in this sum gives a very good approximation

sumcountHWApprox[n_,k_]:=Round[(3+b[n,0])/(6(n-1)) (b[n,0]^(k+1)-1)/(b[n,0]-1)]

The relative error can be shown for n>3 to be less than

n ((n((3/2)^(1/(n-1))-1))/6)^(k+1)

The relative error drops with increasing n and also with increasing k. For n=4 and k=35 it is for example less than 10^-36. Because Log[sumcountHW] is the value needed in the following computation, we can use Log[sumcountHWApprox] instead.
In the example we get for Log[sumcountHWApprox[4,35]] and Log[sumcountHW[4,35]]
106.43205802396354445476531936685416587169481303886 and
106.432058023963544454765319366854165871694687575082

Solving the equation sumcountHWApprox[n_,k_]>=pos[n] for k+1, where pos[n] is the number of nxnxn Rubik's cubes we get for the lower bound for God's number

GodLowerBoundHW[n_]:=Floor[(logPos[n]+Log[6(n-1) (b[n,0]-1)/(3+b[n,0])])/Log[b[n,0]]]

where

logPos[n_]:=Mod[n,2]Log[(24 2^10 12!)]+Quotient[n^2-2n,4]Log[24!] - 6 Quotient[(n-2)^2,4]Log[4!]+Log[ 7! 3^6 ] = Log[pos[n]] 

        n                         k+1               GodLowerBoundHW[n]
          10                     193.88...                      193
         100                   13414.56...                    13414
        1000                 1001447.90...                  1001447
       10000                79634546.62...                 79634546
      100000              6607115368.70...               6607115368
     1000000            564530721350.01...             564530721350
    10000000          49279152940420.89...           49279152940420
   100000000        4372292443702114.13...         4372292443702114
  1000000000      392926702938097379.66...       392926702938097379
 10000000000    35677612468942635132.52...     35677612468942635132
100000000000  3267170564064121565902.50...   3267170564064121565902
The values in the right column are exact because rounding errors using the Floor function only can happen when the number in the middle column is very close to an integer.

The simpler formula GodLowerBoundHWApprox[n_]:=Floor[(logPos[n])/Log[b[n,0]]]

can be shown to have only one of the results GodLowerBoundHW[n] or GodLowerBoundHW[n]-1, where the probability that it is GodLowerBoundHW[n]-1 goes to 1 for n->infinity.

For the limiting behavior we can omit all constant terms in logPos[n_] and subsitute the Quotient Function by a division and get

GodLowerBoundHWLimit[n_]:=((n^2-2n)/4Log[24!]-6 (n-2)^2/4Log[4!])/Log[b[n,0]]

The values given by GodLowerBoundHWLimit differ only by maximal 4 from any value in the right column given in the table above! We have Log[b[n,0]]= Log[n]+Log[3/Log[3/2]]+ O[1/n] and hence get

GodLowerBoundHWLimit[n_] is equal to
g[n_]:= n^2/Log[n] (Log[24!]/4 - 3 Log[4!]/2) asymptotically, or

g[n_]:= 1/4 Log[3246670537110000] n^2/Log[n]

g[n_] will asymptotically be equal to GodHW[n_] - the God's number for Rubik's nxnxn Cube - itself, iff the additional number of moves to solve the cubes in the "tail" of the distribution are of order less than O(n^2/Log[n]). I myself would not be surprised if we even had O(1) for this.

» login or register to post comments