Home »

Some "F2L" computer analyses

Submitted by Bruce Norskog on Tue, 02/19/2008 - 22:18.

I have done some "restricted" God's algorithm calculations for solving two layers of Rubik's Cube, given that the four edges of the face layer are already solved. I say it's a "restricted" calculation because it only considers certain moves or sequences of moves. For convenience, I will consider the two layers to be solved are the bottom layer (generally referred to as the D layer), and the layer above that (typically referred to by speedcubers as the E layer).

Given that four edges of the D layer are taken to be solved, the remaining four edges being considered (those that belong in the E layer) must be distributed among 8 possible edge locations. So the number of configurations for those four edges is 8*7*6*5*(24) = 26880 (including orientations). The four corner cubies being considered (those that belong in the D layer) have 8*7*6*5*(34) = 136080 configurations (including orientations). This makes for a total of 26880*136080 = 3,657,830,400 configurations.

By restricting the moves (or move sequences) that are considered so that the four D layer edges (these will be referred to as the cross edges from now on) remain in their solved positions, only these 3,657,830,400 configurations need to be considered. So my first calculation limited the moves considered to those listed below.

In this analysis, a position from which the solved state (i.e. the two layers of interest solved) can be reached via one of the specified 3-move sequences is considered to be a distance of 3 from solved. A position that can be solved with a U layer turn followed by one of the three move sequences is considered to be a distance of 3 + 1 = 4 from solved, and so on.


Allowed moves/sequences:

counted as one move:
U           U'          U2

counted as three moves:
(L U L')    (L U' L')   (L U2 L')
(L' U L)    (L' U' L)   (L' U2 L)
(R U R')    (R U' R')   (R U2 R')
(R' U R)    (R' U' R)   (R' U2 R)
(F U F')    (F U' F')   (F U2 F')
(F' U F)    (F' U' F)   (F' U2 F)
(B U B')    (B U' B')   (B U2 B')
(B' U B)    (B' U' B)   (B' U2 B)

distance  positions
--------  ---------
  0               1
  1               0
  2               0
  3              24
  4              40
  5               0
  6             444
  7           2,032
  8           1,732
  9           8,236
 10          60,212
 11         116,090
 12         203,792
 13       1,376,580
 14       4,033,014
 15       6,680,438
 16      25,759,944
 17      80,363,704
 18     148,794,392
 19     400,179,802
 20   1,084,980,493
 21   1,124,562,280
 22     624,375,623
 23     139,420,738
 24      11,830,455
 25       5,080,152
 26             182
      -------------
total 3,657,830,400

