Equation for finding Gods number

[LunaNova223]

Hellooo!! I've been a bit curious about finding an equation to find the God number of any puzzle, somethings telling me there has to be one but it's just not discovered? Or maybe the math just proves its not a discoverable equation, I'm not sure!!

Thoughts?

 

[Hazel]

Unless there have been advancements I'm unaware of, there is no mathematical proof that God's number is 20. The proof we have is a proof by cases—lowering the number of configurations that need to be tested as much as possible via mirrors, inverses, etc., and making sure each one has a solution <= 20 moves long (this may be slightly incorrect, but the general method was as I stated). There is no non-brute-force proof like what you're asking for.

 

[LunaNova223]

Unless there have been advancements I'm unaware of, there is no mathematical proof that God's number is 20. The proof we have is a proof by cases—lowering the number of configurations that need to be tested as much as possible via mirrors, inverses, etc., and making sure each one has a solution <= 20 moves long (this may be slightly incorrect, but the general method was as I stated). There is no non-brute-force proof like what you're asking for.

I see! It just interests me because in my mind, there has to be some way to not brute force it, maybe I'm wrong but, I like to think a lot!

Apparently Google claims that in 2010 it was proven to be 20 using maths and computers which brute forced the remaining states for the cube, not sure though, the actual science hasn't been my real interest until a day ago!

Thanks for the reply

 

[Billabob]

The exact value was proven through bruteforce, specifically by first proving that Superflip requires 20 turns to solve, then proving that every other state is solvable in 20 or fewer turns. There's no known direct equation/algorithm to determine God's number for an arbitrary NxNxN puzzle but there are for lower- and upper-bounds.

Lower:
(1/4 log(24!/4!^6) + o(1)) N^2/log(N)

Upper:
(c + o(1)) N^2/log(N)

Conjectured value:
(1/4 log(24!/4!^6) + o(1)) N^2/log(N)

The source can be found here: https://arxiv.org/abs/1106.5736

My mistake, after reading the source these are complexity measures i.e. not concrete figures. Rokicki calculated some lower bounds here: https://web.archive.org/web/20200810000435/http://forum.cubeman.org/?q=node/view/236

I can't find his methodology though.

 

[eeeeeeeee]

The exact value was proven through bruteforce, specifically by first proving that Superflip requires 20 turns to solve, then proving that every other state is solvable in 20 or fewer turns. There's no known direct equation/algorithm to determine God's number for an arbitrary NxNxN puzzle but there are for lower- and upper-bounds.

Lower:
(1/4 log(24!/4!^6) + o(1)) N^2/log(N)

Upper:
(c + o(1)) N^2/log(N)

Conjectured value:
(1/4 log(24!/4!^6) + o(1)) N^2/log(N)

I personally haven't read the source but it can be found here: https://arxiv.org/abs/1106.5736

what do c, o, and n mean

 

[Billabob]

what do c, o, and n mean

I've amended my response as I was misreading the results (my fault for pasting before reading the paper). They're just equations for the computational complexity of each cube, you can't plug in N=4 to get bounds for the 4x4. There's a thread on the paper here with more information & interesting discussions: https://www.speedsolving.com/threads/gods-number-is.30231/

 

[bcube]

Hellooo!! I've been a bit curious about finding an equation to find the God number of any puzzle, somethings telling me there has to be one but it's just not discovered? Or maybe the math just proves its not a discoverable equation, I'm not sure!!

Thoughts?

Hi,

some problems can not currently be solved by humans without computer assistance. Computer-assisted proofs exist (see section "Theorems proved with the help of computer programs" to find the Rubik´s cube).

 

[LunaNova223]

The exact value was proven through bruteforce, specifically by first proving that Superflip requires 20 turns to solve, then proving that every other state is solvable in 20 or fewer turns. There's no known direct equation/algorithm to determine God's number for an arbitrary NxNxN puzzle but there are for lower- and upper-bounds.

Lower:
(1/4 log(24!/4!^6) + o(1)) N^2/log(N)

Upper:
(c + o(1)) N^2/log(N)

Conjectured value:
(1/4 log(24!/4!^6) + o(1)) N^2/log(N)

The source can be found here: https://arxiv.org/abs/1106.5736

My mistake, after reading the source these are complexity measures i.e. not concrete figures. Rokicki calculated some lower bounds here: https://web.archive.org/web/20200810000435/http://forum.cubeman.org/?q=node/view/236

I can't find his methodology though.

Rokicki's work is impressive to say the least, I've read his work and it's pretty awesome

