# God's number is...



## Tim Reynolds (Jun 29, 2011)

\( \Theta(n^2/\log n) \) (for an n x n x n Rubik's Cube)

http://arxiv.org/abs/1106.5736

Haven't read the paper yet, probably will tonight.

THIS IS AN ASYMPTOTIC BOUND, NOT AN EXACT NUMBER. DON'T JUST PLUG IN n=3 AND EXPECT TO GET 20.


----------



## d4m4s74 (Jun 29, 2011)

my math is off, what's god's number on the 3x3x3 according to this?

I mean, if I take Θ(n^2/log n), change the n into 3 (I assume that's correct because they're talking about nxnxn puzzles) I get Θ(3^2/log 3) which according to wolphram alpha equals 1. that can't be it...


----------



## Owen (Jun 29, 2011)

This cannot possibly work...

I can't wait for one of our mathematicians to come in here and explain it.


----------



## aronpm (Jun 29, 2011)

Owen said:


> This cannot possibly work...


 
Why not?


----------



## Goosly (Jun 29, 2011)

I'm curious for a simplified summary of the paper  I don't like reading theoretical things like this anymore, especially since my exams ended only 2 days ago.


----------



## Stefan (Jun 29, 2011)

d4m4s74 said:


> my math is off, what's god's number on the 3x3x3 according to this?
> 
> I mean, if I take Θ(n^2/log n), change the n into 3 (I assume that's correct because they're talking about nxnxn puzzles) I get Θ(3^2/log 3) which according to wolphram alpha equals 1. that can't be it...


 
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.

It's similar to saying that _"bacteria colonies grow *exponentially*"_ or _"your hair grows *linearly*"_. You don't get exact numbers, but it does tell you the "kind" of growth speed.


----------



## Owen (Jun 29, 2011)

aronpm said:


> Why not?


 
Because the way the previous posters interpreted it, it made no sense that you could just plug a number into this simple formula, and get god's number.
This was later confirmed by Stefan Pochmann.


----------



## aronpm (Jun 29, 2011)

Owen said:


> Because the way the previous posters interpreted it, it made no sense that you could just plug a number into this simple formula, and get god's number.
> This was later confirmed by Stefan Pochmann.


 
Previous posters... a 12 year old and someone who copy+pasted it to W|A? Learn what the big theta notation means before you say "it's not possible"


----------



## MTGjumper (Jun 29, 2011)

Well, saying "this cannot possibly work" implies that you disagree what was originally posted.


----------



## d4m4s74 (Jun 29, 2011)

Stefan said:


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


 
Thanks for the clarification, I should have read more then just the abstract. 

Damn, ever since I dropped out I started forgetting a lot, I learned about and used the big O less then a year ago.


----------



## okayama (Jun 30, 2011)

*God's number in NxN cubes*

MIT News: Andrew Winslow showed that the maximum number of moves required to solve a Rubik’s cube with N squares per row is proportional to N^2/log N.
http://web.mit.edu/newsoffice/2011/rubiks-cube-0629.html


----------



## Stefan (Jun 30, 2011)

Seems to be a nice article (except I disagree with the opening paragraph claiming the 20-moves-team didn't evaluate all positions).


----------



## Stefan (Jul 1, 2011)

Stefan said:


> Seems to be a nice article (except I disagree with the opening paragraph claiming the 20-moves-team didn't evaluate all positions).


 
I just realized that they don't properly report about the lower bound, so I don't like that, either. The New Scientist article is worse in some respects, good in others.


----------



## qqwref (Jul 1, 2011)

I looked at the paper, and it was impressive, but not as amazing as it sounded. I have a mixed reaction to the God's Number result; on one hand, it's cool that they established a better upper bound (i.e. a better general solution), but on the other hand establishing something is Θ(n^2/log n) is only useful for computability theorists. It's an interesting-sounding result, but doesn't really have much practical use IMO, because saying that some sequence follows a particular pattern of growth as it goes to infinity doesn't tell us anything about individual values, and we only have two values of the series calculated anyway (11, 20, ...) with a third being very far off.

The "optimal solution of a*b*n can be found in polynomial time on n" result is similar; it sounds interesting, but it's only useful in a mathematical sense to establish a bound for the infinite series, and doesn't really make it easier to actually do the solving. The technique used in the proof relies on brute force, and while it is polynomial in n (it looks to be O(n) but I'm not sure) it involves extremely large constants and thus has no real practical use.


----------



## Jorghi (Jul 1, 2011)

Well the programs that say "20 moves or less" simply just use bruteforcing methods to solve the cube. Though we don't really know how optimal the moves are and because it could take a long time to find a better solution.

Unless there is pure mathematical proof  xD ;P


----------



## qqwref (Jul 1, 2011)

Jorghi said:


> Though we don't really know how optimal the moves are and because it could take a long time to find a better solution.


Of course we know an optimal solution's optimal. The techniques for finding them are quite foolproof.


----------



## David Zemdegs (Jul 1, 2011)

http://www.youtube.com/watch?v=4dlrnw58OxM
Gods number as done recently on a science show in Australia (with a little bit of faz)


----------



## Stefan (Jul 1, 2011)

fazdad said:


> http://www.youtube.com/watch?v=4dlrnw58OxM
> Gods number as done recently on a science show in Australia (with a little bit of faz)


 


Stefan said:


> Great video! This should have its own thread (or maybe be in the 20-thread).



Knew it.


----------



## kprox1994 (Jul 2, 2011)

*Scientists Develop an Algorithim to Solve Cubes of any Size.*

Found this browsing engadget, pretty interesting. http://www.engadget.com/2011/07/01/scientists-develop-algorithm-to-solve-rubiks-cubes-of-any-size/&category=classic&altPost=alt&icid=eng_latest_art Can someone link this? It's too hard to do on my phone.


----------



## Xirned (Jul 2, 2011)

http://www.engadget.com/2011/07/01/scientists-develop-algorithm-to-solve-rubiks-cubes-of-any-size/


----------



## cubernya (Jul 2, 2011)

Thanks...was wondering why the link wasn't working


----------



## PatrickJameson (Jul 2, 2011)

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 (Jul 2, 2011)

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 (Jul 2, 2011)

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


----------



## Stefan (Jul 3, 2011)

Xirned said:


> http://www.engadget.com/2011/07/01/scientists-develop-algorithm-to-solve-rubiks-cubes-of-any-size/


 
Geez that one is terrible. So much wrong with that.


----------



## Herbert Kociemba (Aug 4, 2011)

Stefan said:


> 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


----------



## cmhardw (Aug 5, 2011)

Herbert Kociemba said:


> 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!



Herbert Kociemba said:


> A more carefull analysis does not change the situation, see
> 
> http://cubezzz.dyndns.org/drupal/?q=node/view/236 (h-s metric)
> 
> ...



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.



Herbert Kociemba said:


> 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  )


----------



## Herbert Kociemba (Aug 5, 2011)

cmhardw said:


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


----------



## Christopher Mowla (Aug 17, 2011)

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.


----------



## Godmil (Aug 17, 2011)

I had that idea too, there must be some obvious reason why it's not easier... I just can't put my finger on it.


----------



## qqwref (Aug 17, 2011)

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


----------



## reThinking the Cube (Aug 18, 2011)

qqwref said:


> 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?


----------



## qqwref (Aug 18, 2011)

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.


----------



## reThinking the Cube (Aug 18, 2011)

qqwref said:


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


----------



## qqwref (Aug 18, 2011)

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.


----------



## reThinking the Cube (Aug 18, 2011)

qqwref said:


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



How many symmetrically unique positions are possible for the 1st turn (4x4x4)?


----------



## cuBerBruce (Aug 18, 2011)

reThinking the Cube said:


> How many symmetrically unique positions are possible for the 1st turn (4x4x4)?


 

```
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 (Aug 18, 2011)

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 (Aug 18, 2011)

mr. giggums said:


> 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 (Aug 18, 2011)

reThinking the Cube said:


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


----------



## cuBerBruce (Aug 18, 2011)

qqwref said:


> 2 or 3, depending on what type of turns are allowed.



At least 4 for any standard metric including half-turns. For BTM, it's 8. Didn't you see my table?


----------



## qqwref (Aug 18, 2011)

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.


----------



## reThinking the Cube (Aug 19, 2011)

cuBerBruce said:


> ```
> block turns (half-turns allowed)
> 
> moves  positions  cumulative   positions  cumulative pos.
> ...



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 (Aug 19, 2011)

reThinking the Cube said:


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


----------



## reThinking the Cube (Aug 20, 2011)

cuBerBruce said:


> 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 (Aug 20, 2011)

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



qqwref said:


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



He just needs a lesson on exponents.


----------



## Christopher Mowla (Aug 20, 2011)

JonWhite said:


> 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 (Aug 20, 2011)

reThinking the Cube said:


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


----------



## reThinking the Cube (Aug 21, 2011)

cmowla said:


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

```
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
```



qqwref said:


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



JonWhite said:


> 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 (Aug 21, 2011)

reThinking the Cube said:


> 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 (Aug 26, 2011)

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?


----------



## Cubenovice (Aug 26, 2011)

peppermill said:


> is it worth having knowing gods algorithym?



Yes, if you work it out and *don't* show everyone how it is done.


----------



## riffz (Aug 26, 2011)

peppermill said:


> 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 (Aug 26, 2011)

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.


----------



## peppermill (Aug 28, 2011)

Thankyou cubenovice, riffz and cuberbruce for your succint replies, happy cubing


----------



## Christopher Mowla (Oct 3, 2011)

Herbert Kociemba said:


> 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]

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


----------



## IanTheCuber (Nov 2, 2011)

God's Number is 20...but the FMC WR is 22, proving that humans aren't perfect.

Yes, I am a Christian.


----------



## riffz (Nov 3, 2011)

IanTheCuber said:


> God's Number is 20...but the FMC WR is 22, proving that humans aren't perfect.
> 
> Yes, I am a Christian.



How do you define perfect?


----------



## qqwref (Nov 3, 2011)

cmowla said:


> 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?



IanTheCuber said:


> 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!)


----------



## Cielo (Nov 8, 2011)

IanTheCuber said:


> God's Number is 20...but the FMC WR is 22, proving that humans aren't perfect.
> 
> Yes, I am a Christian.



In fact, István Kocza is unlucky, his WR solution should have been less than 20 moves.

That's because


qqwref said:


> The two numbers are unrelated; FMC scrambles rarely have an optimal solution of 20 moves.


----------



## rokicki (Nov 9, 2011)

*FMC vs God's Number*

Anyone have an estimate for the total number of FMC competitions that have been held, worldwide, ever?

I would be surprised if, assuming random choice of positions, *any* of the positions in any of the FMC competitions have been at distance 20. Those positions are quite rare.

Indeed, almost certainly most have been at distance 18.

Nonetheless, it's absolutely amazing to me how well FMC competitors manage to do.


----------



## Cubenovice (Nov 9, 2011)

1 you should be able to extract the official FMC events from the WCA database which can be downloaded from the WCA site.
2 we are currently at round 371 at fmc.mustcube.net
3 the weekly comp on the forum has several years of FMC

there are propbably some more online comps (speedcubers.de, ..., ...)


----------



## Stefan (Nov 9, 2011)

In the WCA database it looks like 304 scrambles. Though in the recent parallel Chinese fewest moves competitions, maybe they used the same scrambles?



rokicki said:


> Indeed, almost certainly *most have been at distance 18*.



If we assume 1000 scrambles, what's the probability for that?


----------



## rokicki (Nov 10, 2011)

*Probabilities*

We only have an approximate distance distribution above 16,
but it uses a million sample points so it's probably not too
far off.

Probability of none being distance 20 (assuming all are random
and 1000 samples): probably somewhere around 1-1e-8
(that is, 0.99999999, or eight nines).

Probability of most being distance 18: quite a bit higher than
eight nines; about 67% of all positions are 18, and 1000 is a
high number of samples. I get about 1-1e-28, or 28 nines.


----------



## Julian (Nov 11, 2011)

IanTheCuber said:


> God's Number is 20...but the FMC WR is 22, proving that humans aren't perfect.
> 
> Yes, I am a Christian.


I am baffled by this post.


----------



## rk960925 (Nov 16, 2011)

I think it's whatever the length of the scramble is because God can't solve it shorter than the scramble.
Or maybe he can. lol


----------



## Jaycee (Nov 16, 2011)

rk960925 said:


> I think it's whatever the length of the scramble is because God can't solve it shorter than the scramble.
> Or maybe he can. lol


 
50 move scramble?

All positions can be solved in 20 moves or less.


----------



## Ranzha (Nov 16, 2011)

rk960925 said:


> I think it's whatever the length of the scramble is because God can't solve it shorter than the scramble.
> Or maybe he can. lol


 
Try this:
F R U' R' U' R U R' F' R U R' U' R' F R F' (17)
R2 U' R2 U' R2 U y' R U R' B2' R U' R' (13)
You were saying?


----------



## Christopher Mowla (Feb 23, 2013)

This might be pointless, but as a consequence of me currently solving mrCage's commutator problem (I'm making progress, but it's slow and I'm not working on it very often), I can solve the nxnxn cube in 2-3 phases. (Assuming that the middle edges and corners can be solved with one commutator) (2 phases if there are no slices with an odd permutation or 3 if some or all of them are). But if all even permutations (and orientations) of the nxnxn cube can be solved with one commutator, then....