Arguably, there is a flaw in this calculation in that a sequence of moves such as: (R U' R') (R' U2 R) is counted as 6 moves, but could be optimized to R U' R2 U2 R (only 5 face turns).

I have performed another calculation where 32 four-move sequences that preserve the cross are also considered. This allows all but 9 positions to be solved using 25 or less moves. See summary below.


Allowed moves/sequences:

counted as one move:
U           U'          U2

counted as three moves:
(L U L')    (L U' L')   (L U2 L')
(L' U L)    (L' U' L)   (L' U2 L)
(R U R')    (R U' R')   (R U2 R')
(R' U R)    (R' U' R)   (R' U2 R)
(F U F')    (F U' F')   (F U2 F')
(F' U F)    (F' U' F)   (F' U2 F)
(B U B')    (B U' B')   (B U2 B')
(B' U B)    (B' U' B)   (B' U2 B)

counted as four moves:
(L F' L' F)    (L F2 L' F2)   (L2 F' L2 F)   (L2 F2 L2 F2)
(L' B L B')    (L' B2 L B2)   (L2 B L2 B')   (L2 B2 L2 B2)
(R B' R' B)    (R B2 R' B2)   (R2 B' R2 B)   (R2 B2 R2 B2)
(R' F R F')    (R' F2 R F2)   (R2 F R2 F')   (R2 F2 R2 F2)
(F R' F' R)    (F R2 F' R2)   (F2 R' F2 R)   (F2 R2 F2 R2)
(F' L F L')    (F' L2 F L2)   (F2 L F2 L')   (F2 L2 F2 L2)
(B L' B' L)    (B L2 B' L2)   (B2 L' B2 L)   (B2 L2 B2 L2)
(B' R B R')    (B' R2 B R2)   (B2 R B2 R')   (B2 R2 B2 R2)

distance  positions
--------  ---------
  0               1
  1               0
  2               0
  3              24
  4              64
  5              72
  6             444
  7           3,144
  8           7,951
  9          18,622
 10          95,670
 11         384,650
 12       1,033,982
 13       3,175,760
 14      12,081,182
 15      36,424,316
 16      92,555,582
 17     255,605,628
 18     653,124,460
 19   1,096,446,464
 20   1,084,487,378
 21     393,409,884
 22      28,509,722
 23         463,652
 24           1,739
 25               9
      -------------
total 3,657,830,400

The 9 distance-25 positions in the above analysis can be reduced to 3 patterns by using symmetry. These patterns can be generated by:
(L U L') (F U' F') (R' U R) (R U2 R') (B' R2 B R2) (B' U2 B) (F' U F) (L' U' L)
(L U' L') (F' U F) (R' U' R) (R U2 R') U2 (F U F') (R U' R') (L U2 L') (L' U' L)
(L U L') (R' U2 R) (R U' R') (R' F2 R F2) U (R U2 R') U (R' U' R) U (L U L')

Obviously, from the sequences given above, these positions can all be solved in 24 face turns or less using trivial optimizations of the given sequences.

I performed a third calculation where D layer moves are also considered, but not the four-move sequences from the previous calculation. With D layer turns the four cross edges can now have four different configurations, so the number of positions considered becomes 4*3,657,830,400 = 14,631,321,600. Note that the four cross edges are merely permuted amongst themselves, so the other edges are still limited to the same remaining 8 edge positions.


Allowed moves/sequences:

counted as one move:
U           U'          U2
D           D'          D2

counted as three moves:
(L U L')    (L U' L')   (L U2 L')
(L' U L)    (L' U' L)   (L' U2 L)
(R U R')    (R U' R')   (R U2 R')
(R' U R)    (R' U' R)   (R' U2 R)
(F U F')    (F U' F')   (F U2 F')
(F' U F)    (F' U' F)   (F' U2 F)
(B U B')    (B U' B')   (B U2 B')
(B' U B)    (B' U' B)   (B' U2 B)

                          positions with:
            ---------------------------------------------
            A. solved   B. cross rotated C. cross rotated  total positions
distance       cross         +/- 90 deg        180 deg         (A+2B+C)
--------    -----------    -------------    -------------  ---------------
     0                1                0                0                1
     1                0                1                1                3
     2                0                0                0                0
     3               24                0                0               24
     4               40               48               48              184
     5               72              128              128              456
     6              564               80               80              804
     7            2,032            1,464            1,460            6,420
     8            6,292            9,520            9,440           34,772
     9           30,020           21,908           22,040           95,876
    10           86,220           61,424           60,928          269,996
    11          282,834          380,052          373,172        1,416,110
    12        1,442,740        1,412,144        1,420,360        5,687,388
    13        4,253,940        3,550,728        3,556,892       14,912,288
    14       10,775,680       12,628,394       12,522,088       48,554,556
    15       45,721,886       47,613,567       47,699,038      188,648,058
    16      125,038,958      114,134,678      114,145,388      467,453,702
    17      248,217,526      263,563,353      261,694,326    1,037,038,558
    18      713,565,520      720,915,551      720,143,790    2,875,540,412
    19    1,149,313,518    1,080,898,530    1,082,829,610    4,393,940,188
    20      916,944,377      956,586,249      956,485,206    3,786,602,081
    21      396,869,429      410,799,168      411,375,646    1,629,843,411
    22       36,579,071       32,271,898       32,645,183      133,768,050
    23        8,096,077       12,405,618       12,260,201       45,167,514
    24          492,748            9,753           19,231          531,485
    25          110,828          566,116          566,125        1,809,185
    26                3               28               19               78
          -------------    -------------    -------------   --------------
total     3,657,830,400    3,657,830,400    3,657,830,400   14,631,321,600

The three positions with solved cross at distance 26 have all cubies in the correct place, but one of them has all four non-cross edges flipped, and the other two have all four corners twisted, with diagonally opposite corners having the same twist, but neighboring corners having opposite twist. Sequences for these positions are:
(L U L') (L' U L) (F U2 F') (R U' R') D2 (B U B') (B' U B) (R' U' R) (F' U' F) D2
(L U L') (L' U L) (F' U F) (R' U' R) U' (F' U F) (L' U2 L) U (L U' L') (R' U2 R)
(L U L') (L' U' L) (B U' B') D2 (L U' L') (B' U' B) (L' U' L) (B U' B') D2 (L U2 L')

Clearly, these sequences can be trivially optimized to sequences of 25 face turns or less.

» login or register to post comments | previous forum topic | next forum topic

Comment viewing options

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

some more analyses

Submitted by Bruce Norskog on Sat, 03/15/2008 - 19:28.

I have done a couple more of these analyses. The first one is for quarter-turn metric. Again, it is assumed that the cross is already formed (correctly rotated).

Quarter-turn metric F2L analysis

Allowed cross-preserving moves/sequences are:

Single moves:
U            U'

Three-move sequences:
(L U L')      (L U' L')     (L' U L)      (L' U' L)
(R U R')      (R U' R')     (R' U R)      (R' U' R)
(F U F')      (F U' F')     (F' U F)      (F' U' F)
(B U B')      (B U' B')     (B' U B)      (B' U' B)

Four-move (QTM) sequences:
(L U2 L')     (L' U2 L)     (R U2 R')     (R' U2 R),
(F U2 F')     (F' U2 F)     (B U2 B')     (B' U2 B)

distance    positions
--------    ---------
   0                1
   1                0
   2                0
   3               16
   4               32
   5               16
   6              208
   7              952
   8            1,496
   9            3,852
  10           19,204
  11           51,220
  12          105,374
  13          364,084
  14        1,162,008
  15        2,703,072
  16        7,141,294
  17       20,838,278
  18       47,604,902
  19      106,766,882
  20      288,443,746
  21      658,792,006
  22    1,042,896,593
  23    1,024,017,700
  24      402,329,234
  25       48,566,857
  26        5,984,720
  27           36,650
  28                3
        -------------
total   3,657,830,400

Average distance: 22.0196

The positions at distance 28 can be solved with these sequences:

(L U' L') (R U' R') U' (R U' R') (B U' B') (L' U L) (B' U' B) (F' U F) (R' U' R) (F U F')
(L U L') U (F U2 F') (F' U' F) (R' U R) U' (B U' B') (R' U' R) (L' U' L) U (L U' L')
(L U L') (F U' F') (R' U R) U (R U R') (B' U B) (L U L') (L' U' L) (R' U R) (R U R')

The next analysis is for FTM. It is like the FTM analysis in the previous post that considered 4-move cross-preserving sequences. This one allows 534 cross-preserving sequences of 5 FTM moves in addition to the moves of that previous analysis. It does not allow D-layer moves by themselves (which would rotate the cross), but 148 of the 5-move cross-preserving sequences contain D layer moves.

Face-turn metric F2L analysis

Allows:
     3 U layer turns
    24 3-move sequences
    32 4-move sequences
   534 5-move sequences

distance    positions
--------    ---------
   0                1
   1                0
   2                0
   3               24
   4               64
   5              552
   6            1,544
   7            2,728
   8           27,063
   9          123,764
  10          468,819
  11        1,786,254
  12        5,557,694
  13       23,506,636
  14       89,466,711
  15      263,889,182
  16      698,020,265
  17    1,260,785,426
  18    1,095,816,176
  19      214,614,713
  20        3,755,270
  21            7,504
  22               10
        -------------
total   3,657,830,400

Average distance: 16.9740

The 10 positions at distance 22 consist of two symmetrically distinct positions. These positions can be solved using:

(L U' L') (R' U R) U (R2 B2 R2 B2) (B L' U2 B' L) U' (R' F U2 R F')
(L U' L') U' (R2 U' R U R2) (L2 F' L2 U F) (F U F') (D' L' U L D)
» login or register to post comments