Source files and build scripts for my personal website
git clone
Download | Log | Files | Refs | README (12137B)

      1 # Optimizing solutions: n-slice insertions
      3 ## tl;dr
      5 You can insert 3 slices in one of the following ways:
      7 * `E (I) E (I or D) E2`
      8 * `E (I) E2 (I) E`
      9 * `E (D) E2 (D) E`
     11 Where `(I)` denotes a "neutral" sequence like `R2 R2` or `R2 F2 L2`
     12 and `(D)` denotes a "diagonal swap" sequence like `R2 F2 R2`. The list
     13 above is complete up to inverses and mirrors.
     15 ## Setting
     17 The problem is this: say you have a DR finish on U/D that contains some
     18 "sliceable" sequences, such as `U D'`, `U2 D`, `U D` or similar. To be
     19 more precise, a sliceable sequence is a sequence of moves that would
     20 cancel out on a 2x3x3 cube.
     22 *(I will not address the problem of having a DR finish minus slice
     23 and inserting E-moves to solve the slice, because it can be reduced
     24 to the "solved slice" case by solving the slice sub-optimally with
     25 any insertion.)*
     27 Sliceable sequences can often be simplified also in a 3x3x3 cube. One
     28 way to do this is to insert E-layer moves at different points of the
     29 solution in such a way that the effect on the E-layer cancels out. It
     30 has been known since the early days of DR (2019) how to insert two moves
     31 that cancel out (`E` and `E'`, or `E2` and `E2`) without affecting the
     32 E-layer edges even without looking at a cube. *(I believe the first person
     33 to come up with a way to do this was Wen, but correct me if I am wrong.)*
     35 I will call insertions of multiple E-layer moves n-slice insertions.
     36 I will start this post with some necessary preliminaries, and then I'll
     37 recall how to find 2-slice insertions without looking at the cube. Then
     38 I will move explain how to do 3-slice insertions in a similar way, and I
     39 will prove that there is no other way to do 3-slice insertions. Finally,
     40 I'll leave here some considerations I have made for more complex cases,
     41 hoping that this will help us develop a general theory to perform any
     42 kind of n-slice insertion quickly and without looking at a cube.
     44 ## Preliminaries: floppy and "minidisc" sequences
     46 To insert slices, we have to understand how sequences of DR moves affect
     47 the edges of the E-layer. For this purpose, we can ignore any `U*` or
     48 `D*` move, hence we have to study move sequences in the floppy cube
     49 subgroup <R2, L2, F2, B2>.
     51 There are two kinds of sequences that are particularly important: those
     52 that, up to `y` rotations, do not affect the E-layer (we'll call these
     53 sequences *I-sequences*, where I stands for "Identity") and those that,
     54 up to `y` rotations, perform a single diagonal swaps (*D-sequences*).
     56 Some examples of I-sequences:
     58 * `R2 F2 F2 R2` (all moves "cancel out")
     59 * `R2 F2 L2` (equivalent to y', E-edges stay in the same relative position)
     60 * `R2 F2 R2 L2 B2 L2` (two D-sequences in a row always give an I-sequence)
     62 Some examples of D-sequences:
     64 * `F2 B2`
     65 * `R2 F2 R2`
     67 Considering only the effect of a floppy sequence on the E-layer
     68 edges up to y rotations, there are only 6 possible types of sequences.
     69 They are equivalent to the possible permutations of a 2x2x1 cube
     70 (or "minidisc" cube, name that I have just made up) that keep one
     71 corner (say BL) fixed:
     73 * `(no moves)` I-sequences
     74 * `R2`
     75 * `R2 F2`
     76 * `R2 F2 R2` D-sequences
     77 * `F2 R2`
     78 * `F2`
     80 This fact will come into play later on.
     82 ## 2-slice insertions
     84 As I said at the beginning, it has been known for a while how to
     85 do 2-slice insertions (`E E'` or `E2 E2`) without affecting the E-layer
     86 edges. The trick is the following:
     88 * For `E E'` insertions, insert either `E` or `E'` wherever you want
     89   (usually in a "sliceable" place, i.e. right before/after a `U* D*`
     90   pair of moves) and insert the other slice (either `E'` or `E`) in a
     91   spot such that the moves between the two insertions form an I-sequence.
     92 * For `E2 E2` insertions, insert the first `E2` wherever you want, and
     93   the second `E2` in a spot such that the moves between the two
     94   insertions form either an I-sequence or a D-sequence.
     96 There is no other way of inserting two slices so that they cancel out.
     98 ### Examples
    100 For our first example, say you have a DR finish like this:
    102 ```
    103 Setup: R2 D R2 D' U' R2 U R2 U' B2 L2
    105 Solution:
    106 L2 B2 U //Blocks + OBL
    107 R2 U' R2 U D R2 D' R2 //J+J perm
    108 ```
    110 Ideally, you would like to "slice away" the `U D` in the second step.
    111 You can insert there either an `E` or an `E'`, in either case one you save
    112 one move. Where can you insert the second slice move? We can see that the
    113 three moves before `U D` are an I-sequence, and placing an `E'` before
    114 them would cancel out the `U` ending the first step.  Here only an `E'`
    115 can be inserted, so we'll have to use `E` in the other spot.  So we have:
    117 ```
    118 L2 B2 U [2]
    119 R2 U' R2 U D [1] R2 D' R2
    120 [1] = E
    121 [2] = E'
    122 ```
    124 Giving a final solution: `L2 B2 D B2 U' B2 U2 R2 D' R2`.
    125 One move saved!
    127 *(I like to number my insertions in the order I found them, hence the
    128 [2] before the [1] in this case.)*
    130 For our second example, take the double edge swap `(UF DF) (UL DR)`:
    132 ```
    133 R2 F2 R2 U2 F2 R2 F2 U2
    134 ```
    136 You can turn the two `U2` moves into `Uw2` and you get an equivalent alg.
    137 This is equivalent to the following two-slice insertion:
    139 ```
    140 R2 F2 R2 U2 [1] F2 R2 F2 [2] U2
    141 [1] = [2] = E2
    142 ```
    144 Notice that the two slices are separated by a D-sequence.
    146 Less intuitively, you can also change some of the other moves to
    147 their wide counterpart:
    149 ```
    150 R2 [1] F2 R2 U2 F2 [2] R2 F2 U2
    151 [1] = [2] = M2
    152 ```
    154 or
    156 ```
    157 R2 F2 [1] R2 U2 F2 R2 [2] F2 U2
    158 [1] = [2] = S2
    159 ```
    161 This trick is useful for maximizing cancellations with edge insertions,
    162 without memorizing many variations of the same alg.
    164 ## Bonus: 2 slices to solve a 4x case
    166 This bit is out of scope for this page, but it is still interesting
    167 to note. If, instead of shortening a "solved slice", you are trying to
    168 solve a 4x case (that is, edges are solved but the 4 E-layer centers are
    169 swapped), you can still use 2-slice insertions fairly easily.  In fact,
    170 inserting `E E` or `E' E'` so that they are separated by a D-sequence is
    171 going solves this case. Keep in mind that this will *not* work if the two
    172 `E` moves in the same direction are separated by an I-sequence!
    174 ## 3-slice insertions
    176 Up to inverses and mirrors, there are only two possible types of 3-slice
    177 insertions: `E E E2` and `E E2 E`. Both consist of two `E` moves (or two
    178 `E'` moves) and one `E2` move.
    180 To understand how to find spots to insert them, we are going to think
    181 about them as if we are inserting two `E` moves in the same direction,
    182 and then fixing the slice by inserting an `E2`. This works for both
    183 types of 3-slice insertions.
    185 The first question we want to ask is then: where can we insert two
    186 `E` moves so that the result can be fixed by a single `E2` insertion?
    187 An `E2` insertion necessarily performs a double swap of edges, so our
    188 two `E` insertion must leave such a case. (We are ignoring centers,
    189 because we already now they will be solved at the end of our process if
    190 we insert two `E` moves in the same direction and one `E2` move.)
    192 The answer is: the moves between the two `E` moves must form an
    193 I-sequence. Indeed, since an I-sequence does not affect the relative
    194 position of E-layer edges, two `E` moves separated by an I-sequence
    195 have the same effect as an `E2` move, that is a double edge swap (up to
    196 `y` rotations).
    198 This already tells us something useful: in those cases where we
    199 would like to insert two slices `E E'`, but we find an admissible
    200 spot for the second slice that would cancel more if we inserted the
    201 inverse move, we can the inverse move and hope to find a suitable
    202 spot to "correct" the insertions with an `E2`. We'll see in a minute
    203 where we can insert the `E2`, now let's prove that this is the only
    204 way to perform 3-slice insertions.
    206 We can check that this is the only admissible way to insert the two
    207 `E` moves by going through all other "minidisc sequences" listed in
    208 the previous section, and checking that E (minidisc sequence) `E`
    209 does not yield, up to a `y` rotation, a double edge swap.
    211 Up to a `y` rotation:
    213 * `E R2 E` is a single edge swap (`y2 F2` solves the slice)
    214 * `E R2 F2 E` is a 3-cycle (`y2 [E, F2]` solves the slice)
    215 * `E R2 F2 R2 E` is a single edge swap (`y2 [R2: B2]` solves the slice)
    216 * `E F2 R2 E` is a 3-cycle (`y2 [E', L2]` solves the slice)
    217 * `E F2 E` is a single edge swap (`y2 L2` solves the slice)
    219 So, where can we insert the final `E2`? This is easy: the moves between
    220 the `E2` and any of the two `E` moves must be either an I-sequence
    221 or a D-sequence. This can be proved with the same reasoning we used a
    222 few paragraphs above when we said that two `E` moves separated by an
    223 I-sequence have the same effect as an `E2`, combined with the knowledge
    224 on 2-slice insertions of type `E2 E2`.
    226 This gives us 4 possible "patterns" for 3-slice insertions, up to
    227 inverses and mirrors:
    229 * `E (I) E (I) E2`
    230 * `E (I) E (D) E2`
    231 * `E (I) E2 (I) E`
    232 * `E (D) E2 (D) E`
    234 Where (I) and (D) denote I- and D-sequences, respectively.
    236 ### Examples
    238 Let's take this example:
    240 ```
    241 Setup: L2 F2 L2 D' L2 D R2 D B2 U'
    242 Solution:
    243 U B2 U' B2 D' F2 U //HTR
    244 U D' B2 L2 B2 U' D // Finish, one move cancel
    245 ```
    247 *(The second step could be replace by `U' D F2 R2 F2 U D'` for one less
    248 move, and then you could use a 2-slice insertion, but please let me use
    249 this artificial example for now.)*
    251 The DR finish is then: `U B2 U' B2 D' F2 U2 D' B2 L2 B2 U' D`
    253 We would like to slice away the `U2 D'` and the `U' D` at the end, but
    254 they are separated by a D-sequence, and an `E2 E2` insertion would not
    255 work here.  But fear not, for we can use 3-slice insertions:
    257 ```
    258 U B2 U' [3] B2 D' F2 U2 D' [2] B2 L2 B2 [1] U' D
    259 [1] = E
    260 [2] = E2
    261 [3] = E
    262 ```
    264 In this case rather than inserting the two `E` moves first and then adjust
    265 with an `E2` it makes more sense to insert and `E` and an `E2` and then fix
    266 with another `E`, for maximum cancellation. This is reflected in the order
    267 I wrote the insertions.
    269 I would like to add more examples here, but I have yet to use 3-slice
    270 insertions in an actual FMC attempt.
    272 ## General n-slice insertions
    274 I have not been able to devise a general method for n-slice insertions,
    275 but I have some ideas on how to work in this direction.  This section
    276 contains only speculations, if you are only interested in learning
    277 new techniques that you can apply to your solves you do not have
    278 to read it.
    280 First of all, it could be worth considering only what we can call
    281 *fundamental* slice sequences, i.e. those having no contiguous
    282 sub-sequence that keeps centers solved. For example `E E E2` is
    283 fundamental, but `E2 E' E E2` is not (the `E' E` subsequence keeps
    284 centers solved) and neither is `E E' E E2 E` (both the `E E'` at the
    285 beginning and the `E' E` starting on move 2, as well as the ending
    286 `E E2 E`, are sub-sequences that do not affect centers).
    288 The idea behind this is that we can perform a non-fundamental
    289 slice insertion in two or more passes, by inserting the shorter
    290 subsequences first. Unfortunately, this is not as simple: for example,
    291 the non-fundamental sequence `E E' E E'` could be such that the first
    292 `E E'` pair leaves a 3-cycle that is subsequently fixed by the other
    293 `E E'` pair. Nevertheless, decomposing a sequence into fundamental
    294 subsequences can have its use.
    296 Classifying all fundamental sequences is actually very easy: up to
    297 inverses and mirrors, this is the full list:
    299 * `E E'`
    300 * `E2 E2`
    301 * `E E2 E`
    302 * `E E E2`
    303 * `E E E E`
    304 * `E2 E E2 E'`
    306 The fact that there are no fundamental sequences longer than 4 moves
    307 is a consequence of the following theorem (warning: Math ahead,
    308 caution advised):
    310 **Theorem**. Let n and k be positive integers. If a sequence of k
    311 elements of Z/nZ has sum 0 and it has no non-trivial (contiguous)
    312 subsequence with sum 0, then k <= n.
    314 *Clarification: non-trivial means that it contains at least one element
    315 and it is not the whole sequence.*
    317 **Proof** (thanks to Chiara for the nice proof). It is enough to
    318 prove that any sequence of n+1 elements of Z/nZ has a subsequence whose
    319 sum is 0. To prove this, let, for l=1 to n+1, s\_l = a\_1 + ... + a\_l.
    320 If s\_i=0 for any i, we are done. Otherwise by the pigeonhole principle
    321 there must be s\_i and s\_j with s\_i = s\_j and, say, i < j. But then
    322 the subsequence a\_(i+1), ..., a\_j has sum s\_j - s\_i = 0. This proves
    323 the claim.
    325 More work needs to be done here.