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

PatrickJameson

Premium Member
Joined
Apr 15, 2008
Messages
996
Location
Buffalo, NY
WCA
2007JAME01
YouTube
Visit Channel
I first saw this here a few hours ago. I found this quote silly:

"Suppose someone takes a solved 20x20x20 Rubik's cube and makes five moves - can you figure out [from that scrambled state] what those five moves were?" he asks. In other words, can you solve it in five moves? He suspects that you cannot, but has yet to prove it. "We don't know."
 

cmhardw

Premium Member
Joined
Apr 5, 2006
Messages
4,115
Location
Orlando, Florida
WCA
2003HARD01
YouTube
Visit Channel
The article is interesting yes, but I agree that the 20x20x20 cube quote was funny. 5 moves on a 20x20x20 would be very easy to do because there are so many layers. Sure it might take some thought to figure out, but quite easy.

15 moves on a 20x20x20? I'm guessing not so easy.
 

cuBerBruce

Member
Joined
Oct 8, 2006
Messages
914
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
Visit Channel
If I made the moves r2 u2 r2 u2 (where the lower case letters indicate moving the layer adjacent to the face layer), you would not be able to tell for sure what moves I made. (Although I would assume you would be able to solve it in 4 moves.)
 
Joined
Nov 29, 2008
Messages
214
You're ignoring the Θ and thus the constant factors. See here for a definition/explanation:

http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau_notations

It's not a formula where you can just plug in a number and get an output number. That's not what this is about. No, it tells you that God's numbers have a lower bound of (n^2/log n)*k1 and an upper bound of (n^2/log n)*k2, for some positive constants k1 and k2. This isn't particularly useful to get God's number for a specific n, this is all about the *general* case of nxnxn.

In the metric, where a move is defined by turning a single slice by 90 or 180 degrees there are surely less than (3n)^k different maneuvers of length k. So there are at most ((3n)^(k+1)-1)/(3n-1) maneuvers of length <=k (geometric summation formula). If you take Chris Hardwicks formula pos(n) for the number of positions of the nxnxn cube and solve for a k so that ((3n)^(k+1)-1)/(3n-1) >= pos(n) for large n you get something like

k is appoximately (0.25Log(24!)-1.5Log(4!))n^2/Log(n) for very large n (so you should not take n=3 here)

which is about 8.9291 N^2/Log[n].

A more carefull analysis does not change the situation, see

http://cubezzz.dyndns.org/drupal/?q=node/view/236 (h-s metric)

and

http://cubezzz.dyndns.org/drupal/?q=node/view/239

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
 
Last edited:

cmhardw

Premium Member
Joined
Apr 5, 2006
Messages
4,115
Location
Orlando, Florida
WCA
2003HARD01
YouTube
Visit Channel
In the metric, where a move is defined by turning a single slice by 90 or 180 degrees there are surely less than (3n)^k different maneuvers of length k. So there are at most ((3n)^(k+1)-1)/(3n-1) maneuvers of length <=k (geometric summation formula). If you take Chris Hardwicks formula pos(n) for the number of positions of the nxnxn cube and solve for a k so that ((3n)^(k+1)-1)/(3n-1) >= pos(n) for large n you get something like

k is appoximately (0.25Log(24!)-1.5Log(4!))n^2/Log(n) for very large n (so you should not take n=3 here)

which is about 8.9291 N^2/Log[n].

Wow, this is a very interesting analysis! I wouldn't have expected that:
((3n)^(k+1)-1)/(3n-1) >= pos(n)

would simplify so neatly to show that k is approximately:
"(0.25Log(24!)-1.5Log(4!))n^2/Log(n) for very large n"

Very cool!

A more carefull analysis does not change the situation, see

http://cubezzz.dyndns.org/drupal/?q=node/view/236 (h-s metric)

and

http://cubezzz.dyndns.org/drupal/?q=node/view/239

I don't know if this would affect your analysis, and it is very likely that I am speaking out of ignorance here, but in the second link you have a line that reads:
I implemented Chris Hardwicks formula for the number of positions of an nxnxn cube as
pos[n_]:=(24*2^10*12!)^(Mod[n,2])*7!*3^6*24!^Quotient[n^2-2n,4]/4!^(6 Quotient[(n-2)^2,4])

This formula will only calculate the number of positions to an even n x n x n cube, if I interpret your input correctly.

