A plan to settle the maximin distance problem so we can all go home

I outline an approach which may be able to determine the maximin depth of the Rubik cube R - may be able to prove the answer is 20 face turns - with a feasible amount of computer time.

Because R has 4.3*10^19 configurations, exhaustive search is not feasible.

At present at least 10000 configurations are known (including the "superflip") that require 20 face-turns (20f) to solve.

Silviu Radu has a proof at at most 27f are necessary.

So the answer is somewhere in [20, 27]. What is it?

H.Kociemba's "two phase solver" works by first getting into the H = subgroup (which is known to be possible in at most 12f because of an exhaustive search of R/H) and then solving (which is known to be possible in at most 18f because of an exhaustive search of H) thus proving an upper bound of 30f.

Those exhaustive searches were possible because
cardinality(H) = 8!^2*4!/2 = 19508428800
cardinality(R/H) = 3^7*2^11*12!/8!/4! = 2217093120
both are small enough, although pretty big.

However, Kociemba has apparently claimed that a slightly enhanced version of his solver has (so far) never needed more than 20f to solve. It works by finding not only one best way to get into H, but also other (perhaps including suboptimal) ways, and then solving all the H-positions that result.

Fine. So my suggestion is simply to try to turn that empirical experience into a theorem.

Associate each member m of R/H with the (say) 100 shortest ways to get it into H. (Note: it may be necessary to tune the value of "100" and to make it m-dependent.) These 100 ways (i.e. faceturn sequences), and their costs (i.e. faceturn counts) are rapidly found assuming we have precomputed an enormous table giving, for each coset in R/H, its distance to H.

Now, we have (for any given m in R/H) a collection P[m] of 100 permutations in R, which relate the 100 closest members of H it can reach, and associated with each of these 100 members p of P[m] we know its cost C[p]. Let pbest be one of the min-cost perms.

Now the CONJECTURE is that, no matter what m you pick, and no matter what member h of H you pick, at least one of the 100 members p of P[m] has the property that p*pbest'*h (where the * denotes permutation multiplication and ' denotes inverse perm) is within H-distance <=20-C[p] of the start position.

This conjecture (for any given m) may be confirmed as follows. Assume for a contradiction that it is false. Then we can wlog restrict attention to the small subset of h in H such that h is at distance >=21-C[pbest] from start. This small set is immdiately known assuming we have a precomputed enormous table of H elements and their distances to start. We now can restrict attention to the even smaller subsubset of h in H such that psecondbest*pbest'*h also is at distance >=21-C[psecondbest] from start. And so on. We keep going in this way to pthirdbest etc, and as soon as the set-intersection reaches zero size, we are done and the conjecture is confirmed for that m.

We do this for every m. If this all succeeds, the result will be a proof that the Rubik cube is soluble in 20f, and also a proof that (some flavor of) Kociemba's algorithm will always work in <=20f.

