# How many ways to optimally solve a given positon?



## guysensei1 (Jun 17, 2014)

I was thinking about how many ways there are to optimally solve a given position on the rubik's cube (as you may have guessed from the title).

I was considering counting mirrors, inverses, and rotated algs to be the 'same' solution, but then I'm not sure if this is a reasonable thing to do, as some of these rules only work on symmetric positions.


Any input from the more mathematically inclined people here?


----------



## CHJ (Jun 17, 2014)

i know at least 4 optimal Y-perms that are all different completely if that helps


----------



## guysensei1 (Jun 17, 2014)

CHJ said:


> i know at least 4 optimal Y-perms that are all different completely if that helps



There has got to be more optimal solutions than that right? Cubeexplorer lists 24 optimal Y perms. Haven't checked for the presence of inverses yet.


----------



## CHJ (Jun 17, 2014)

guysensei1 said:


> There has got to be more optimal solutions than that right? Cubeexplorer lists 24 optimal Y perms. Haven't checked for the presence of inverses yet.



cubeexplorer usually adds in a load of inverses and such, i just wanna learn all the optimals personally


----------



## Kirjava (Jun 17, 2014)

Don't think there's a known way of working this out outside of brute force.


----------



## Lucas Garron (Jun 17, 2014)

I don't know at all. This will probably depend on quite a few factors.

Commutators will usually have many ways of doing things, and positions closer to solved are likelier to have multiple optimal commutator algs.
I have no idea how symmetry would affect this (apart from having a lot of optimal algs that are mirror/inverse/otherwise symmetric).

It would be interesting to run this for all states close to solved, and also for a lot of random states.
I don't even know how much longer Kociemba will take to find all optimal solutions.


----------



## rokicki (Jun 17, 2014)

You can get very close to an approximate answer to this, on average, for
some interesting cases, just by comparing the count of canonical sequences
of length $n$ and the number of positions at distance $n$.

For small $n$ these are very close. For instance, for $n=15$, there are
103,697,388,221,736,960 canonical sequences and 91,365,146,187,124,313
positions. That means most distance-14 positions have only a single
optimal solution; indeed, at least 86% of them do. On average, there are
about 1.13 optimal solutions per position at distance 14. This logic also
shows that most length-14 canonical sequences are optimal.

Conversely, at distance 18, the story changes a bit. There are about
29 billion billion positions at this distance, and 246.6 billion billion canonical
sequences. Not all those sequences lead to positions of distance 18, but
the majority do, so at distance 18 you're going to see an average of
probably somewhere around 8 optimal solutions per sequence.

For distance 19 and distance 20 positions, the number of optimal solutions
goes up tremendously.

Through distance 3, canonical sequences of length $n$ and positions at
distance $n$ are exactly 1:1.


----------



## guysensei1 (Jun 17, 2014)

rokicki said:


> You can get very close to an approximate answer to this, on average, for
> some interesting cases, just by comparing the count of canonical sequences
> of length $n$ and the number of positions at distance $n$.
> 
> ...



Nice analysis! 

Can you give an example of a distance 14 position and its 2 optimal solutions?


Is 14 the smallest number for multiple optimal solutions?


----------



## rokicki (Jun 17, 2014)

Howdy!

Offhand, no, but I could do some searches.

The smallest distance for which there is a position with multiple
optimal solutions is of course our old squares group friend

U2D2F2B2

and variations, because (U2D2) commutes with (F2B2) so you
can solve it also as

F2B2U2D2

The notion of "canonical sequence" is not sufficiently strong to
capture this case.

Of course from this you can construct any number of longer
solutions. For instance, just winging it here, but I'd be fairly
certain that

F2B2 R2L2 UFRDBLUFRD

is an example of a distance-14 optimal sequence that leads
to a position with more than one canonical optimal solution
(just swap F2B2 and R2L2 in the solution). (Confirmed, yes,
this is indeed an optimal sequence.)

Calculating *all* optimal solutions for a distance-19 position could
take quite a while. One reason optimal solvers can find solutions
to distance-19 positions so quickly is because there are so many
such optimal solutions; any first move likely turns the distance-19
position into a distance-18 position, so not much of the tree need
be searched.

