From:

~~~ Subject:

in fact, you can eliminate the possibility of starting with F2, R2 or U2,

since these each commute with superfliptwist, and may be done in stage 2.

in other words, if F2 sequence = superfliptwist, then also

sequence F2 = superfliptwist.

Right. I had not considered this in the program (it is still fairly

general), but it only does mean early termination.

also, you need not consider 19 turns in stage 1. by symmetry, you may

suppose the last face turned is U, which is done in stage 2.

But I have now had different thoughts. Currently phase 1 checks in 3

dimensional space. When a solution is found the program calculates the

current position for phase two after which it finds a solution in a

different 3 dimensional space. (I just though how I might speed up the

calculations to get to the starting position for the second phase,

but will not yet elaborate on that; I will first try it out.) But this

does not help finding whether there are solutions of 19 turns or less.

What I am now considering is to have a phase 1 program only, where phase

1 is done in an additional dimension: the permutation of the corner cubes.

So to prove the non-existence of a solution of 19 turns or less, this

program would seek for a phase 1 solution in 4 dimensional space of at

most 19 turns and next check whether this also solves the edge cubes.

This would eliminate quite a few dead alleys where the current phase 1

finds a solution and has still things to do.

if you use the fact that U and D commute, L and R commute and F and B

commute, then the number of sequences of length n in stage 1 grows

exponentially, with ratio approximately 13.35. if the runtime is

proportional to the number of sequences tested in stage 1, (which

may or may not be the case) that would mean testing 18 turns deep

would take approximately 178.18 times as long. (eliminating the

possibility of starting with F2, R2 or U2 would cut that in half.)

If I use a single phase algorithm, I can eliminate much more! What I

see for runtime is not entirely proportional. When looking at the

number of configurations done in phase 2, this goes up by factors that

start in the neighbourhood of 30 and diminish to (probably) ultimately

the factor you mention. This indicates that tree pruning is much more

effective with fewer turns in phase 1.

here's something you may have already considered. if your prune tables

in stage 1 consider only pairs (flip, twist), (flip, location) and

(twist, location), some search paths may be pruned 8 turns early.

(each of these pairs had positions 9 twists from start.) at the

expense of a lot more memory, you can do some pruning 11 turns early,

by storing tables for triples (flip, twist, location). you'd probably

have to store these tables in very compressed form, and divide out by

symmetries of the cube that preserve the U-D axis. it may turn out

that the overhead of processing this compressed information does not

adequately compensate for the improved foresight, but it's worth

considering.

I think the overhead is much to large computation-wise and memory-wise.

The size of the table would be uncompressed 2217093120 integers in the

range from 0 to 12. Factoring out symmetries would reduce it by a factor

of about 32 (slightly less). [4 for rotational symmetry, 4 for mirroring

both U-D and F-B, 2 for inversion.] Using 3.5 bits per configuration

this means > 30 MByte. The machines I am using currently are not able

to handle that amount of information. But it is feasable. If we skip

inversion (which is most difficult to do) we are at > 60 MByte. The

problem remains to adequately number the remaining positions from 1 to

max. Some configurations are inert with respect to the rotations and/or

mirroring. On the other hand, we need the table in core (do not try

to do this through disk access!). Some insightful thoughts are needed

here.

it would be excellent if you could show that 20 face turns is minimal

for superfliptwist! even finding a shorter solution would be great!

I agree to that! I have a number of machines, still going strong.