Since all even permutation cycle classes for:
8 objects (corners) can be solved with two iterations of 3 2-cycles,
12 objects (middle edges) can be solved with two iterations of 5 2-cycles,
24 objects (wing edges and all non-fixed center orbits) can be solved with two iterations of 11 2-cycles

We can establish an upperbound for the nxnxn cube to be twice the length of the case(s) which require the longest optimal maneuver which does some 3 2-cycle sequence, some 5 2-cycle sequence, and some 11 2-cycle sequence (in all orbits of pieces besides the corner and middle edge orbits) + at most floor(n/2) slice quarter turns (we first do a quarter turn to every slice which has an odd permutation to get the cube into the commutator subgroup).

In other words, if we wanted to calculate the upperbound for the 3x3x3 using this approach (we already know God's number for the 3x3x3, of course), we would need to solve all {3 2-cycle of corners, 5 2-cycle of middle edges} positions (including all orientations of corners and middle edges) and then the upperbound would be twice the length of the case(s) which require the longest optimal maneuver + 1. One such position is generated by the maneuver L2 F' L2 U2 F2 U2 F' L2 F2 U2 F D2 R2 B2. I don't know if this alg is move optimal (cube explorer is too slow), but assuming that it is and assuming that this is one of the worst {3 2-cycle of corners, 5 2-cycle of middle edges} as far as required moves go, then the upperbound for the 3x3x3 would be 2(14)+1 = 29, for example.

It would be a lot of computing, but, taking the 11 2-cycles for 24 objects, for example, we would "only" need to solve (3794809718700/24!)100 = 6.116*10^-10% of the permutations for each set of 24 objects...(well this percentage might be off due to the symmetries of the cube, but it might be in the ballpark). So instead of having 24!^2 positions to test for the 4x4x4 (ignoring the corners at the moment) (which has one wing edge orbit and one X-center orbit), we would need to test (3794809718700)^2 positions.

Of course for non-fixed center pieces on the regular nxnxn cube, we can treat them to be a variety of cycle classes since there are 4 of each color in every orbit, and this complicates things.

I'm not sure if this approach would generate smaller upperbounds than "trivial" approaches which have already been known, but I just thought I should mention it, especially for cube sizes larger than those which we have non-trivial upperbounds for. I have no idea if a product of disjoint 2-cycles are easy cycle classes to solve optimally, but if they are, this approach could be worth while.


----------



## cuBerBruce (Feb 23, 2013)

cmowla said:


> (see spoiler)





Spoiler



This might be pointless, but as a consequence of me currently solving mrCage's commutator problem (I'm making progress, but it's slow and I'm not working on it very often), I can solve the nxnxn cube in 2-3 phases. (Assuming that the middle edges and corners can be solved with one commutator) (2 phases if there are no slices with an odd permutation or 3 if some or all of them are). But if all even permutations (and orientations) of the nxnxn cube can be solved with one commutator, then....

