From:

~~~ ~~~ Subject:

At various times, there have been discussions about what the maximum

distance from Start might be in God's algorithm. One argument is made

with respect to worst/best case branching factors. For example,

a simple calculation is that the first move has at most twelve

possibilities and that each subsequent move has eleven possibilities,

when dealing with Q-turns only. For Q-turns plus H-turns, the same

argument would be eighteen possibilities for the first move and seventeen

possibilities for each subsequent move.

My experience is that search trees tend to develop relatively

constant branching factors after some sort of variable startup.

I expect Rubik's cube to be no different. I just wonder if anyone

has calculated some number of levels for the full Rubik's cube,

enough levels for the hypothesized steady state branching factor

to be achieved. I have not done so, but if anyone has, it might

shed considerable light on the question of the maximum distance

from Start.

Subsets of the cube such as corners only and edges only have been

calculated. It is suggestive to examine branching factors for the

cases which have already been calculated. The question of "average

branching factor" is subject to interpretation because it is not

necessarily clear when the distribution has achieved its steady

state. I am including a number of tables giving branching factors

for the cases which have been calculated already. I will preface

the tables with the following comments:

1. The distributions for edges-only cubes have a variable branching

factor during a startup phase, then have a relatively constant

branching factor for several levels. and finally the distribution

has sort of a tail.2. The distributions for corners-only cubes have a variable branching

factor during a startup phase, and almost immediately the

distribution has a tail. The number of cases simply is not

large enough to support an extended constant branching factor

in the middle of the distribution. It's sort of like a very

short airplane flight where it is time to descend about the

time the ascent is completed.3. I would expect the distributions for a full cube to have an

even longer period with a constant branching factor than

the distributions for edges-only cubes because the number

of cases is so much larger. There should be plenty of time

for a plateau between the startup phase and any tail of the

distribution.4. There are an equal number of odd and even permutations. For

the cases where you restrict yourself to Q-turns, there are

therefore equal numbers of states an even distance from Start

and an odd distance from Start. Hence, the distribution tends

either to have two adjacent levels with approximately equal

numbers of states, or else tends to have one dominant level with

a level on each side of the dominant level with about half

the number of states in the dominant level.5. For the cases where you allow both Q-turns and H-turns, there

tends to be one dominant level which contains most of the

of the states.6. Those of you who followed all the traffic on this list in

December and January will recall that my work with God's

algorithm exploits symmetric conjugates in order to reduce

the size of the problem. It turns out that using conjugates

does not change the average branching factor once you get

past the startup portion of the distribution. This effect

can be a bit hard to see for corners-only cubes because the

steady state portion of the distribution is so short, but

the effect is very striking for edges-only cubes. I would

expect the effect to be very striking, as well, for the

case of the full cube.------------------------------------------------------------------>>2x2x2 Cube using Q-turns and H-turns

Distance Number of Branching Number of Branching Ratio of from Cubes Factor M Factor Cubes to Start Conjugates Conjugates0 1 1 1.00 1 9 9.00 2 2.00 4.50 2 54 6.00 5 2.50 10.80 3 321 5.94 19 3.80 16.89 4 1847 5.75 68 3.58 27.16 5 9992 5.41 271 3.99 36.87 6 50136 5.02 1148 4.24 43.67 7 227536 4.54 4915 4.28 46.29 8 870072 3.82 18364 3.74 47.38 9 1887748 2.17 39707 2.16 47.54 10 623800 0.33 13225 0.33 47.17 11 2644 0.00 77 0.01 34.34Total/Avg 3674160 ? 4.83 77802 ? 3.54 47.22------------------------------------------------------------------>>2x2x2 Cube using Q-turns

Distance Number of Branching Number of Branching Ratio of from Cubes Factor M Factor Cubes to Start Conjugates Conjugates0 1 1 1.00 1 6 6.00 1 1.00 6.00 2 27 4.50 3 3.00 9.00 3 120 4.44 6 2.00 20.00 4 534 4.45 17 2.83 31.41 5 2256 4.22 59 3.47 38.24 6 8969 3.98 217 3.68 41.33 7 33058 3.69 738 3.40 44.79 8 114149 3.45 2465 3.34 46.31 9 360508 3.16 7646 3.10 47.15 10 930588 2.58 19641 2.57 47.38 11 1350852 1.45 28475 1.45 47.44 12 782536 0.58 16547 0.58 47.29 13 90280 0.12 1976 0.12 45.69 14 276 0.00 10 0.01 27.60Total/Avg 3674160 ? 3.05 77802 ? 2.92 47.22------------------------------------------------------------------>>Corners of 3x3x3 Cube using Q-turns and H-turns