The reason I bring this up is that I am unclear whether you are using the floor function for the bolded parts or not (I don't know the program you're using, and what notation that program uses for the floor function). In my formula I intend those bolded parts to be arguments of the floor() function. If your notation is using that function, then disregard this portion of my post.

I am wondering in particular if this affects your results for this portion:
Searching the first n that countSumApprox[n]>=pos[n] gives for 2<=n<=30
{6,15,32,48,72,95,124,153,189,224,265,306,353,400,452,504,562,620,682,746,814,882,956,1029,1108,1187,1270,1354,1443}

If you're removing the floor function as an approximation, then you can disregard this concern. If the error introduced becomes negligible because you're taking the limit as n approaches infinity (for your final result), then disregard this concern.

If you would rather not use the floor function, then for cubes of odd size the bolded parts should become:
Quotient[n^2-2n,4]

would become:
Quotient[n^2-2n-3,4]

and
Quotient[(n-2)^2,4]

would become:
Quotient[(n-2)^2-1,4]

Apologies if I have misinterpreted something in your article, but I wanted to bring this up just in case.

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

Very neat! You should name this the Kociemba conjecture (if you haven't already ;) )
 
Joined
Nov 29, 2008
Messages
214
I don't know if this would affect your analysis, and it is very likely that I am speaking out of ignorance here, but in the second link you have a line that reads:


This formula will only calculate the number of positions to an even n x n x n cube, if I interpret your input correctly.

Sorry, I did not mention that it is Mathematica code. And Quotient[7, 4] is for example 1, so I think the code is correct.

What was wrong in my last message is the branching factor bf=(3n), it must be of course bf=(9n), but this does not change the result at all, because the Log[n] in the denominator originally results from Log[bf], but Log[9n]= Log[9]+Log[n] and Log[3n]=Log[3]+Log[n] behave both like Log[n] for large n. That's why a refined model which takes into account the commutativity between moves on the same axis etc. will give no better estimation unless the branching factor will not be of order Θ(n) any more - and the numerical data is totally against this.
 
Last edited:

Christopher Mowla

Premium Member
Joined
Sep 17, 2009
Messages
1,184
Location
Earth
YouTube
Visit Channel
I don't want to mess up this great thread, but I think I have something to say to help us pursue God's Algorithm for any size cube with very little thought compared to the current approach.

Instead of solving scrambles, why don't we instead just do the opposite?

Instead, why don't we make scrambles using all combinations of slices. We record the length of each scramble in all of the move metrics (so that we can obtain the diameter for every move metric) and assign each to the corresponding permutation they generate. The number of scrambles needed to be generated depends on whether or not all permutations have been reached with the given scramble length. (Obviously, the permutations which require the most moves (God's Algorithm) would be the group of permutations which are achieved last in the computation process, have the greatest length, and are equal in length).

The amount of scrambles is tremendous, but merely generating scrambles is much easier to compute than optimal solves. This way we don't really need to worry about creating an optimal solver for a specific cube size and then spending years and years of computation afterwords to solve all possible permutations optimally.

By computing the scrambles and recording which permutation they generate and how many moves they are, we can have all possible solutions to a given permutation that are no longer than God's Algorithm.

And of course, if we do not have the hard-drive space to hold all possible scrambles for all permutations of the nxnxn cube, we can just program the computer to keep track of the scramble lengths associated with each permutation.

In my opinion, it isn't necessary to keep the scrambles for the 8x8x8 cube and above because, if an algorithm works on the 7x7x7 for all combinations of orbits, it's translatable to all size cubes. (I have evidence to back this POV up, since I did create parity algorithms that are not directly transferable to all cube sizes, and I have observed algorithms that are unique to the 4x4x4, 5x5x5, big even cubes including the 4x4x4, big even cubes excluding the 4x4x4, big odd cubes including the 5x5x5, and big odd cubes excluding the 5x5x5).

Most importantly, this approach is definitely irrefutable as far as God's Algorithm is concerned. This approach can obviously be used to compute God's Algorithm for all permutation puzzles.
 
Last edited:

qqwref

Member
Joined
Dec 18, 2007
Messages
7,834
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
I've had that idea too. Here's the big problem: suppose we do this for the 4x4x4, which has 7.4 * 10^45 positions. To even keep track of the bare minimum (which positions have been solved so far) we need at least one bit for each position, or 9.2 * 10^44 bytes. This is about 8.4 * 10^32 terabytes. You can currently buy space for about $40 a terabyte. I think you can see where this is headed.