Since all even permutation cycle classes for:
8 objects (corners) can be solved with two iterations of 3 2-cycles,
12 objects (middle edges) can be solved with two iterations of 5 2-cycles,
24 objects (wing edges and all non-fixed center orbits) can be solved with two iterations of 11 2-cycles

We can establish an upperbound for the nxnxn cube to be twice the length of the case(s) which require the longest optimal maneuver which does some 3 2-cycle sequence, some 5 2-cycle sequence, and some 11 2-cycle sequence (in all orbits of pieces besides the corner and middle edge orbits) + at most floor(n/2) slice quarter turns (we first do a quarter turn to every slice which has an odd permutation to get the cube into the commutator subgroup).

In other words, if we wanted to calculate the upperbound for the 3x3x3 using this approach (we already know God's number for the 3x3x3, of course), we would need to solve all {3 2-cycle of corners, 5 2-cycle of middle edges} positions (including all orientations of corners and middle edges) and then the upperbound would be twice the length of the case(s) which require the longest optimal maneuver + 1. One such position is generated by the maneuver L2 F' L2 U2 F2 U2 F' L2 F2 U2 F D2 R2 B2. I don't know if this alg is move optimal (cube explorer is too slow), but assuming that it is and assuming that this is one of the worst {3 2-cycle of corners, 5 2-cycle of middle edges} as far as required moves go, then the upperbound for the 3x3x3 would be 2(14)+1 = 29, for example.

It would be a lot of computing, but, taking the 11 2-cycles for 24 objects, for example, we would "only" need to solve (3794809718700/24!)100 = 6.116*10^-10% of the permutations for each set of 24 objects...(well this percentage might be off due to the symmetries of the cube, but it might be in the ballpark). So instead of having 24!^2 positions to test for the 4x4x4 (ignoring the corners at the moment) (which has one wing edge orbit and one X-center orbit), we would need to test (3794809718700)^2 positions.

Of course for non-fixed center pieces on the regular nxnxn cube, we can treat them to be a variety of cycle classes since there are 4 of each color in every orbit, and this complicates things.

I'm not sure if this approach would generate smaller upperbounds than "trivial" approaches which have already been known, but I just thought I should mention it, especially for cube sizes larger than those which we have non-trivial upperbounds for. I have no idea if a product of disjoint 2-cycles are easy cycle classes to solve optimally, but if they are, this approach could be worth while.



I note that the position L2 F' L2 U2 F2 U2 F' L2 F2 U2 F D2 R2 B2 is just two moves away from a position that is only a 2-cycle of corners and a 2-cycle of edges. Thus, I would guess it's more like a near-best case for its cycle structure than a near worst-case.

Around 2/3 of all 3x3x3 cube positions require 18 moves to solve optimally. I would tend to guess some of the positions with the cycle structures cmowla mentioned will require that many moves. Thus, it wouldn't surprise me if the upper bound result would be something more like 36. (I just tried conjugating the above with a rather arbitrary 5-move maneuver, F R' D L F), and this resulted in an 18f* position. This suggests that 18f* positions are probably very common for this particular cycle structure.)

