• Welcome to the Speedsolving.com, home of the web's largest puzzle community!
    You are currently viewing our forum as a guest which gives you limited access to join discussions and access our other features.

    Registration is fast, simple and absolutely free so please, join our community of 40,000+ people from around the world today!

    If you are already a member, simply login to hide this message and begin participating in the community!

God's number is...

qqwref

Member
Joined
Dec 18, 2007
Messages
7,834
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
Oh yeah, I forgot about turns of the middle layer (since those aren't typically used while scrambling, which was the context iirc). I also didn't take amount (angle) into account.

Still, though, I have no idea what RtC was trying to say.
 
Joined
Dec 11, 2009
Messages
294
Code:
block turns (half-turns allowed)

moves  positions  cumulative   positions  cumulative pos.
                   positions     mod M         mod M

  0            1              1            1           1
  1           54             55            8           9
  2         2070           2125           87          96
  3        78649          80774         2052        2148
  4      2973289        3054063        66299       68447
  5    111963451      115017514      2376654     2445101
  6   4212573974     4327591488     88205742    90650843
  7 158458718464   162786309952   3305688035  3396338878

Thank you for doing this analysis. For the #of positions in column#1 - Is this NOT counting transpositions to the same position like U2 d2 R' = d2 U2 R', and equivalent positions reached by different turns +cube rotation like U D' = Ey?
 

cuBerBruce

Member
Joined
Oct 8, 2006
Messages
914
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
Visit Channel
Thank you for doing this analysis. For the #of positions in column#1 - Is this NOT counting transpositions to the same position like U2 d2 R' = d2 U2 R', and equivalent positions reached by different turns +cube rotation like U D' = Ey?

In each of your examples, the two sequences you give produce the same position, so are only counted as one position. I used a hash table to avoid counting duplicates such as these more than once. Whole cube rotations are not counted as moves, so Ey (or U D') is counted as a position 1 move from solved, since E is a single block turn. The cube can be rotated so DLB corner is at DLB to prevent counting "positions" differing by only the orientation of the cube as different positions.

I have done basically the same thing in six different metrics. See this thread on the Domain of the Cube forum.
 
Last edited:
Joined
Dec 11, 2009
Messages
294
In each of your examples, the two sequences you give produce the same position, so are only counted as one position. I used a hash table to avoid counting duplicates such as these more than once. Whole cube rotations are not counted as moves, so Ey (or U D') is counted as a position 1 move from solved, since E is a single block turn. The cube can be rotated so DLB corner is at DLB to prevent counting "positions" differing by only the orientation of the cube as different positions.

I have done basically the same thing in six different metrics. See this thread on the Domain of the Cube forum.

Can you do another table (same metric), that also shows the total number of positions that are possible (including duplicates) before ANY equivalency elimination? Showing the various branching factors would be nice too.
 

JonWhite

Member
Joined
Jan 25, 2011
Messages
61
hey guys, learn math. symmetry is NOT going to help reduce ANYTHING by a factor of a hundred million million million.

Still, though, I have no idea what RtC was trying to say.

He just needs a lesson on exponents.
 

Christopher Mowla

Premium Member
Joined
Sep 17, 2009
Messages
1,184
Location
Earth
YouTube
Visit Channel
hey guys, learn math. symmetry is NOT going to help reduce ANYTHING by a factor of a hundred million million million.
Did he say it was? He's asking pretty good questions that I think shows that he knows math pretty well. Nevertheless, his questions pertain to the scrambles which make the permutations, but this will not help very much considering what qqwref pointed out about the amount of hard-drive space needed for information on the permutations alone. At least RtC is contributing to this idea. Not all math problems have an obvious real world application, and, sometimes, somethings previously overlooked become foundational.
 

cuBerBruce

Member
Joined
Oct 8, 2006
Messages
914
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
Visit Channel
Can you do another table (same metric), that also shows the total number of positions that are possible (including duplicates) before ANY equivalency elimination? Showing the various branching factors would be nice too.

If you're asking for the number of unique possible sequences, that should be easy to calculate by hand. If you're asking for something else, I'm not sure what it is exactly what you want, or what the point of calculating it is. The "positions" column in my table gives positions from the set of 7.4*10^45 positions of the 4x4x4. The "positions mod M" is the number of symmetry-reduced positions. (M is the symbol Dan Hoey used for the symmetry group of the cube in the old cube-lovers archives.)
 
Joined
Dec 11, 2009
Messages
294
Instead, why don't we make scrambles using all combinations of slices.

My take on that, was that the number of combinations generated, would initially be much larger than the actual number of "distinct" 4x4x4 positions. Therefore, the reductions in positions from this larger set would also be larger- if all the equivalencies were eliminated. My intention was that "symmetrically equivalent" would be positions mod M, but also include any isomorphic positions reached by different move orders, or whole cube rotations.

Here is a table (approx.) that shows the jist of this:
Code:
	ALL SLICES	ALL SLICES	SYMM	           SYMM	          SAVINGS
	#of positions	Commulative	#of positions	Commulative        #of positions
0	1	             1	             1	         1	         0
1	72	             73	             8	         9	         64
2	4968	             5041	             87	         96	         4945
3	342792	             347833	   2052	         2148	         345685
4	23652648	             24000481       66299	         68477	         23932004
5	1632032712	1656033193	2376654           2445101	         1653588092
6	1.1261E+11 	1.1427E+11 	8.8206E+07 	9.0651E+07 	1.1418E+11 
7	7.7701E+12 	7.8844E+12 	3.3057E+09 	3.3963E+09 	7.8810E+12 
8	5.3614E+14 	5.4402E+14 	1.2396E+11 	1.2736E+11 	5.4389E+14 
9	3.6993E+16 	3.7538E+16 	4.6486E+12 	4.7760E+12 	3.7533E+16 
10	2.5526E+18 	2.5901E+18 	1.7432E+14 	1.7910E+14 	2.5899E+18 
11	1.7613E+20 	1.7872E+20 	6.5371E+15 	6.7162E+15 	1.7871E+20 
12	1.2153E+22 	1.2331E+22 	2.4514E+17 	2.5186E+17 	1.2331E+22 
13	8.3854E+23 	8.5087E+23 	9.1928E+18 	9.4447E+18 	8.5086E+23 
14	5.7859E+25 	5.8710E+25 	3.4473E+20 	3.5418E+20 	5.8709E+25 
15	3.9923E+27 	4.0510E+27 	1.2927E+22 	1.3282E+22 	4.0510E+27 
16	2.7547E+29 	2.7952E+29 	4.8478E+23 	4.9806E+23 	2.7952E+29 
17	1.9007E+31 	1.9287E+31 	1.8179E+25 	1.8677E+25 	1.9287E+31 
18	1.3115E+33 	1.3308E+33 	6.8172E+26 	7.0040E+26 	1.3308E+33 
19	9.0493E+34 	9.1824E+34 	2.5564E+28 	2.6265E+28 	9.1824E+34 
20	6.2440E+36 	6.3359E+36 	9.5867E+29 	9.8493E+29 	6.3359E+36 
21	4.3084E+38 	4.3717E+38 	3.5950E+31 	3.6935E+31 	4.3717E+38 
22	2.9728E+40 	3.0165E+40 	1.3481E+33 	1.3851E+33 	3.0165E+40 
23	2.0512E+42 	2.0814E+42 	5.0555E+34 	5.1940E+34 	2.0814E+42 
24	1.4153E+44 	1.4362E+44 	1.8958E+36 	1.9477E+36 	1.4362E+44 
25	9.7659E+45 	9.9095E+45 	7.1093E+37 	7.3040E+37 	9.9095E+45 
26	6.7384E+47 	6.8375E+47 	2.6660E+39 	2.7390E+39 	6.8375E+47 
27	4.6495E+49 	4.7179E+49 	9.9974E+40 	1.0271E+41 	4.7179E+49 
28	3.2082E+51 	3.2554E+51 	3.7490E+42 	3.8517E+42 	3.2554E+51 
29	2.2136E+53 	2.2462E+53 	1.4059E+44 	1.4444E+44 	2.2462E+53 
30	1.5274E+55 	1.5499E+55 	5.2721E+45 	5.4165E+45 	1.5499E+55
How do you think I overestimated? If you think you can get a factor of 10^20 or more using symmetry, please, let me know how.

pfffh. As the table shows (lol), there would be a bulk savings of approx. 1.5*10^55 positions by turn 30 - if all of the symmetrically equivalent positions are eliminated. This is (lol) not surprisingly > than a billion times more than the total number of distinct positions for 4x4x4 ~ 7.4*10^45. But viewing symmetry as limited to mod M, within the already determined to be "distinct positions", then those additional reductions will only be ~/48.

hey guys, learn math. symmetry is NOT going to help reduce ANYTHING by a factor of a hundred million million million.

He just needs a lesson on exponents.

If I have to teach you a lesson a hundred million million million times, will you become my exponent?
 

qqwref

Member
Joined
Dec 18, 2007
Messages
7,834
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
As the table shows (lol), there would be a bulk savings of approx. 1.5*10^55 positions by turn 30 - if all of the symmetrically equivalent positions are eliminated.
Uh, what? The concept of "bulk savings" is useless here, because (a) I think you're only saving moves because you massively overcount in the "all" column, (b) subtracting two very large numbers tells us nothing because what's important here is the quotient, and (c) my point was that, at the very least, you still need to store a yes/no for each possible position to see which ones have been seen so far, and that would be technologically impossible to store, even with a factor-of-48ish reduction. Canceling moves in scrambles does not fix this problem.

I don't really understand why you're being so aggressive with your posts. It seems as if whenever you have an idea, even if it's completely wrong and you haven't explained it in enough detail for anyone to follow, you act like everyone else is stupid for having any questions or complaints about it. You're not going to win respect by attacking people without reason, you know.
 

peppermill

Member
Joined
Aug 18, 2011
Messages
2
i'm a new member hi everyone, my question is really simple, if you did work out how to do every scrambled cube in twenty moves or less and could show everyone how this is done and why you dont need more than 20 moves everytime, if you could show scrambled positions that by sight indicate you could pure solve it in 19, 18,17,16 and below would you not just kill the enigma of the rubiks cube, and i'm talking 4x 4's upwards to infinitum sized cubes, what would happen to the mystery of the cube? is it worth having knowing gods algorithym?
 

riffz

Member
Joined
Oct 3, 2008
Messages
2,068
Location
Toronto (Canada)
WCA
2009HOLT01
YouTube
Visit Channel
i'm a new member hi everyone, my question is really simple, if you did work out how to do every scrambled cube in twenty moves or less and could show everyone how this is done and why you dont need more than 20 moves everytime, if you could show scrambled positions that by sight indicate you could pure solve it in 19, 18,17,16 and below would you not just kill the enigma of the rubiks cube, and i'm talking 4x 4's upwards to infinitum sized cubes, what would happen to the mystery of the cube? is it worth having knowing gods algorithym?

Just because we know the maximum number of moves necessary to solve any scrambled cube doesn't mean we can find the optimal solutions by hand.
 

cuBerBruce

Member
Joined
Oct 8, 2006
Messages
914
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
Visit Channel
I note that knowing God's number does not imply knowing God's algorithm. Simply solving every position in 20 moves or less is not God's algorithm. (I'm not saying anyone explicitly was claiming this.) God's algorithm means knowing how to solve every position optimally, and a very miniscule percentage actually require 20 moves.

I note although we know God's number for 3x3x3 (for face turns), we are still a long way from even knowing the distance distribution of God's algorithm. We only know the distribution up to 15 moves, and that set only accounts for less than 1/400 of all positions.

When considering even larger cubes, the number of positions grows at a rather astronomical rate. There is really no forseeable way of getting God's algorithm for 4x4x4 without extreme advances in computing technology (or some as yet undiscovered mathematical insight is found to simplify the problem). Although we may be able to determine fairly good estimates for God's number for larger cubes, I would say it's questionable if we'll ever have a number proved for 4x4x4 and larger.
 

Christopher Mowla

Premium Member
Joined
Sep 17, 2009
Messages
1,184
Location
Earth
YouTube
Visit Channel
Of course I cannot prove this, but I am pretty sure that God's number for the nxnxn cube is

C(n)*n^2/Log(n) with

C(n)->0.25Log(24!)-1.5Log(4!) for n->Infinity
Maybe it's a coincidence, but when I looked at my derivative formula a second time (from this post), I noticed something interesting.

You're saying that \( C\left( n \right)=\frac{1}{4}\ln \left( 24! \right)-\frac{3}{2}\ln \left( 4! \right)=\ln \left( \frac{24!^{1/4}}{4!^{3/2}} \right) \).

The only two non constant factors in the derivative formula besides the natural log factor happen to be: \( \frac{24!^{\left( 1/4 \right)\left( n+1 \right)\left( n-3 \right)}}{4!^{\left( 3/2 \right)\left( n-1 \right)\left( n-3 \right)}} \).

So \( \ln \left( \frac{24!^{\frac{1}{4}\left( n+1 \right)\left( n-3 \right)}}{4!^{\frac{3}{2}\left( n-1 \right)\left( n-3 \right)}} \right)\frac{n^{2}}{\ln \left( n \right)} \)

The command "Log[24!^((1/4) (Range[100] + 1) (Range[100] - 3))/4!^((3/2) (Range[100] - 1) (Range[100] - 3))] (Range[100]^2/Log[Range[100]])//N" in Mathematica yields (values for n=1 to n=100):

{ComplexInfinity , -209.603 , 0. , 625.318 , 1960.58 , 4342.15 , 8155.32 , 13833.9 , 21859. , 32758. , 47103.6 , 65513. , 88647.1 , 117210. , 151947. , 193647. , 243139. , 301293. , 369021. , 447272. , 537038. , 639348. , 755271. , 885915. , 1.03243*10^6 , 1.19599*10^6 , 1.37782*10^6 , 1.57919*10^6 , 1.80138*10^6 , 2.04574*10^6 , 2.31364*10^6 , 2.60648*10^6 , 2.9257*10^6 , 3.2728*10^6 , 3.64929*10^6 , 4.05671*10^6 , 4.49667*10^6 , 4.97078*10^6 , 5.48071*10^6 , 6.02816*10^6 , 6.61484*10^6 , 7.24254*10^6 , 7.91306*10^6 , 8.62822*10^6 , 9.38991*10^6 , 1.02*10^7 , 1.10605*10^7 , 1.19733*10^7 , 1.29405*10^7 , 1.39641*10^7 , 1.50462*10^7 , 1.61888*10^7 , 1.73942*10^7 , 1.86645*10^7 , 2.00019*10^7 , 2.14087*10^7 , 2.28872*10^7 , 2.44396*10^7 , 2.60684*10^7 , 2.77758*10^7 , 2.95644*10^7 , 3.14365*10^7 , 3.33947*10^7 , 3.54414*10^7 , 3.75792*10^7 , 3.98107*10^7 , 4.21384*10^7 , 4.45652*10^7 , 4.70935*10^7 , 4.97261*10^7 , 5.24658*10^7 , 5.53154*10^7 , 5.82775*10^7 , 6.13552*10^7 , 6.45512*10^7 , 6.78685*10^7 , 7.13099*10^7 , 7.48785*10^7 , 7.85773*10^7 , 8.24093*10^7 , 8.63775*10^7 , 9.0485*10^7 , 9.4735*10^7 , 9.91307*10^7 , 1.03675*10^8 , 1.08372*10^8 , 1.13223*10^8 , 1.18234*10^8 , 1.23406*10^8 , 1.28744*10^8 , 1.3425*10^8 , 1.39928*10^8 , 1.45781*10^8 , 1.51814*10^8 , 1.58029*10^8 , 1.6443*10^8 , 1.7102*10^8 , 1.77804*10^8 , 1.84784*10^8 , 1.91965*10^8}

(For those who may be wondering, "complex infinity" in Mathematica just means dividing by zero).

If we start with the value for n=4, that is, 625.318 and divide it by the value for n=3 (well, in this case it would be 20 and not zero), we get 31.2659. Likewise, if we continue interating with 1960.58/31.2659 =62.70665485 for the 5x5x5, and so on, we get:
[FONT=&quot]
Code:
n=2:   11
n=3:   20
n=4:   31.2659
n=5:   62.70665485
n=6:   69.24544149
n=7:   117.7741065
n=8:   117.4613029
n=9:   186.0953306
n=10: 176.0280599
n=11: 267.5914284
n=12: 244.8247329
n=13: 362.0839241
n=14: 323.7094834
n=15: 469.3931065
n=16: 412.547601
n=17: 589.3598688
n=18: 511.2207599
n=19: 721.8427516
n=20: 619.6252563
n=21: 866.7141865
n=22: 737.6687839
n=23: 1 023.861951
n=24: 865.2680173
n=25: 1 193.190987
n=26: 1 002.345821
n=27: 1 374.595445
n=28: 1 148.839832
n=29: 1 567.999255
n=30: 1 304.681743
n=31: 1 773.336688
n=32: 1 469.816769
n=33: 1 990.520222
n=34: 1 644.193294
n=35: 2 219.501815
n=36: 1 827.75701
n=37: 2 460.212149
n=38: 2 020.468033
n=39: 2 712.594266
n=40: 2 222.285904
n=41: 2 976.592701
n=42: 2 433.164604
n=43: 3 252.167974
n=44: 2 653.067145
n=45: 3 539.265871
n=46: 2 881.953595
n=47: 3 837.848056
n=48: 3 119.795215
n=49: 4 147.868404
n=50: 3 366.572571
n=51: 4 469.29323
n=52: 3 622.228207
n=53: 4 802.071821
n=54: 3 886.75986
n=55: 5 146.163056
n=56: 4 160.128579
n=57: 5 501.560725
n=58: 4 442.303052
n=59: 5 868.217385
n=60: 4 733.260235
n=61: 6 246.09646
n=62: 5 032.839342
n=63: 6 635.359829
n=64: 5 341.292848
n=65: 7 035.600007
n=66: 5 658.465512
n=67: 7 446.96595
n=68: 5 984.343194
n=69: 7 869.451746
n=70: 6 318.8773
n=71: 8 303.025603
n=72: 6 662.077494
n=73: 8 747.646669
n=74: 7 013.909263
n=75: 9 203.312673
n=76: 7 374.355562
n=77: 9 669.983959
n=78: 7 743.394437
n=79: 10 147.65561
n=80: 8 121.018605
n=81: 10 636.28889
n=82: 8 507.196532
n=83: 11 135.86593
n=84: 8 901.930092
n=85: 11 646.35073
n=86: 9 305.232389
n=87: 12 167.67032
n=88: 9 717.06143
n=89: 12 699.93
n=90: 10 137.37871
n=91: 13 243.06844
n=92: 10 566.13131
n=93: 13 797.00818
n=94: 11 003.40002
n=95: 14 361.83359
n=96: 11 449.0952
n=97: 14 937.42493
n=98: 11 903.25648
n=99: 15 523.81908
n=100: 12 365.83595
[/FONT]By these "results," God's number would appear to be higher in odd cubes. Specifically, God's number for n=7 and n=8 would be nearly identical, but then the values for odd cubes surpasses that of the even cubes henceforth.

Do these results seem to be reasonable? I can tell that for n=100, the result here is less than the approximation of the lowerbound you posted by about 1000.
 
Last edited:

qqwref

Member
Joined
Dec 18, 2007
Messages
7,834
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
Do these results seem to be reasonable?
Not really - why would God's number be higher for, say, a 95x95x95 cube than a 96x96x96 cube? Especially considering the lower one can be simulated on the higher one?

God's Number is 20...but the FMC WR is 22, proving that humans aren't perfect.
The two numbers are unrelated; FMC scrambles rarely have an optimal solution of 20 moves. (And being Christian has nothing to do with people not being perfect. Simply put, nobody could expect someone to find an optimal solution to a random scramble in an hour when a computer requires so much processing power to do it!)
 
Top