(For comparison, the 3x3x3 is "only" 4.8 million terabytes. Hence the coset approach.)
 
Joined
Dec 11, 2009
Messages
294
I've had that idea too. Here's the big problem: suppose we do this for the 4x4x4, which has 7.4 * 10^45 positions. To even keep track of the bare minimum (which positions have been solved so far) we need at least one bit for each position, or 9.2 * 10^44 bytes. This is about 8.4 * 10^32 terabytes. You can currently buy space for about $40 a terabyte. I think you can see where this is headed.

(For comparison, the 3x3x3 is "only" 4.8 million terabytes. Hence the coset approach.)

What if you only need to keep track of SYMMETRICALLY UNIQUE positions?
 
Joined
Dec 11, 2009
Messages
294
You'd probably save a factor of about 24*2*2 (for rotations + mirrors + inverses), at most. Since that's about 10^2, you would still have to store 8.4 * 10^30 terabytes. I think you can see that this doesn't help much.

Start from the 1st move of the scramble, and only store the position if it is symmetrically unique. I think you may have overestimated much.
 
Last edited:

cuBerBruce

Member
Joined
Oct 8, 2006
Messages
914
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
Visit Channel
How many symmetrically unique positions are possible for the 1st turn (4x4x4)?

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
And 4x4x4 (non-supercube) positions do not have (unique) inverses, so you'd only save about a factor of 48 using symmetry.
 

mr. giggums

Member
Joined
Feb 14, 2010
Messages
394
Location
Batavia, Northern Illinois
WCA
2011BERN02
I believe on the 3x3 there are 1,090,175,792,696,524,800 non-symetric positions which is about 1/40 of the original number. Now the non-symetric positions can be stored in 60 bits per position times the # of positions which equals 65,410,547,561,791,488,000 bits or 8,176,318,445,223,936,000 bytes or ~8,176,318.4 terabytes.
For 4x4 there are 7,401,196,841,564,901,869,874,093,974,498,574,336,000,000,000 positions now assuming that the 1/40 ratio is true (it isn't but hopefully it will be closer than 1/96 (= 1/24*1/2*1/2) ) then the non-symetric positions are 185,029,921,039,122,546,746,852,349,362,464,358,400,000,000. That can be stored in 148 bits per position for a total of 185,029,921,039,122,546,746,852,349,362,464,358,400,000,000 bits or 185,029,921,039,122,546,746,852,349,362,464,358,400,000,000 bytes or ~185,029,921,039,122,546,746,852,349,362,464.4 terabytes or ~1.85*10^32 terabytes.

TL;DR
3x3 = ~8,176,318.4 terabytes
4x4 = ~1.85*10^32 terabytes
 

cuBerBruce

Member
Joined
Oct 8, 2006
Messages
914
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
Visit Channel
I believe on the 3x3 there are 1,090,175,792,696,524,800 non-symetric positions which is about 1/40 of the original number. Now the non-symetric positions can be stored in 60 bits per position times the # of positions which equals 65,410,547,561,791,488,000 bits or 8,176,318,445,223,936,000 bytes or ~8,176,318.4 terabytes.

It's long been known that the number of symmetry-reduced positions for the 3x3x3 is 901,083,404,981,813,616. So the ratio of cube positions to symmetry-reduced cube positions for 3x3x3 is 43,252,003,274,489,856,000/901,083,404,981,813,616 which is approximately 47.9999998172897.

The number of symmetric positions is 164,604,041,664, so the number of non-symmetric positions is 43,252,003,274,489,856,000 - 164,604,041,664 = 43,252,003,109,885,814,336. Dividing this by 48 gives 901,083,398,122,621,132 symmetry-reduced unsymmetric positions.

I don't know how you came up with the numbers you did.
 

qqwref

Member
Joined
Dec 18, 2007
Messages
7,834
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
How many symmetrically unique positions are possible for the 1st turn (4x4x4)?
2 or 3, depending on what type of turns are allowed. You still haven't explained what you mean (i.e. whether I overestimated the rough amount of symmetric positions, or the ending number of bits) and why you think it would significantly change my numbers or my conclusion.
 
Top