Home »

Number of maneuvers for Rubik's Cube

Submitted by Herbert Kociemba on Sat, 05/19/2007 - 10:35.
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.
» login or register to post comments | previous forum topic | next forum topic

Comment viewing options

Select your preferred way to display the comments and click 'Save settings' to activate your changes.

Cube Lovers Bounds

Submitted by Jerry Bryan on Sun, 05/20/2007 - 21:01.
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.
» login or register to post comments

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

Submitted by Herbert Kociemba on Sat, 05/19/2007 - 10:38.
Sorry, should be Round[(3+r)(6+3r)^n /4]
» login or register to post comments

A little explanation

Submitted by jaap on Sat, 05/19/2007 - 12:43.
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/
» login or register to post comments

Boundary Conditions

Submitted by Jerry Bryan on Sun, 05/20/2007 - 22:16.
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.
» login or register to post comments

You are right, I overlooked t

Submitted by Herbert Kociemba on Sat, 05/19/2007 - 13:17.
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
» login or register to post comments

Complication is in the eye of the beholder

Submitted by Mike G on Mon, 05/21/2007 - 09:17.
> 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.
» login or register to post comments