In general, we expect God's number for an nxnxn cube to be only "slightly more" than the peak distance. Thus, I think this will generally produce a bound nearly twice the actual value of God's number, not to mention that for even relatively small n, the number of configurations to solve gets extraordinarily large. So you might have to consider solving only two or even one orbit at a time, and this would result in bounds an increasingly larger factor off from God's number as n increases. While this may be an interesting approach at producing an upper bound on God's number, I think it is not going to get as good a result as other more conventional approaches.

I find that the position cmowla gave is actually 14f*: U2 F D' L2 U B' U' B D2 B' D2 L2 F' D'

I note that applying U2 D2 gives a 13f* position, a 2-cycle of corners and a 2-cycle of edges. I also note that applying D2 (R2 U2)3 results in N-perm. I noticed when I solved all of the PLL configurations (including all AUF cases) optimally, that the N-perms took notoriously long to solve, despite a relative low move count. Since cmowla's position is somewhat related to N-perm, this would seem to have something to do with why Cube Explorer takes so long to solve that position optimally.


----------



## Christopher Mowla (Jul 14, 2014)

*A Simple Algorithm for Approximating God's Number*

Hey guys,

The following is just another one of my crazy approximations of god's number (I think it works best with h-b move metric, which I think is OBTM), but it is based off of such a simple idea, and the results seem to be very reasonable, that I thought I should just post it before I forget it.
*Algorithm*​
Let's let a formula which gives the number of positions of the _n_x_n_x_n_ cube be called \( f\left( n \right) \), then I "claim" that god's number is within a small proximity of the result from using the following algorithm.

