qqwref
Legend
- Joined
- Dec 18, 2007
- Messages
- 7,834
- Location
- a <script> tag near you
- WCA ID
- 2006GOTT01
- YouTube
- Visit Channel
What? (Remember that my method only gives a lower bound for the God's Algorithm number - so for example we know that the depth of the 4x4 is somewhere between 31 (as per my calculations) and 77 (Norskog's Thistlethwaite-style solver).
Er... not really. (By the way 2R is M in my notation, and the singular of "axes" is "axis".) You've come close to the basic approximation, though. A 3x3 cube has 6 faces, and each face has 3 moves. Since scrambles never put the same face twice in a row the number of possibilities in this basic approximation is 18 * 15^(n-1) for n moves. This is very easy to calculate and very simple to use, since you can even use logarithms to avoid explicitly calculating it out for any n.
However there is a more complicated approximation which I was talking about, which takes into account the fact that after doing a series of moves along the same axis we cannot use a slice on that axis that was already used. This doesn't make a difference on the 3x3 but it does provide a better lower bound on larger cubes and the Megaminx (and besides we don't care about 3x3 really because a lower bound of 20 is known
). I'll describe it more closely: we have a recurrence relation with two sequences, a and b. We will let a_n be the number of scrambles of length n which end in just one turn from the axis, and b_n be the number of scrambles of length n which end in two turns from an axis (like U' D2). Then the recurrence relation is:a_1 = 18, b_1 = 0
a_n := 12 * a_(n-1) + 12 * b_(n-1)
b_n := 3 * a_(n-1)
Note that the 12s are because there are 4 possible faces that are not on a given axis, and to get a_n we must have changed axis right before the last term. Anyway this gives a very precise count of the number of scrambles we can generate: the number of scrambles for n moves is just a_n + b_n. This becomes a bit more tricky for larger cubes because an NxNxN cube needs N-1 of these sequences. For example on the 5x5x5 we have sequences a, b, c, d and
a_1 = 36, b_1 = 0, c_1 = 0, d_1 = 0
a_n := 24 * a_(n-1) + 24 * b_(n-1) + 24 * c_(n-1) + 24 * d_(n-1)
b_n := 9 * a_(n-1)
c_n := 6 * b_(n-1)
d_n := 3 * c_(n-1)
So the basic approximation is okay, but this calculation will give you an exact value for the number of scrambles. Recurrence relations like these can be created for any puzzle, but they get rather complicated (for example the megaminx has 4 and I imagine the gigaminx would have even more).
Well yes, the approximation for 7x7 is 54 * 51^(n-1) for n moves. But as you can see the larger the cube the higher chance that the same-axis slices will get in the way of each other. Interestingly there are some scramblers which change axis after every turn; that would actually reduce the number of possibilities to 54 * 36^(n-1), which is not an approximation since turns don't affect future possible turns at all. Intriguingly this would mean that we now need 102 moves to scramble a 7x7
As far as the growth of the optimal number of turns, I think we are way too far away from that kind of knowledge to even make a decent guess at it. All I have are a couple of lower bounds with absolutely no guarantee of how close they are, and for even the 4x4 it is quite difficult to get a better lower bound (you might have to optimally solve positions) or to get a decent upper bound (since you need some kind of solution method to prove that, assuming you don't have an optimal solver). So unless we can know more about at the very least the 4x4 I don't think it it is reasonable to guess a pattern based on 2x2 and 3x3. However, taking the complete and total guess that the number of moves is about three more than predicted in my calculation, I think something like
1/2 (5 (N-1)^2 + 3 (N-1) + 14) = 1/2 (5 N^2 - 7 N + 16)
for an NxNxN cube (N >= 2) might fit reasonably well. It's likely to be more or less quadratic, although of course it probably won't follow a simple sequence such as this.
