cube files
Indexed Cube Lovers Archive
A plan to settle the maximin distance problem so we can all go home
Submitted by WarrenSmith on Fri, 05/19/2006 - 20:50.
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
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 =
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