And for distance 20, to do a full ply-20 search, even with my
high-powered, 176GB-pruning-table, 32-thread optimal solver,
could take a while. Might be worth giving it a shot though. For
averages, distance-20 positions are statistically insignificant;
only distances 15 through 19 really need be considered.


----------



## guysensei1 (Jun 18, 2014)

rokicki said:


> Howdy!
> 
> Offhand, no, but I could do some searches.
> 
> ...



I had an epiphany regarding my own question, the actual shortest scramble with 2 optimal solutions is R L.


----------



## Renslay (Jun 18, 2014)

guysensei1 said:


> Nice analysis!
> 
> Can you give an example of a distance 14 position and its 2 optimal solutions?
> 
> ...




The shortest movements which are not identical in a trivial way, yet has the same effect on the cube have a length of 6. I cannot prove this; and we have to define "trivially identical move sequences". But I think two sequences are trivially identical if they can be transfered into each other with basic steps such as cube rotations (F x = x U), swapping commutative sub-steps (R L = L R), expanding middle layer turns into outer layer turns (M = R L' x'), and merging multiple layer turns (U U2 = U'). Maybe a few more.

An example for a 6 step non-trivial identity:
R' U R' F R F'
=
B U' B' U R' U

Which means R' U R' F R F' (B U' B' U R' U)' = R' U R' F R F' U' R U' B U B' = id.
(There are many more 6 move examples).

So, is this the state with shortest multiple non-trivially identical solutions?


----------



## Lucas Garron (Jun 18, 2014)

Renslay said:


> So, is this the state with shortest multiple non-trivially identical solutions?



Not in HTM.
R U R' F' U2
U2 F' L' U L 


Also, there's a fairly standard way to measure "identical sequences", as Tom mentions. Look for him and Kociemba talking about "canonical sequences" on this forum.


----------



## Renslay (Jun 18, 2014)

Lucas Garron said:


> Not in HTM.
> R U R' F' U2
> U2 F' L' U L
> 
> ...



Very nice! I did not aware of 5 move pairs.

Yes, the definition of canonical sequences is something like that I want. However, as Rokicki pointed out, it does not cover cases like U2 D2 F2 B2 = F2 B2 U2 D2, which I feel still is a trivial identity, because with basic transformations I can get:
U2 D2 F2 B2 = E2 y2 S2 z2 = y2 E2 S2 z2 = y2 S2 E2 z2 = (...) = S2 z2 E2 y2 = F2 B2 U2 D2.


----------



## rokicki (Jun 18, 2014)

Renslay said:


> Yes, the definition of canonical sequences is something like that I want. However, as Rokicki pointed out, it does not cover cases like U2 D2 F2 B2 = F2 B2 U2 D2, which I feel still is a trivial identity, because with basic transformations I can get:
> U2 D2 F2 B2 = E2 y2 S2 z2 = y2 E2 S2 z2 = y2 S2 E2 z2 = (...) = S2 z2 E2 y2 = F2 B2 U2 D2.



Canonical sequences are based on a very simple principle: adjacent commuting moves have a single
preferred order.

For the half-turn and quarter-turn metric, the close correspondence between the count of sequences
of length $n$ and positions at distance $n$ with this simple definition means that search can be
performed effectively using this simple definition.

In the slice-turn metric, things get a little messier. S2 and E2 commute in the slice-turn metric, but
the reduction to a single canonical sequence is more complicated since they cross syllables. In the
HTM and QTM, the only commuting moves are in the same syllable so the reduction is straightforward.
However, in the STM, we end up with things like this:

U2 S2 E2 F2

If "S2 E2" is the preferred order for those commuting moves, we cannot reduce this further by
inspection only of adjacent moves. But if we can flip those, we get

U2 E2 S2 F2

which of course can be reduced to

D2 B2 z2

but this reduction requires a bit more complexity. And as it turns out, the reduction in search
space, even in the slice-turn metric, is not all that great. Is it worth it? Perhaps.

So I guess what we lack most here is how you define "triviality" of an identity. The pair
pointed out by Lucas comes from the fact that the position he shows is antisymmetric, so
the second move sequence is just the inverse of the first but reoriented.


----------