I figured it was brute force, I was told it was done for a few puzzles with the help of computers, so I guess we can only wait until computers become powerful enough to brute force any and all NxNxN puzzle

I do want to believe there is an undiscovered equation for it, maybe getting close to it at least, I figured there'd be a link between reachable cube states, legal moves from any state, sides and ultimately Gods number for any puzzle, but maybe I'm dreaming too much haha

 

[Billabob]

I figured it was brute force, I was told it was done for a few puzzles with the help of computers, so I guess we can only wait until computers become powerful enough to brute force any and all NxNxN puzzle

You might be waiting a while because Rokicki has stated in the past that it would take more computing power to optimally solve a single 4x4 state than it took to solve the entire set of 3x3s. As computers become more and more powerful this becomes more feasible without borrowing Google's supercomputers but I'm not aware of any serious attempts to optimally solve a hard 4x4 scramble. 5x5 is totally out of the question and 6x6, 7x7, 8x8 etc get more and more absurd unless some new technique is devised to reduce the workload.

I had the idea to take the paper's approach of finding optimal solutions for every possible 3-cycle of pieces (doing this on the 5x5 suffices for every piece on every cube size) and multiplying out the worst-case scenario for the amount of pieces present per cube but it's already been done:

https://www.reddit.com/r/Cubers/comments/8chfuu/i_found_a_general_formula_for_an_upper_bound_of

I even read and upvoted this 7 years ago apparently. This gives a very high upper bound but it's still one that can be generalised to any N no matter how large.

The bound could be improved by applying the general principal that the fewer & larger the subsets you divide the puzzle into, the shorter the total solution should end up being. You could even take this to the limit of its absurdity and find optimal solutions for every state for corners, edges, midges, edge-centres, corner-centres, etc. then multiply these out by the amount of edge types present in the cube, but I doubt the upper bound would be close to the actual value of God's number.

 

[LunaNova223]

You might be waiting a while because Rokicki has stated in the past that it would take more computing power to optimally solve a single 4x4 state than it took to solve the entire set of 3x3s. As computers become more and more powerful this becomes more feasible without borrowing Google's supercomputers but I'm not aware of any serious attempts to optimally solve a hard 4x4 scramble. 5x5 is totally out of the question and 6x6, 7x7, 8x8 etc get more and more absurd unless some new technique is devised to reduce the workload.

I had the idea to take the paper's approach of finding optimal solutions for every possible 3-cycle of pieces (doing this on the 5x5 suffices for every piece on every cube size) and multiplying out the worst-case scenario for the amount of pieces present per cube but it's already been done:

https://www.reddit.com/r/Cubers/comments/8chfuu/i_found_a_general_formula_for_an_upper_bound_of

I even read and upvoted this 7 years ago apparently. This gives a very high upper bound but it's still one that can be generalised to any N no matter how large.

The bound could be improved by applying the general principal that the fewer & larger the subsets you divide the puzzle into, the shorter the total solution should end up being. You could even take this to the limit of its absurdity and find optimal solutions for every state for corners, edges, midges, edge-centres, corner-centres, etc. then multiply these out by the amount of edge types present in the cube, but I doubt the upper bound would be close to the actual value of God's number.

Yeah wow, It's definitely gonna take years, I'll beg google for a few days on the supercomputers one day!!

But in all seriousness, it doesn't seem completely impossible in the somewhat far future to be able to get somewhere with this! What triggered my curiosity was the Megaminx, thats the one I was researching before coming here, I'll look into the bound things though, I'm interested

 

[Ben Whitmore]

God's number for the NxNxN cube is at least floor(log((4-a)S)/log(3/(a-1))) where a = (3/2)^(1/(N-1)) and S is the number of states of the NxNxN cube

Table[Floor[Log[(4-(3/2)^(1/(n-1)))(24*12!*2^10)^Mod[n,2]7!3^6(24!)^Floor[n(n-2)/4]/(4!)^(6Floor[(n-2)^2/4])]/Log[3/((3/2)^(1/(n-1))-1)]],{n,2,50}] - Wolfram|Alpha

Wolfram|Alpha brings expert-level knowledge and capabilities to the broadest possible range of people—spanning all professions and education levels.

www.wolframalpha.com

 

[CubingKid]

Hellooo!! I've been a bit curious about finding an equation to find the God number of any puzzle, somethings telling me there has to be one but it's just not discovered? Or maybe the math just proves its not a discoverable equation, I'm not sure!!

Thoughts?

An exact formula does not exist but a formula for the lower bound does exist.