Solving Rubik's cube in 40 quarter turns

I hope you are going to do the 38 computation so that we are going to have a better upper bound. Now about the solver and the resources:

The program was made in GAP and takes about 70 days on an usual PC.
But it is constructed so that if you have N PC computers then the speed is 70/N days. I used 20 computers for about 3-4 days. The program uses following idea:
Call the set of elements that must be computed in 22q or less for X.
Rather then concentrating on each position it is better just to generate elements in X regardless to what they are and keep track on which elements have been found. Using this method the program computes all but 105000 positions(of the total 44 milions) in just 1 day on an usual PC. Because we dont have control over what positions we generate in the set X some positions are going to be regenerated and the speed decreases as more positions are found.

How are positions in X generated?

Let (x,y) denote an element in the cube group and x is the edge configruation and y is the corner configuration.Given a fixed edge configuration call it g. Call the set consisting of elements of the form (g,z) achivable in 10 moves or less for S_1. And the set of elements of the form (g^-1,u) achivable in 12 moves or less for S_2. It is obvious that if we take an element from S_1 and multiply by an element from S_2 we get an element of the form (id,uw). For example if we take g to be the identity (of the edge configuration) we get 3079007 elements in X in just 2 minutes after taking all possible products between S_1 and S_2.

The above computation have been done very recently and work i still done on the paper presenting detailed algorithms etc. I found however a new algorithm based on the above idea that finishes the 70 day computation in maybe 1-2 days maximum.

I hope somebody takes the time to verify my "Data file". If you do this please send me an email.

Silviu

As Silviu mentioned, it was recently determined that the cube restricted to edges can be solved in at most 18 quarter turns. Further, that analysis indicated that there is a unique antipode in that case. There are only four configurations of the edges that have this level of symmetry. These configurations can be stated in terms of certain representative positions of the cube where the corners are all in place and oriented correctly. These four cases are:
1. the solved cube (obviously not the antipode)
2. Pons Asinorum (solveable in 12 quarter turns: U2 B2 F2 B2 L2 R2, so it can't be the antipode)
3. the superflip
4. Pons Asinorum composed with the superflip

Since edge configurations corresponding to 1 and 2 can not be antipode, the antipode must correspond to one of the other two edge configurations: the edge configuration of the superflip, or that of Pons Asinorum composed with the superflip.

For each edge configuration, there are 8!*(3^7)/2 = 44,089,920 possible configurations of the corners. I have used a fast cube solving routine to check all cube positions with the same edge configurations as 3 and 4 above. This resulted in finding a way to solve each of these 2 * 44,089,920 cube positions in no more than 38 moves. (Note these solutions that were found are typically far from optimal solutions.) The following tables list the distribution of the lengths (quarter turns) of the solutions that this fast solver found for the set of positions of interest.

Superflip edge configuration

solution
length       count
  14             2
  18            57
  20           177
  22          2835
  24         21714
  26        151834
  28        953099
  30       4649674
  32      13820528
  34      17381839
  36       7107953
  38           208
          --------
          44089920

Pons Asinorum composed with superflip edge configuration

solution
length       count
  18            40
  20           332
  22          2846
  24         22176
  26        153416
  28        963499
  30       4656631
  32      13817591
  34      17408560
  36       7064629
  38           200
          --------
          44089920

Since solutions for cube positions with the superflip edge configuration were found using only 14 quarter turns, the antipode (requiring 18 quarter turns to solve the edges) must be the other edge configuration, corresponding to Pons Asinorum composed with the superflip.

Now, divide all positions of the Rubik's cube into two sets. The first set being all those with the same edge configuration as Pons Asinorum composed with the superflip. The second set being all the remaining positions.

In the first set, my fast solver found a solution for every case using no more than 38 quarter turns.

In the second set, all positions can reach a configuration with the edges solved in 17 quarter turns or less. According to Silviu's result, it takes no more than 22 additional quarter turns to solve the cube, for a total of 17+22 = 39.

Thus, assuming there are no flaws in any of the computer analyses involved, then all positions of Rubik's cube can be solved with no more than 39 quarter turns. I will plan to generate a list of actual quarter-turn sequences to solve the various positions corresponding to the antipode of the edges-only analysis.

The edges-only analysis listed 30 positions that require 17 quarter turns to solve the edges, but only 3 that are unique with respect to M, the symmetry group of the cube. If all cube positions having these edge configurations can be shown to be solved in 38 moves or less (and these require an odd number of moves to solve, so really 37 or less), then that would further reduce the upper bound for the quarter turn metric to 38 (assuming the correctness of the computer analyses used). One of these three positions must be the position one quarter-turn from the antipode. I can't check the other two positions unless I can find out what they are.

- Bruce Norskog

Congratulations to you both -- this is quite a leap from 42, especially if 38 can be proved.

Two questions:

(1) Do you think this approach would be likely to improve the upper bound in HTM, too? (I suspect not, from the known edges-only result.)

(2) What kind of fast solver are you using, Bruce?

Mike G.

Mike G. wrote:

(1) Do you think this approach would be likely to improve the upper bound in HTM, too? (I suspect not, from the known edges-only result.)

Lowering the upper bound in QTM from 42 to 38 would bring the upper bound/lower bound ratio close to the same value as for HTM. So I suspect this approach may not yield a better upper bound for HTM. Solving corners without preserving edges takes 11 face turns in the worst case. 14 + 11 = 25, which is fairly close to 28 already. Also the edges-only analysis for HTM has many more antipodes, 24 unique wrt M rather than 1, and one level closer has close to 7 million positions (unique wrt M). So my technique of "eliminating" those cases would at least be more time-consuming.

(2) What kind of fast solver are you using, Bruce?

My fast solver is actually a function that I call repeatedly from within a program that is edited and recompiled each time I want to try different cases. It is based somewhat upon the documentation of Herbert Kociemba's Cube Explorer two-phase algorithm, but mine builds tables for QTM rather than HTM. My code uses two large arrays of approximately 70MB and 670MB, so distances of positions for each phase can be looked up directly, rather than using an IDA*-like algorithm to solve each phase. The code starts with the position to be solved and looks for a move that will bring it to a closer position. (It doesn't look for alternate possible moves once it finds one.) When phase 1 is completed, it does the same for phase 2. Then it eliminates redundant moves from the result. Finally, the whole process is repeated for two other symmetrically equivalent positions to see if a better solution is found. (In obtaining my previously posted results, I stopped the process of trying alternative symmetrically equivalent positions when I found one less than 38 moves. Thus, I eliminated the second and third cases most of the time, providing essentially an average 3x speed improvement.)

I have since re-run my program to generate a file with solve sequences for each position. Actually, I put in code so that only one of each set of symmetrically equivalent positions are solved. Since many fewer positions then needed to be analyzed, I changed the code back to always trying three cases for each position, to get shorter average solutions, and a somewhat smaller output file. The file size is approximately 31MB if I use a one-character code for each quarter turn move (or about 38MB if standard notation with apostrophes is used). I can email either file to someone, if requested to do so.

- Bruce Norskog