# Predicting God's Number for Higher Order Cubes



## spyr0th3dr4g0n (Sep 19, 2016)

I plotted the natural log of the number of states per moves to solve, and got a nice trend.

Taking data from this site for the 2x2x2


Spoiler: 2x2x2 qtm












Taking data from cube20 and making a similar plot


Spoiler: 3x3x3 htm











We can see from the graph that the 3x3x3 approximations look like they might underestimate 16 moves and over estimate 18 moves, but they are otherwise fairly accurate.

Plotting using the same function for 2x2x2 htm gives a similar looking curve.

Is there any reason this trend shouldn't continue for higher order cubes? Is there any data for the number of states per optimal moves to solve for 4x4x4 cubes?



Spoiler: 2x2x2 data





```
0    1    0
1    6    1.791759469
2    27    3.295836866
3    120    4.787491743
4    534    6.280395839
5    2256    7.721348613
6    8969    9.101529466
7    33058    10.40601887
8    114149    11.64525989
9    360508    12.79526943
10    930588    13.74357192
11    1350852    14.11624606
12    782536    13.57029521
13    90280    11.41067123
14    276    5.620400866
```






Spoiler: 3x3x3 data





```
0    1    0
1    18    2.890371758
2    243    5.493061443
3    3240    8.083328609
4    43239    10.67449814
5    574908    13.26196531
6    7618438    15.84608192
7    100803036    18.42867903
8    1332343288    21.0102051
9    17596479795    23.59096471
10    2.32248E+11    26.17107188
11    3.06329E+12    28.75051023
12    4.03744E+13    31.32921767
13    5.31653E+14    33.90701292
14    6.98932E+15    36.48315975
15    9.13651E+16    39.05364047
16    1.1E+18    41.54184185
17    1.2E+19    43.93143832
18    2.9E+19    44.8138275
19    1.5E+18    41.85199678
20    490000000    20.00991595
```


----------



## AlphaSheep (Sep 19, 2016)

I'm not sure what trend you're talking about but just to explain what you're looking at, there are two things that determine how many states are at a given depth.

The number of possible move combinations at a depth. This grows exponentially, so it will appear as a straight line on a log plot.
The number of states that have not yet been reached. This starts off as the maximum number of states and drops off to zero at God's number.
What your graphs show is a long linear part where 1 dominates (i.e. adding a move is likely to produce a new state) followed by a rapid drop off where 2 dominates (adding a new move is likely to reach a state that another move sequence already reached). All NxNxN cubes have this behaviour, and so do all puzzles without weird move restrictions. 

1 is very easy to calculate for higher order cubes, although the numbers get very large very quickly. I don't know if you can calculate 2 without brute force, but you can easily get a lower bound using the total number of states and subtract the number of move sequences calculated in 1. That can give you a lower bound on God's number for any puzzle.

No, there's not much information for the number of states at each move depth on 4x4 and up. In fact, even the 3x3 data you give is incomplete for the last depths.


----------



## spyr0th3dr4g0n (Sep 19, 2016)

And would it be worth doing the brute force for 4x4x4 to get a better estimate than the lower bounds? Has someone done it before? Thanks for the reply, that's good news that it should hold, and your logic seems good.


----------



## AlphaSheep (Sep 19, 2016)

Doing the brute force for 4x4 would take too long (like millions of years too long). 

Lower bounds have been calculated for God's number for up to a 20x20.


----------



## spyr0th3dr4g0n (Sep 19, 2016)

Thanks for the link, that helps a lot. Bruteforcing would take a long long time yes, but an approximation could be gotten by only working on a subset of the total possible states, for instance generating (uniformly?) and solving a large amount of 4x4x4 states and extending the reusults. My aim is only to have a guess that is better than the current lower bounds, not an exact figure.


----------



## xyzzy (Sep 19, 2016)

Optimally solving even one random state on 4x4x4 is expected to require years of CPU time, as mentioned on cube20.org, and the situation only gets worse on larger cubes. However, I think that by solving just a handful of random 4x4x4 states optimally, we should be able to improve the lower bound by a few moves.

(We do have upper bounds of 55 OBTM for 4x4x4 and 143 OBTM for the 5x5x5; I don't know if larger cubes have been analysed in detail.)


----------



## spyr0th3dr4g0n (Sep 20, 2016)

But with more modern software does it still take years to produce an answer for a single random cube state?


----------



## stoic (Sep 20, 2016)

spyr0th3dr4g0n said:


> But with more modern software does it still take years to produce an answer for a single random cube state?


Improving the software can only do so much; actually processing the required number of calculations is a hardware problem.

I'd be interested if anyone has attempted a guess at how long we should have to wait until Moore's Law kicks in sufficiently.


----------



## tseitsei (Sep 20, 2016)

stoic said:


> Improving the software can only do so much; actually processing the required number of calculations is a hardware problem.
> 
> I'd be interested if anyone has attempted a guess at how long we should have to wait until Moore's Law kicks in sufficiently.


Moore's law will stop working soon since transistors are getting so small that the size of atoms is actually becoming a limiting factor sometime soon.

IMO our hopes lies more with quantum computers... They should be great for this kind of thing since we should be able to simultaneously test many many move(sequences) instead of just one at the time. But I'm not an expert on that subject so I might be totally wrong here...


----------