One form of the algorithm may be summarized as:
(i) build R/H distance table
(ii) build H distance table
(iii) for each m in R/H (and we may also mod out by whole-body-rotations etc of the cube):
| find pbest[m] and its cost C[pbest]
| find the members h of H at distance >=21-C[pbest] from I
| for each such h
|| generate perms p giving short ways to get from m into H
||| if one found so dist(p*pbest'*h) <= 20-C[p]
||| then cross that h off the list and move on to the next h


If it fails, then
(a) you can try the (hopefully few) failure (m,h)'s with larger values of "100" and/or larger values of "20" and hopefully still will get a pretty strong upper bound
(b) you will know some particularly nasty m's and h's to use to try to generate a 21f configuration...

How much computing this will take is an open question... but I suspect it is within reach. The few far members h of H are best stored in hash tables in RAM to avoid the need for slow disk accesses (non-presence in the hash tables ==> close) and the outer loop over m may be done in parallel on many machines. These plausibly will make a proof possible in a few years (?) of computing. You could make it more attractive for volunteers if you could figure out a way to do it with smaller tables in most cases (with hard cases being uploaded to those rarer machines that are willing to work harder and use more disk)...

Perhaps some of you can refine and analyse this game plan further...

Warren D Smith
http://math.temple.edu/~wds/homepage/works.html
http://math.temple.edu/~wds/crv
warren.wds /at/ gmail.com

Comment viewing options

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

some more comments

H.Kociemba sent me some emails to educate me about some of the
weaknesses in my suggested cube-diameter-establishing method.

Unfortunately HK prefers to keep that correspondence private,
but the rough conclusion is that there are several ideas that I
was unfamiliar with, which could be used to improve my suggested
approach both in terms of speed and in terms of memory consumption;
and it appears Rokicki already has some code that does something vaguely similar
to what I was suggesting (although I do not know quite what);
and Kociemba estimates (necessarily crudely) that 16000 PC-years
of computing would suffice to establish the cube-diameter.
Far more than that amount of resources is available if you organize something like
GIMPS
but that is not a trivial job.

I think considerably more analysis both mental and software is needed on
this issue before GIMPing it would become reasonable, and it seems to me
it would be best for that analysis to be conducted in the open on this forum.

feasibility analysis

OK, I looked up some data on the www and did some feasibility analysis of my plan to try to determine the maximin cube configuration and hopefully prove it is 20f (the superflip). Let us examine some data:
Dik T. Winter (24 May 1992, corrected on May 28)  
calculated the following exhaustive H coset in R
distance distribution:
  0f          1
  1f          4
  2f         50
  3f        592
  4f       7156
  5f      87236
  6f    1043817
  7f   12070278
  8f  124946368
  9f  821605960
 10f 1199128738
 11f   58202444
 12f        476
tot= 2,217,093,120
One apparent deficiency of this calculation was that it used only the 18 moves (U,D,R,L,F,B)^{1, -1, 2} at distance=1 and did NOT use the 24 cube-body-rotation moves with distance=0. If the latter had been used (which makes a difference because H is not symmetric under cube-body-rotations) then quite probably distances would have decreased.

The entire R/H set of 2.2 billion distances can thus be stored in 1.1 GigaBytes as a table of nybbles (1 nybble = 4 bits) or if you are willing to store only 8 kinds of distances {12,11,10,9, 8,7,6, and <=5} then in only 0.77 GigaBytes as a table of 3-bit numbers. If you manage to hack up a clever indexing scheme (which would probably have to involve a pre-lookup in a specially consructed table with 1000 entries to figure out the indexing) to only tabulate one coset per the 24 in the cube-body-rotation equivalence class then these numbers can be reduced by a factor of about 24 (we only use the best, i.e. least distance, among the 24) or perhaps by a factor of 10 if we also store in the table which of the 24 equiv classes it is - that would take 9 bits per table entry.

Anyhow, the POINT is that this whole table can fit in RAM, doesn't have to be one disk, to get SPEED. Of course, not a lot of people right now have bought 3 GigaBytes of RAM but it can be done, and with the 10X reduction to only 0.11 GBytes, practically everybody has that much RAM.
H = (U, D, F2, B2, R2, L2)  enumeration by distance
by Tomas Rokicki 2006 & Mike Reid 1995 (now indep'yl confirmed)
 d      all moves     moves in H
 0f             1              1
 1f            10             10
 2f            67             67
 3f           456            456
 4f         3,079          3,079
 5f        20,076         19,948
 6f       125,218        123,074
 7f       756,092        736,850
 8f     4,331,124      4,185,118
 9f    23,639,531     22,630,733
10f   122,749,840    116,767,872
11f   582,017,108    552,538,680
12f 2,278,215,506  2,176,344,160
13f 5,790,841,966  5,627,785,188
14f 7,240,785,011  7,172,925,794
15f 3,319,565,322  3,608,731,814
16f   145,107,245    224,058,996
17f       271,112      1,575,608
18f            36          1,352
   -------------- --------------
   19,508,428,800 19,508,428,800
OK, again, these authors apparently have not taken advanatge of 24-way cube-body-rotation symmetry to get a 24-way reduction in storage space, although the table's first column of course does take advantage of that symmetry for the purpose of reducing the faceturn count (since the full group is invariant under the 24 cube-body-rotations even though H is not, H is only invariant under 4 rotations).

Anyhow, we can store the 16,17,and 18f configurations in a big hash table in RAM, they will fit. Indeed, using canonization under the 24-group before hashing, we can even store the 15f configurations too - in maybe 2 GigaBytes total. (Have to have a good hashing scheme; each table entry stores the distance in 2 bits and also a compressed version of the configuration itself in 32 bits, 34 bits total per table entry). This also can fit in RAM not on disk, though you have to buy a lot of RAM.

If you really have a serious budget the entire Rokicki table can be stored in RAM at 1 nybble per entry (no longer need any hashing since whole table is stored) in 9.8 GigaBytes and in only 0.41 GigiBytes if you can dream up a good /24 indexing scheme.

With all this stuff stored in RAM, for most entries in the H-cost table it is going to be possible to prove - without ever leaving RAM - that 8f+14f = 22f suffices using the hashing 15-18 plan (assuming the best of the 6 versions of each coset that arise under 24-way rotation, manage to usually get into the lower 1/6 of the Winter distance distribution, i.e. 8f or less, and since most of the Rocicki distribution is 14f or less). This doesn't seem good enough -- too many disk accesses will be needed to handle the unproven stuff, which'll be too slow, and 22f is above the desired 20f (although perhaps 22f is best possible).

With EVERYTHING in RAM you can totally avoid going to disk, and now we're talking. I then think it might be possible to do the whole calculation on just one PC but if many PCs can work on different chunks of the Winter table in parallel there seems no question the calculation ought to be feasible:

Kociemba http://www.kociemba.homepage.t-online.de/cube.htm says he used his 2phase algorithm to solve 500,000 random cubes and in all cases it took <=20f, and he solved 1000 random cubes optimally finding a max of 19f and an average of 17.7f.

Kociemba says his 2phase algorithm solves 10000 cubes per hour on average on a 3GHz pentium 4 and it is not even using huge precalculated tables, just IDA* search. At that rate handling all 10^8 cosets in the Winter table (with 24-way reduction from cube body rotations) would take 10^4 hours = 1.1 years and almost all these cosets would be doable in <=20f (we expect at most 10^8/500000 = 200 exceptional cosets which would perhaps have to be examined more deeply). This calculation is bogus because a "coset" is not the same as "a scrambled cube" and really it'll be a lot slower since there will be many far-H elements to consider... However, with the aid of our huge precalculated tables, it'll be way faster than that, maybe 1000 times faster once the tables are built, which will probably be enough to cancel out this bogusness factor. So I guesstimate 1 year of computing on a machine with a lot of RAM will suffice to establish the diameter of the cube, and with N such machines, almost N times faster for 1<=N<=20 since building the big tables should be doable in only a few days at most.

Warren Smith

24 Rotations

I'm not sure how the 24 cube-body rotations could be used to reduce the size of the problem. Unless you choose to ignore the face centers, a cube-body rotation doesn't change anything (c.f., the 4-spot position, which would appear to be solved if the cube centers were ignored).

It seems to me that if the 24 cube-body rotations are considered to be equivalent, then a different (and smaller) problem is being solved. The entire Rubik's cube problem is not really being solved.

The solution of the smaller problem would serve to place limits on the solution of the larger problem. For example, I solved the edges-without-corners-without-face-centers problem years ago. My solution could be thought of as providing a lower limit to the edges-without-corners-with-face-centers problem that Tom Rokicki solved in the last year or two. My solution could also be thought of as solving cosets of the problem that Tom was able to solve in its entirety. Which is to say, the problem Tom solved is 24 times larger than the problem I solved.

I think that Tomas Rokicki al

I think that Tomas Rokicki already tried a variant of this with his suboptimal solver. However testing each element of the group H for a given coset seem to take about an hour. So you have to multiply this with the number of cosets. For more details on his approach you can see the comments on his post about the group H.

H={L, R, F2, B2, U2, D2} (correction of HTML-caused screwup)

use greater than sign, trouble comes your way.