Distance Number of Branching Number of Branching Ratio of from Cubes Factor M Factor Cubes to Start Conjugates Conjugates0 1 1 1.00 1 18 18.00 2 2.00 9.00 2 243 13.50 9 4.50 27.00 3 2874 11.83 71 7.89 40.48 4 28000 9.74 637 8.97 43.96 5 205416 7.34 4449 6.98 46.17 6 1168516 5.69 24629 5.54 47.44 7 5402628 4.62 113049 4.59 47.79 8 20776176 3.85 433611 3.84 47.91 9 45391616 2.18 947208 2.18 47.92 10 15139616 0.33 316823 0.33 47.79 11 64736 0.00 1481 0.00 43.71Total/Avg 88179840 ? 4.74 1841970 ? 4.63 47.87------------------------------------------------------------------>>Corners of 3x3x3 Cube using Q-turns

0 1 1 1.00 1 12 12.00 1 1.00 12.00 2 114 9.50 5 5.00 22.80 3 924 8.11 24 4.80 38.50 4 6539 7.08 149 6.21 43.89 5 39528 6.04 850 5.70 46.50 6 199926 5.06 4257 5.01 46.96 7 806136 4.03 16937 3.98 47.60 8 2761740 3.43 57800 3.41 47.78 9 8656152 3.13 180639 3.13 47.92 10 22334112 2.58 466052 2.58 47.92 11 32420448 1.45 676790 1.45 47.90 12 18780864 0.58 392558 0.58 47.84 13 2166720 0.12 45744 0.12 47.37 14 6624 0.00 163 0.00 40.64Total/Avg 88179840 ? 4.48 1841970 ? 4.29 47.87------------------------------------------------------------------>>Edges of 3x3x3 Cube Without Centers using Q-turns and H-Turns

0 1 1 1.00 1 18 18.00 2 2.00 9.00 2 243 13.50 9 4.50 27.00 3 3240 13.33 75 8.33 43.20 4 42359 13.07 919 12.25 46.09 5 538034 12.70 11344 12.34 47.43 6 6666501 12.39 139325 12.28 47.85 7 79820832 11.97 1664347 11.95 47.96 8 888915100 11.14 18524022 11.13 47.99 9 8056929021 9.06 167864679 9.06 48.00 10 27958086888 3.47 582489607 3.47 48.00 11 3883792136 0.14 80930364 0.14 47.99 12 8827 0.00 314 0.00 28.11Total/Avg 40874803200 ? 12.26 851625008 ? 11.99 48.00------------------------------------------------------------------>>Edges of 3x3x3 Cube Without Centers Using Q-turns

0 1 1 1.00 1 12 12.00 1 1.00 12.00 2 114 9.50 5 5.00 22.80 3 1068 9.37 25 5.00 42.72 4 9759 9.14 215 8.60 45.39 5 88144 9.03 1860 8.65 47.39 6 786500 8.92 16481 8.86 47.72 7 6916192 8.79 144334 8.76 47.92 8 59623239 8.62 1242992 8.61 47.97 9 495496593 8.31 10324847 8.31 47.99 10 3695351994 7.46 76993295 7.46 48.00 11 17853871137 4.83 371975385 4.83 48.00 12 18367613703 1.03 382690120 1.03 48.00 13 395043663 0.02 8235392 0.02 47.97 14 1080 0.00 54 0.00 20.00 15 1 0.00 1 0.02 1.00Total/Avg 40874803200 ? 8.80 851625008 ? 8.63 48.00------------------------------------------------------------------

= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Robert G. Bryan (Jerry Bryan) (304) 293-5192 Associate Director, WVNET (304) 293-5540 fax 837 Chestnut Ridge Road BRYAN@WVNVM Morgantown, WV 26505 BRYAN@WVNVM.WVNET.EDU

If you don't have time to do it right today, what makes you think you are

going to have time to do it over again tomorrow?