What is God's number on a 4x4 Rubik's cube?

[KottenCube]

Now please don't go asking for bigger cube god numbers. It took day with Google computers for a 3x3, imagine how long it would take them with a 4x4.

 

[Lucas Garron]

http://www.wolframalpha.com/input/?i=gods+number

Look at the description. Oh god.

Then leave feedback with an improved description. They listen.
(The description is based on MathWorld.)

 

[CubeRoots]

I don't see what's wrong with this description, it's correct.

 

[Stefan]

The number involves both a maximum and a minimum, and "minimum" and "required" both cover the minimum aspect while the maximum aspect is missing. Should be "maximum number of turns required" or "minimum number of turns sufficient".

 

[tx789]

There's 7.4x10^45 and a 3x3 has 4.3x10^18 so if it takes one day to do 43 quintillion(4.3x10^18) it would take approx years (no calulator likes you putting in the 7.4x10^45 or at least true iOS one)

 

[Ickathu]

but when you add in the increased speed and strength and power of technology and computers, I estimate that Google could crack it in about 2 years. I wonder how fast it could be calculated if you used all the supercomputers and processing power that the US government uses... Not that that would happen, of course, but I bet that could do it in 6 months to a year.

 

[RNewms27]

There's 7.4x10^45 and a 3x3 has 4.3x10^18 so if it takes one day to do 43 quintillion(4.3x10^18) it would take approx years (no calulator likes you putting in the 7.4x10^45 or at least true iOS one)

From cube20.org about the 3x3:

"We partitioned the positions into 2,217,093,120 sets of 19,508,428,800 positions each.
We reduced the count of sets we needed to solve to 55,882,296 using symmetry and set covering.
We did not find optimal solutions to each position, but instead only solutions of length 20 or less.
We wrote a program that solved a single set in about 20 seconds.
We used about 35 CPU years to find solutions to all of the positions in each of the 55,882,296 sets."

Symmetry will make the numbers smaller, but 4x4 solutions are also much longer.

 

[Stefan]

but when you add in the increased speed and strength and power of technology and computers, I estimate that Google could crack it in about 2 years. I wonder how fast it could be calculated if you used all the supercomputers and processing power that the US government uses... Not that that would happen, of course, but I bet that could do it in 6 months to a year.

I'd like to see how you calculated those times.

 

[Ickathu]

I'd like to see how you calculated those times.

computerz get fazters, not uber fazt, I like the number 2, yearz seems like a good unit. Government haz bunches of cpus, probably 4 or more times cpu power than goooogle. 6 monfz.

i.e., I didn't.

 

[qqwref]

Uh, the problem is 1.7 * 10^26 times harder just in terms of the number of positions alone. That is about a sixth of a billion billion billion. To crack it in 170 million days (which is about 465,000 years) we would need a billion billion times as much computing power as Google used for the cube20 experiment. And oh yeah, we also have to factor in that solving each position takes longer (have we even solved ONE random 4x4x4 position optimally yet?), that we would need much more storage space (an exabyte is far far too small), and that dividing the search space into cosets is much harder for 4x4x4 (since it's not a group).

I think it's absolutely fair to say that this won't be computed in the lifetime of anyone on this forum now.

 

[Owen]

I think it's absolutely fair to say that this won't be computed in the lifetime of anyone on this forum now.

Bummer, I am really curious about this.

 

[tx789]

I think it's absolutely fair to say that this won't be computed in the lifetime of anyone on this forum now.

You never know still

 

[athena]

i'm going to make a wild guess that it's 77 single layer turns.
i found the pattern below which holds for n=1 to 3.

1^3 - 1^2 + 1^1 - 1^0 = 0
2^3 + 2^2 - 2^1 + 2^0 = 11
3^3 - 3^2 + 3^1 - 3^0 = 20
4^3 + 4^2 - 4^1 + 4^0 = 77
5^3 - 5^2 + 5^1 - 5^0 = 104
etc.

i doubt it's correct but i thought i would share.
i saw the current upper bound on n=4 is 77 here: http://cubezzz.dyndns.org/drupal/?q=node/view/93
so we just need to get it lower than 77 to throw away this pattern.

 

[ben1996123]

1^3 - 1^2 + 1^2 - 1^0 = 0
2^3 + 2^2 - 2^2 + 2^0 = 11
3^3 - 3^2 + 3^1 - 3^0 = 20
4^3 + 4^2 - 4^2 + 4^0 = 77
5^3 - 5^2 + 5^5 - 5^0 = 104

yeah you're bad at maff, I also doubt its correct.

 

[cuBerBruce]

i'm going to make a wild guess that it's 77 single layer turns.
i found the pattern below which holds for n=1 to 3.

1^3 - 1^2 + 1^2 - 1^0 = 0
2^3 + 2^2 - 2^2 + 2^0 = 11
3^3 - 3^2 + 3^1 - 3^0 = 20
4^3 + 4^2 - 4^2 + 4^0 = 77
5^3 - 5^2 + 5^5 - 5^0 = 104
etc.

i doubt it's correct but i thought i would share.
i saw the current upper bound on n=4 is 77 here: http://cubezzz.dyndns.org/drupal/?q=node/view/93
so we just need to get it lower than 77 to throw away this pattern.

The number 20 for 3x3x3 restricts turns to face layers only. Allowing central layer turns, it's likely to be 18 or 19 (although I'm not aware 20 has been ruled out with certainty).

I also presume 77 to be a rather weak upper bound on 4x4x4. A similar technique on 3x3x3 resulted in a 29-move upper bound (face turns).

 

[qqwref]

That, plus:
- you can't do unique cubic interpolation on only two or three data points
- God's number isn't O(n^3), it's O(n^2/log n) (iirc).

 

[Christopher Mowla]

i'm going to make a wild guess that it's 77 single layer turns.
i found the pattern below which holds for n=1 to 3.

1^3 - 1^2 + 1^1 - 1^0 = 0
2^3 + 2^2 - 2^1 + 2^0 = 11
3^3 - 3^2 + 3^1 - 3^0 = 20
4^3 + 4^2 - 4^1 + 4^0 = 77
5^3 - 5^2 + 5^1 - 5^0 = 104
etc.

so we just need to get it lower than 77 to throw away this pattern.

Obviously you made a few typos (I fixed them in the quote above), but writing this pattern as a formula, it gives a value of 8381 slice half turns for the 20x20x20. I attempted to make a formula myself for this while back, and it seemed to give values larger than what God's number probably is for very large cubes. Based on my formula, GN for the 20x20x20 cannot be more than 867 slice half turns, and Mr. Rokicki claims that it must be at least 682. Even if GN for n = 20 is 1500 slice half turns, 8381 is a lot more (which also supports qqwref's comment). So 77 is most likely too high (based on my formula, it's going to be at most 63...it's most likely in the mid 40s).

EDIT: And I'm just playing here, but when I mentioned that GN for 4x4x4 is most likely in the mid 40s, extrapolating those calculations to the 100x100x100 gives about 15,000. (Just to make even more stupid guesses, based on my formula, GN for the 105^3 should be no more than 18k...just because someone is solving that one right now).

 

[IAssemble]

How many turns does it take you to solve a 4x4x4 cube?

Can you solve a 4x4x4 cube in fewer turns than MultiCuber 3?

Enjoy!

 

[ben1996123]

50 moves wat !

I was expecting it to take about 80

also, no

 

[AvGalen]

I have never been a big fan of 444fmc because I can really only do a very optimized reduction+avoidparity+333fmc. But I think my lowest ever was around 65 and most were much more like 80