[1] Choose a cube size for which you want to approximate god's number for in OBTM and call it N.
[2] Evaluate \( \left\lfloor \text{Log}_{10}\left[ f\left( N \right) \right]+0.5 \right\rfloor \) to get the number of digits of \( f\left( N \right) \).
[3] Now, by experimentation, substitute values for _k_ in \( \left\lfloor \text{Log}_{10}\left[ k! \right]+0.5 \right\rfloor \) to try to match the value calculated in step [2]. Choose _k_ + 1 if _k_ is smaller than the result from [2] and _k_ + 1 is larger than the result from [2].

The God's number approximation will be the value of _k_ which is obtained in step [3].

*Formula*​
Using this approximation of the number of digits of _k_! and using Mathematica, I get the following formula which "calculates the lower and upperbound" for a cube of size N.

\( \text{God }\!\!'\!\!\text{ sNo.}\left( n \right)=\left\lfloor \frac{\left\lfloor \text{Log}_{10}\left[ f\left( n \right) \right]+0.5 \right\rfloor \left( \ln \left( 2 \right)+\ln \left( 5 \right) \right)}{\text{ProductLog}\left[ \frac{1}{b}\left\lfloor \text{Log}_{10}\left[ f\left( n \right) \right]+0.5 \right\rfloor \left( \ln \left( 2 \right)+\ln \left( 5 \right) \right) \right]} \right\rfloor \)​
, where: ProductLog[x] is the inverse function of \( xe^{x} \),
choose \( b=2 \) to get the "lowerbound" and choose \( b=3 \) to get the "upperbound".
, and again, \( f\left( n \right) \) is any number of positions formula for cube size _n_.

This formula is only necessary for very large _n_, and its purpose is to give you an interval where to start testing _k_ values when finding the number of digits _k_! has (which is step [3] of the algorithm).
*Results from the Algorithm and the Formula*​
Below, "GN" is the "actual" God's number approximation using the algorithm, and the bracketed pair is the lowerbound and upperbound achieved from the formula.


n=2, {10,11}, GN = 10
n=3, {20,22}, GN = 21
n=4, {36,40}, GN = 39
n=5, {52,57}, GN = 56
n=6, {73,81}, GN = 79
n=7, {95,103}, GN = 101
n=8, {122,132}, GN = 129
n=9, {148,160}, GN = 157
n=10, {179,193}, GN = 189
n=11, {210,226}, GN = 222
n=12, {245,263}, GN = 259
n=13, {281,301}, GN = 296
n=14, {321,343}, GN = 338
n=15, {360,385}, GN = 379
n=16, {404,432}, GN = 425
n=17, {448,478}, GN = 471
n=18, {496,529}, GN = 521
n=19, {544,580}, GN = 571
n=20, {596,635}, GN = 625
n=100, {10344,10801}, GN = 10687
n=1000, {698895,720084}, GN = 714818
n=1001, {700192,721417}, GN = 716142​*Comment*​ 
I can see that my approximation for _n_ = 1001 is smaller than qqwref's lowerbound of 981766, but I'm not sure exactly if his was correct.


----------



## qqwref (Jul 14, 2014)

You call that simple?!?

Also, iirc it's known that God's Number is Θ(n^2/log n) - how does this formula compare? It's really hard to tell with all the floors and the ProductLog and stuff. And it sounds like you're pretty much just finding the value of k for which the k! has about the same number of digits as the number of positions of the cube. For instance the 7x7x7 has ~10^160 positions and 101! is ~10^160. But surely factorials have nothing to do with the number of moves it takes to get to a given state, right? 

What worries me is that there is really no theoretical basis for your formula (and that the "upper bound" and "lower bound" you give are not upper and lower bounds of God's Number at all, they're just values from slightly different versions of your formula). You sort of just pulled an idea out of thin air based on some numerical coincedences. And remember that you actually only have two data points here (two known God's Numbers), so if you're just trying to fit a function to the data, it'd be extremely easy to find one that looks like it works. Unless you have some reason, based on the properties of cube moves and cube pieces, I don't see any reason not to disregard this formula and the numbers it produces.


----------



## Christopher Mowla (Jul 14, 2014)

qqwref said:


> And it sounds like you're pretty much just finding the value of k for which the k! has about the same number of digits as the number of positions of the cube.


That's exactly right.



qqwref said:


> But surely factorials have nothing to do with the number of moves it takes to get to a given state, right?


Probably not.



qqwref said:


> What worries me is that there is really no theoretical basis for your formula (and that the "upper bound" and "lower bound" you give are not upper and lower bounds of God's Number at all, they're just values from slightly different versions of your formula). You sort of just pulled an idea out of thin air based on some numerical coincidences.


That's exactly right. However, the results from the formula are not the lower and upperbounds talked about when referring to God's number, but the lower or upperbounds which we choose for _k_ in _k_! without having to "guess" too much to get the approximation for God's number. The formula is mainly used to aid us to quickly find the value of _k_ in _k_! such that the number of digits it contains matches the number of digits of _f_(_N_).



qqwref said:


> And remember that you actually only have two data points here (two known God's Numbers), so if you're just trying to fit a function to the data, it'd be extremely easy to find one that looks like it works.


I know. This is the third or fourth formula I've found so far like this.



qqwref said:


> Unless you have some reason, based on the properties of cube moves and cube pieces, I don't see any reason not to disregard this formula and the numbers it produces.


I wasn't asking you or anyone to take this seriously. I was mainly posting it for entertainment purposes.

Lastly, yes, I call this algorithm simple. The formula isn't exactly, but the algorithm (idea) is very simple. I thought this was a fun way to directly use the number of positions to create an approximation.


----------



## qqwref (Jul 14, 2014)

It's not a working approximation though, it's just a function that matches the two known values (if you fudge it a bit) and roughly increases as n increases. If someone really wants to get a good sense of what God's Number might be for larger cubes, this is not a good starting point.


----------



## IRNjuggle28 (Jul 14, 2014)

Do we have ideas of what positions are likely to be hardest to solve on NxNxN? On 3x3, for example, people had theorized that superflip was an extremely bad position before brute force solvers proved that. Are there positions on 4x4, or 5x5, or NxN for that matter, that are likely to be hard to solve for theory based reasons? It seems like finding a dozen or so 4x4 positions that are each going to require lengthy solutions for their own individual reasons, and brute forcing them, could at least give an reasonable estimate for God's number. 

Another idea that might be worth considering is brute forcing a bunch of random 4x4 permutations, and using that approximate average solution length to generate a guess at 4x4 God's number by examining the standard deviation of solution length as well as the God's numbers of 2x2 and 3x3 and extrapolating.

The reason I'm mostly thinking of this for 4x4 is that I know that things get harder and harder to brute force the bigger they get, and that these estimates will get inaccurate fast if they're extrapolated far enough. So, with those things in mind, are either of these ideas useful? The idea is that conclusions based on vague or approximated data is more likely to be accurate than conclusions based on vague or approximated theory.


----------



## qqwref (Jul 15, 2014)

I don't think we have any educated guesses about what positions are the hardest to solve, and we are nowhere near being able to brute force optimally solve random 4x4x4 positions anyway. (It's about 10^26 times as hard as brute force optimally solving random 3x3x3 positions.) I'm sure if it was practical to find optimal solutions to 4x4x4 states people would already have done a bunch of random scrambles and difficult-looking pretty patterns, and posted the results.


----------



## rokicki (Jul 15, 2014)

I estimate that optimally solving a *single* randomly chosen 4x4x4 position would take
roughly as much time as computing God's number for the 3x3x3, based on current
knowledge and technology.

I am also pretty sure we will come up with ideas and techniques to reduce this.

Indeed, pushing this envelope is a big reason I'm sponsoring the Computer/Human
4x4x4 FMC challenge (which ends tomorrow at noon Pacific time.)


----------

