# Number of maneuvers for Rubik's Cube

By accident I just ran across a formula I developed many years ago for the number of maneuvers in FTM which cannot be shortened in a trivial way. I did not see it anywhere else, so maybe it is of some interest.

Let r = Sqrt(6) and k the maneuver length, then we have

N(k) = [(3+r)(6+3r)^n + (3-r)(6-3r)^n]/4

which gives 1, 18, 243, 3240, 43254, ...

Round[(3+r)(6+3r)^n] is a good approximation even for small n. and we see that 6+3r = 13.348... is the asymtotic branching factor.

## Comment viewing options

### Cube Lovers Bounds

The best Cube Lovers bounds may be found at:

http://www.math.rwth-aachen.de/~Martin.Schoenert/Cube-Lovers/Dan_Hoey__The_Supergroup_--_Part_2__At_least_25_qtw,_and_why.html

http://www.math.rwth-aachen.de/~Martin.Schoenert/Cube-Lovers/Dan_Hoey__Re__Updated_Upper_Limits,_Q-turns.html

http://www.math.rwth-aachen.de/~Martin.Schoenert/Cube-Lovers/Dan_Hoey__Re__lower_bounds.html

The first two messages address the quarter turn metric. The last message addresses the face turn metric.

### Sorry, should be Round[(3+r)(

Sorry, should be Round[(3+r)(6+3r)^n /4]

### A little explanation

That's quite nice.

I assume you first constructed the recurrence relation:

s(n) = 3*4*s(n-1) + 3*3*2*s(n-2)

Here I use s(n) for the number of manoeuvres of length n. The last two moves of the move sequence are either adjacent or opposite faces. If adjacent, you simply extend a sequence of n-1 moves with a move on one of the 4 faces adjacent to the last move. This gives the first term.
If opposite, you extend a sequence of n-2 moves with two opposing moves on one of the 2 axes other than the last move. This gives the last term.

Put in the boundary conditions:
s(1) = 18
s(2) = 243

and you get your formula. Unfortunately the formula gives s(0)=3/2, but that is because the relation breaks down:

s(2) = 3*4*s(1) + 3*3*3*s(0)

There is a factor 3 instead of 2 in the last term because there is no previous move and all 3 axes are available for the pair of opposite moves.

Jaap
Jaap's Puzzle Page: http://www.geocities.com/jaapsch/puzzles/

### Boundary Conditions

When I have played with this before, I have come the conclusion that the asymptotic branching factor turns out to be the same, irrespective of what boundary conditions are used. Obviously, it's nice to use the correct boundary conditions, but you get the same asymptotic branching factor even if you don't.

This has some interesting implications if you start with what is known and project out to what is not known. For example, the number of positions is currently known out to 11 face turns from Start. The actual branching factor tends to decline slightly as you get further from Start, until finally it declines sharply as you get close to the diameter. The decline in actual branching factor corresponds to an increased number of duplicate positions as you get further from Start, which in turn corresponds to the effects of longer relations (c.f., the recent thread on Irreducible Loops).

For example, the actual branching factor from 10f to 11f is about 13.19..., which is a bit less than the asymptote of about 13.348... The 13.19... figure is 3063288809012/232248063316. But if you plug in 232248063316 and 3063288809012 as boundary conditions, then both Herbert's formula and Dan Hoey's formula quickly revert back to the asymptotic branching factor of about 13.384 if you project out to 12f from Start, 13f from Start, 14f from Start, etc.

I have wondered if it might be possible to come up with a formula that actually isn't asymptotic, and that reflects different boundary conditions. In other words, might it be possible to come up with a formula where the projected branching factor would continue to decline further from Start. For example, starting with the actual branching factor of about 13.19... going from 10f to 11f, might it be possible to find a formula for which the projected branching factor would continue to decline in going to 12f, 13f, 14f, etc. I have a few very rough ideas, but I'll put the details in a separate thread.

### You are right, I overlooked t

You are right, I overlooked that N(0) gives 3/2.
My way was a bit more complicated, I startet with a(1)=9 and b(1)=9 and used the recurrence

a(n+1) = 6*a(n) + 9*b(n) and
b(n+1) = 6*a(n) + 6*b(n)

Herbert

### Complication is in the eye of the beholder

> My way was a bit more complicated

...but it has the advantage that the boundary condition is simpler. (I used the same method, btw, after failing to understand the description in Singmaster's Notes.)

It would be nice if this were done for a shape-changing puzzle such as Square-1. It's no more difficult -- in principle! -- but the matrix M on the r.h.s. of

(vector) a(n+1) = M.a(n)

is large, because of the multiplicity of shapes, and its eigenvalues and eigenvectors would (probably) have to be found numerically. As in the case of the Cube, the asymptotic b.r. will just be the largest eigenvalue of M.