God's Number for 5x5x5?

[nalralz]

I know there is a thread for God's number for 4x4x4 but but what is God's number for 5x5x5? Is it less than 60? The WCA scramble count is 60.

 

[guysensei1]

It's greater than 20. That I can say for sure.

 

[josh42732]

And greater than 21 definitely.

 

[cubernya]

Has anybody done the calculation for the number of turns it even takes to reach all positioms? I know this has been done for 3x3 (18) and 4x4 (32?)

 

[guysensei1]

Has anybody done the calculation for the number of turns it even takes to reach all positioms? I know this has been done for 3x3 (18) and 4x4 (32?)

Isn't the 3x3 one supposed to be 20?

 

[cashis]

yeah I'm pretty sure God's # for 333 is 20.

 

[theROUXbiksCube]

yeah I'm pretty sure God's # for 333 is 20.

someone got an 18 in the weekly FMC solves a while back i believe

 

[qqwref]

I'm pretty sure this is not something we'll know or even have a good shot at answering for a very, very long time. Do some FMC if you want - 103 sounds really good - but keep in mind that the 4x4x4 FMC contest that just concluded had winning averages of 36 for computer and 76 for human. So you are probably going to have to use a computer to get anywhere near optimal.

 

[cashis]

someone got an 18 in the weekly FMC solves a while back i believe

I'm not sure I'm seeing your point.
Every cube state can be solved with a maximum of 20 moves.

 

[theROUXbiksCube]

I'm not sure I'm seeing your point.
Every cube state can be solved with a maximum of 20 moves.

Maybe they confused the two

 

[shadowslice e]

Has anybody done the calculation for the number of turns it even takes to reach all positioms? I know this has been done for 3x3 (18) and 4x4 (32?)

God's number for 3x3x3 is definately 20. 18 was established as a lower bound for the number of moves that a cube could be solved in a while back.

However, this was not created using a supercomputer to all solutions but rather by working out how many possible combinations of 18 moves one could make on a cube and does not account for cubes that are isometric.

As it turns out the total number of unique positions a cube could be in (while assembled correctly) was less than the number of combinations of 18 turns one could make on a cube.

However, many, if not most cubes that could be created with the 18 turn movesets would be identical.

If i remember correctly, there are actually still a stupidly large number of 20-depth cubes possible (something like ~490,000,000)

In addition, as far as I'm aware, no one has actually proven that God's number for 3x3x3 is 20 mathematically- only via brute force methods.

 

[StachuK1992]

http://cube20.org/


There are about 490,000,000 20-depth cubes.

 

[tseitsei]

http://cube20.org/


There are about 490,000,000 20-depth cubes.

Yep and even if it sounds amazingly large number at first it really is VERY VERY small compared to total number of positions which is ~43*10^18

So that means that only (49*10^7)/(43*10^18) = 1.4*10^-11 = 1.4*10^-9 % of all positions are 20 move optimal. So ridiculously few

 

[NewCuber000]

someone got an 18 in the weekly FMC solves a while back i believe

Yes, of course theres going to be possible solutions to some scrambles under 20 moves. But what they're saying is that the most moves it will ever take to solve a rubiks cube will be 20 moves or less.

 

[TDM]

Isn't the 3x3 one supposed to be 20?

Not God's number. He means there are over 43 quintillion possible combinations of 18 moves or less (which is how the lower bound of 18 was found for 3x3 before we found superflip to be 20 moves optimal).

 

[cubernya]

God's number for 3x3x3 is definately 20. 18 was established as a lower bound for the number of moves that a cube could be solved in a while back.

However, this was not created using a supercomputer to all solutions but rather by working out how many possible combinations of 18 moves one could make on a cube and does not account for cubes that are isometric.

As it turns out the total number of unique positions a cube could be in (while assembled correctly) was less than the number of combinations of 18 turns one could make on a cube.

However, many, if not most cubes that could be created with the 18 turn movesets would be identical.

If i remember correctly, there are actually still a stupidly large number of 20-depth cubes possible (something like 200000+)

In addition, as far as I'm aware, no one has actually proven that God's number for 3x3x3 is 20 mathematically- only via brute force methods.

This is what I was getting at. I think I've seen calculations done like this for up to 7x7, but I have no idea where they are

 

[Christopher Mowla]

This is what I was getting at. I think I've seen calculations done like this for up to 7x7, but I have no idea where they are

Are you thinking of this or this?

 

[nalralz]

But what is it for 5x5?

 

[shadowslice e]

Total number of possible permutations for a 5x5x5= 282 870 942 277 741 856 536 180 333 107 150 328 293 127 731 985 672 134 721 536 000 000 000 000 000 =~2.83x10^74 (from Wikipedia)

Number of permutations possible for WCA scrambling= 15^60= 3.67x10^70

Doesn't this mean that at least 99.9% of scrambles on a professor are not reachable from a WCA scramble?

Actual number of moves needed to equalise the number of possible permutations= 64 (15^64=~1.86x10^74).

Considering many of these states would be identical or at least isomorphic, I would say that the WCA should employ a 70 move scramble.

However, the question at this point is: is it worth it? When a speedcuber begins to solve they will likely add to the number of moves required to reach each state rather than reduce it (at least for a few moves at the start)

 

[Lucas Garron]

Considering many of these states would be identical or at least isomorphic, I would say that the WCA should employ a 70 move scramble.

However, the question at this point is: is it worth it? When a speedcuber begins to solve they will likely add to the number of moves required to reach each state rather than reduce it (at least for a few moves at the start)

It doesn't matter, as long as the states are indistinguishable from random by a human. 10^74 states are good enough, as long as they are sufficiently well distributed.

It's a separate question to ask if they're well-distributed enough, one that probably hasn't had enough attention. But mostly unrelated to the "can we reach every state" calculation.

(The fraction of Megaminx scrambles we can generate is also very low.)