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

ryanmcg86 said:
is there some comprehensive list somewhere of all, or just all KNOWN move equivalents? like, as an example, LLL (3 moves) is the same thing as L'(1 move, for a total of 2 (3 - 1) move-amount difference), another would be RR' being the same...
Click to expand...

I did this for up to 5 moves. It's a 550 MB text file though.
 
qqwref said:
No, of course there is no such formula... we only know the number for 2x2x2 and 3x3x3. Even if we had such a formula how could we possibly prove it was correct? We do know the number grows proportional to n^2/log(n) for an nxnxn cube, but apart from that, pretty much nothing.
Click to expand...

If God's number for 2x2 and 3x3 had been calculated rather than brute forced, a formula may be possible to setup for any nxnxn cube.

Btw quantum computers can do many things at once right? They can check every solution for a scramble at the same time (if I'm understanding it correctly), so maybe we will be able to brute force God's number for the 4x4 within the next 10 or 20 years.
 
Chrizz said:
If God's number for 2x2 and 3x3 had been calculated rather than brute forced, a formula may be possible to setup for any nxnxn cube.

Btw quantum computers can do many things at once right? They can check every solution for a scramble at the same time (if I'm understanding it correctly), so maybe we will be able to brute force God's number for the 4x4 within the next 10 or 20 years.
Click to expand...

Most computers can do many things at once. for example, a computer with a 12-core processor can run 12 threads at once - you could say that it can do 12 things at once. It just depends on the CPU. Quantum computers are different because instead of 1s and 0s, they have 1s, 0s, and 'both at the same time'. I can't say I'm anywhere near knowledgable on them, but that's how I understand it.
 
Chrizz said:
a formula may be possible to setup for any nxnxn cube.
Click to expand...
Unfortunately, no one has any idea whether a simple formula exists or what it would look like.
(Although we know how to get a value with roughly the right number of digits.)

Chrizz said:
Btw quantum computers can do many things at once right? They can check every solution for a scramble at the same time (if I'm understanding it correctly), so maybe we will be able to brute force God's number for the 4x4 within the next 10 or 20 years.
Click to expand...
Unfortunately, you're not understanding correctly. :-(

Quantum computers can only apply "parallelism" for problems with a certain structure. I don't know of any reasoning that suggests you can frame calculating optimal solutions or God's number using this structure.
 
Chrizz said:
If God's number for 2x2 and 3x3 had been calculated rather than brute forced, a formula may be possible to setup for any nxnxn cube.
Click to expand...
Too bad those numbers weren't calculated, then :p There may eventually be a way to directly determine the diameter of a permutation group (that is, God's Number for a puzzle) but it isn't known yet.

Lucas Garron said:
Quantum computers can only apply "parallelism" for problems with a certain structure. I don't know of any reasoning that suggests you can frame calculating optimal solutions or God's number using this structure.
Click to expand...
Well, with sufficiently large memory and enough parallelism you can compute a God's Algorithm in one step per move. I'm sure you can guess what algorithm I'm thinking of.
 
Lucas Garron said:
Unfortunately, no one has any idea whether a simple formula exists or what it would look like.
(Although we know how to get a value with roughly the right number of digits.)
Click to expand...
One of their results is that solving a single face of the nxnxn cube requires roughly the same number of moves it takes to solve the entire puzzle. Has anyone looked in to calculating the number of required moves it takes to solve one face of the 4x4x4, for example. (I know Bruce Norskog did such a search for the first center of the 5x5x5.) Clearly this is more accurate as n gets large, but I'm just curious.
 
Lucas Garron said:
Unfortunately, you're not understanding correctly. :-(

Quantum computers can only apply "parallelism" for problems with a certain structure. I don't know of any reasoning that suggests you can frame calculating optimal solutions or God's number using this structure.
Click to expand...

I read the article and I see that quantum computers would still take a long time to solve the problem, however, I do think that quantum computers are better at this than classical computers. In the article it says that you can reduce the time to find the solution to a problem from S/2 to √S. That obviously wouldn't be a significant enough reduction to calculate it with a today's computer, but it would be an improvement.
They also say that quantum computers exploit certain mathematical properties of the problem, which to me sounds like we should first know what the structure of the problem is, something we don't know as far as I know.

I think I'll have to revise my guess and say that it will be calculated before it will be brute forced.
 
I think God's Number for the 4x4x4 is 32.

I extended the recursive accumulator for unique 4x4x4 positions out this far. I noticed at depth 31, you get

470,703,927,480,007,324,417,289,104,727,084,394,384,064,512

...and at depth 32, you get

12,875,779,855,238,747,700,213,127,810,947,408,348,230,811,648.

If there are 7,401,196,841,564,901,869,874,093,974,498,574,336,000,000,000 unique arrangements, then the total arrangements possible at depth 31 is too small to represent this number, and the depth 32 count is finally greater than it. I'm not sure at what point the cumulative total exceeds it, but to err on the side of caution, we can set 32 as the safe upper bound

I have the numbers for depths 1 to 16 listed here:

http://lightningcloudcomputing.com/OO_4x4x4/info_05.shtml

I'll fill the rest of them in later.
 
There was a post here last night that said "do the same for 3x3."
I'd like that as well, to show some sort of consistency.

What you're doing is obviously above my head at this point, but seeing consistency with KNOWN 2x2 and 3x3 numbers would shed some belief. As is, it kinda seems like magic to get this number so soon.
 
StachuK1992 said:
There was a post here last night that said "do the same for 3x3."
I'd like that as well, to show some sort of consistency.

What you're doing is obviously above my head at this point, but seeing consistency with KNOWN 2x2 and 3x3 numbers would shed some belief. As is, it kinda seems like magic to get this number so soon.
Click to expand...

I get these numbers for the 3x3x3:

depth 18 = 246,639,261,965,462,754,048
depth 19 = 3,292,256,598,848,819,251,200
depth 20 = 43,946,585,901,564,160,587,264

The number typically quoted for all 3x3x3 arrangements = 43,252,003,274,489,856,000 which looks promising, until you count the commas. Somehow, there are 1000 times as many positions at depth 20 as there are in this number.

So perhaps my supposition about the 4x4x4 is likewise off, or the 3x3x3 numbers I have are not correct.
 
Last edited:
StachuK1992 said:
Damn.
Click to expand...

Not necessarily a setback. If an order of magnitude above the permutation count is needed, just add 2 more to my number, and you get God's Number for the 4x4x4 is 34. Coming up with a proof would be the hard part, but at least we have a guideline in place that we didn't have before yesterday.
 
That kind of computation has been done before by several people. It's important to note it does depend exactly on what metric you use (especially for big cubes). It's a great way to get a lower bound on God's Number but I really don't recommend trying to estimate the actual number by adding an extra term to it.
 
qqwref said:
That kind of computation has been done before by several people.
Click to expand...

I haven't come across any. Are there any existing links you could point me to for now?

qqwref said:
It's important to note it does depend exactly on what metric you use (especially for big cubes). It's a great way to get a lower bound on God's Number but I really don't recommend trying to estimate the actual number by adding an extra term to it.
Click to expand...

So has a lower bound of 32 already been established based on what you mentioned?

I was counting moves such as R, R', and R2 as 1 turn. Ditto for slice moves.
 
unsolved said:
I haven't come across any. Are there any existing links you could point me to for now?
Click to expand...
From googling "god's number lower bound": http://en.wikipedia.org/wiki/Optimal_solutions_for_Rubik's_Cube#Lower_bounds, www.cube20.org/, http://cubezzz.dyndns.org/drupal/?q=node/view/54, http://www.math.rwth-aachen.de/~Mar..._Hoey__Lower_bounds_for_the_4x4x4_(Long).html, https://www.speedsolving.com/forum/...4-Rubik-s-cube&p=725532&viewfull=1#post725532, https://www.speedsolving.com/forum/...od-s-number-is&p=650846&viewfull=1#post650846. I'm sure you can find more and I'm sure these are not all exactly the same approach.

I've also done similar calculations myself; a document with last modified date of mid 2010 lists numbers of 34 for the 4x4x4, 40 for the 4x4x4 supercube, 43 for the megaminx, 50 for the 5x5x5, 63 for the 5x5x5 supercube, 73 for the 6x6x6, 92 for the 6x6x6 supercube, 95 for the 7x7x7, 125 for the 7x7x7 supercube, 135 for the gigaminx, etc. Some of these may be off by one due to only taking the number of positions at a given depth into account rather than taking the sum of positions of depths up to that depth (a silly mistake, but the number of positions grows exponentially with a large base anyway, so it doesn't matter all that much :p).

unsolved said:
So has a lower bound of 32 already been established based on what you mentioned?
Click to expand...
I don't have the numbers memorized since it depends exactly on what metric choice you use (there are many possibilities) and is ultimately not very useful.
 
 
You must log in or register to reply here.

Similar threads

J
Gods number 4x4
Replies
1
Views
1,715
shadowslice e
shadowslice e
S
God's Number for 4x4 Found!
3 4 5
Replies
93
Views
12,844
Jaycee
Jaycee
B
God's number for the FTO
Replies
10
Views
817
BadDisplayName
B
iguana
What is God's number for a 3-gen scramble?
Replies
8
Views
648
Bruce MacKenzie
Bruce MacKenzie
A
4x4x4 OBTM (WTM) upper bound improved from 55 to 54
Replies
1
Views
453
SpeedCubingLord
SpeedCubingLord
Back
Top