#### xyzzy

##### Member

tl;dr: between ~~16 and 46~~ 18 and 34 moves (inclusive).

The kilominx has (19!/2) ⋅ 3^18 ~ 24 septillion states (with a fixed corner), which is well beyond what we can exhaustively enumerate. Even with full symmetry+antisymmetry reduction, that's still around 98 sextillion states, which is a lot larger than the number of 3×3×3 states

This first post will be about an upper bound. (Lower bound analysis to come later, but for now you can have the "trivial" lower bound of 16 moves by counting move sequences without immediate cancellations.) We divide solving the kilominx into two phases, given by the following chain of subgroups: $$G_0:=\langle\text{all 12 moves}, \text{rotations}\rangle$$, $$G_1:=\langle U,R,F,D,DB,DBL\rangle$$, $$G_2:=\langle\rangle$$. For this, we

Note that $$G_1=\langle U,R,F,D,DB,DBL\rangle=\langle U,R,F\rangle\times\langle D,DB,DBL\rangle$$. This effectively divides the puzzle into two disjoint "hemispheres" that don't interact, centred at the U-R-F and D-DB-DBL corner pieces. For convenience, call these the north and south hemispheres, respectively. The right coset space $$G_1\backslash G_0$$ can be treated as a vector of 20 bits corresponding to whether each corner piece belongs to the south hemisphere in the solved state, along with an additional value in $$\mathbb Z/3$$ corresponding to the sum of the orientations of the 10 pieces belonging to the south hemisphere. In other words, this phase is equivalent to separating the pieces into the hemispheres they belong to, and ensuring that the corner orientation within each hemisphere adds up to 0.

The coset space has $$\binom{20}{10}\cdot3=554268$$ cosets, but there is no need to consider the whole coset space. Firstly, we don't even need to care about corner orientation here; once the corners are separated into the hemispheres, we can change the total corner orientation within each hemisphere (without affecting the separation) by just rotating around the U-R-F corner. Secondly, it doesn't matter whether the pieces are all moved to the correct hemispheres; we could also have them all moved to the wrong hemispheres and then rotate the puzzle to put them in the correct hemispheres. This reduces the number of cases to consider to $$\binom{20}{10}/2=92378$$.

Average: 3.707

Upper bound: 6

The $$\langle U,R,F\rangle$$ subgroup, while much smaller than $$G_0$$, is still pretty large, having 36 billion states. It's small enough that a full breadth-first search can be done if symmetry+antisymmetry reduction is used, but I will leave this for another time.

Anyway, we can split this into solving orientation then permutation; for this, I used the same definition of orientation as in my solver. Unlike on a 2×2×2, it's not possible to define orientation in terms of a subgroup generated by single moves (e.g. you can't just say something like "the orientation defined by ⟨U, R2, F2⟩"). Here, we choose reference stickers on each of the corner pieces by taking the one that is closest to perpendicular to the U-D axis; equivalently, corner orientation is preserved by U, (R' F R F')3, flip and y. (There's a different choice of reference stickers that is more symmetrical when restricted to $$\langle U,R,F\rangle$$, which would make implementing symmetry/antisymmetry reduction easier.)

Orientation:

Average: 5.19

Upper bound: 7

Permutation:

Average: 11.510

Upper bound: 13

(The distribution for the orientation substep is done with a standard breadth first search, but the distribution for the permutation step was computed by doing an IDA* search on each of the 10!/2 states with pieces already oriented. It's not possible to use a BFS to directly compute the latter distribution, as most moves disturb corner orientation.)

This gives an upper bound of 20 moves for $$\langle U,R,F\rangle$$, and since $$G_1$$ is just two copies of $$\langle U,R,F\rangle$$, the upper bound for phase 2 as a whole is 40 moves.

To conclude, this gives an upper bound of 46 moves for solving a kilominx.

Spoiler: empirical results from sampling one million random states in ⟨U, R, F⟩

Average: 11.763

These are the three 14-move states (or, well, the inverses of these, but same thing):

U R U2' R2' F' U2 F' U2' R F2 R2 U' R2 U'

U R2 U2 R2 F' U R F' R2' F2' U2' R2' U' F2

U R U2' F2' U2' R F' R F U2 R2 F2' R2 U2'

These can probably be solved in fewer moves if we allow moves other than just U, R and F. (I don't have a full optimal solver yet.)
Spoiler: assorted rambling

The kilominx has (19!/2) ⋅ 3^18 ~ 24 septillion states (with a fixed corner), which is well beyond what we can exhaustively enumerate. Even with full symmetry+antisymmetry reduction, that's still around 98 sextillion states, which is a lot larger than the number of 3×3×3 states

*without any symmetry reduction*. (You know a number is large when the spelling checker thinks that it's not a real word.)This first post will be about an upper bound. (Lower bound analysis to come later, but for now you can have the "trivial" lower bound of 16 moves by counting move sequences without immediate cancellations.) We divide solving the kilominx into two phases, given by the following chain of subgroups: $$G_0:=\langle\text{all 12 moves}, \text{rotations}\rangle$$, $$G_1:=\langle U,R,F,D,DB,DBL\rangle$$, $$G_2:=\langle\rangle$$. For this, we

*do not*use a fixed corner, so $$G_0$$ includes all 20!/2 even permutations of the corners. Further, while rotations can be done solely with face turns, keeping the "core" fixed, we explicitly include them in the generating set and treat them as free moves (i.e. rotations don't contribute to the move count).**Phase 1: separation**Note that $$G_1=\langle U,R,F,D,DB,DBL\rangle=\langle U,R,F\rangle\times\langle D,DB,DBL\rangle$$. This effectively divides the puzzle into two disjoint "hemispheres" that don't interact, centred at the U-R-F and D-DB-DBL corner pieces. For convenience, call these the north and south hemispheres, respectively. The right coset space $$G_1\backslash G_0$$ can be treated as a vector of 20 bits corresponding to whether each corner piece belongs to the south hemisphere in the solved state, along with an additional value in $$\mathbb Z/3$$ corresponding to the sum of the orientations of the 10 pieces belonging to the south hemisphere. In other words, this phase is equivalent to separating the pieces into the hemispheres they belong to, and ensuring that the corner orientation within each hemisphere adds up to 0.

**EDIT: This is slightly wrong because I forgot about parity**, but I don't have time to fix it right now. See qqwref's post later in this thread. The overall upper bound is unaffected, but the average move count increases slightly.The coset space has $$\binom{20}{10}\cdot3=554268$$ cosets, but there is no need to consider the whole coset space. Firstly, we don't even need to care about corner orientation here; once the corners are separated into the hemispheres, we can change the total corner orientation within each hemisphere (without affecting the separation) by just rotating around the U-R-F corner. Secondly, it doesn't matter whether the pieces are all moved to the correct hemispheres; we could also have them all moved to the wrong hemispheres and then rotate the puzzle to put them in the correct hemispheres. This reduces the number of cases to consider to $$\binom{20}{10}/2=92378$$.

depth | # reduced cosets |
---|---|

0 | 10 |

1 | 240 |

2 | 4050 |

3 | 26890 |

4 | 52552 |

5 | 8616 |

6 | 20 |

Upper bound: 6

**Phase 2: two 3-gen solves**The $$\langle U,R,F\rangle$$ subgroup, while much smaller than $$G_0$$, is still pretty large, having 36 billion states. It's small enough that a full breadth-first search can be done if symmetry+antisymmetry reduction is used, but I will leave this for another time.

Anyway, we can split this into solving orientation then permutation; for this, I used the same definition of orientation as in my solver. Unlike on a 2×2×2, it's not possible to define orientation in terms of a subgroup generated by single moves (e.g. you can't just say something like "the orientation defined by ⟨U, R2, F2⟩"). Here, we choose reference stickers on each of the corner pieces by taking the one that is closest to perpendicular to the U-D axis; equivalently, corner orientation is preserved by U, (R' F R F')3, flip and y. (There's a different choice of reference stickers that is more symmetrical when restricted to $$\langle U,R,F\rangle$$, which would make implementing symmetry/antisymmetry reduction easier.)

Orientation:

depth | # cosets |
---|---|

0 | 1 |

1 | 8 |

2 | 61 |

3 | 452 |

4 | 2674 |

5 | 9182 |

6 | 7070 |

7 | 235 |

Upper bound: 7

Permutation:

depth | # states |
---|---|

0 | 1 |

1 | 4 |

4 | 6 |

5 | 56 |

6 | 190 |

7 | 746 |

8 | 4727 |

9 | 25251 |

10 | 140966 |

11 | 602085 |

12 | 944543 |

13 | 95825 |

Upper bound: 13

(The distribution for the orientation substep is done with a standard breadth first search, but the distribution for the permutation step was computed by doing an IDA* search on each of the 10!/2 states with pieces already oriented. It's not possible to use a BFS to directly compute the latter distribution, as most moves disturb corner orientation.)

This gives an upper bound of 20 moves for $$\langle U,R,F\rangle$$, and since $$G_1$$ is just two copies of $$\langle U,R,F\rangle$$, the upper bound for phase 2 as a whole is 40 moves.

To conclude, this gives an upper bound of 46 moves for solving a kilominx.

depth | # states |
---|---|

0 | 0 |

1 | 0 |

2 | 0 |

3 | 1 |

4 | 0 |

5 | 3 |

6 | 10 |

7 | 87 |

8 | 671 |

9 | 5453 |

10 | 40232 |

11 | 245288 |

12 | 600187 |

13 | 108065 |

14 | 3 |

These are the three 14-move states (or, well, the inverses of these, but same thing):

U R U2' R2' F' U2 F' U2' R F2 R2 U' R2 U'

U R2 U2 R2 F' U R F' R2' F2' U2' R2' U' F2

U R U2' F2' U2' R F' R F U2 R2 F2' R2 U2'

These can probably be solved in fewer moves if we allow moves other than just U, R and F. (I don't have a full optimal solver yet.)

Ignoring orientation, there are 284 permutations at depth 9 (and none at depth 10). Solving all 284×3^9 states with those permutations, we get this distribution:

Average: 11.832

The proportion of 14-movers in this specially chosen sample is much higher than in a uniform random sample. All of these 14-movers are local maxima, and most are "strict" local maxima (in the sense that every legal move brings it to depth 13). Up to symmetry, there's one 14-mover among these that isn't a strict local maximum, and it's one move away from a 14-mover

This very strongly suggests that the actual diameter should be 14 moves, which would bring the overall upper bound down to 6+14+14=34 moves.

On another note, my current kilominx random state scrambler uses different solving phases and has a move count of 27.8±1.3 moves. The scrambling/solving is done with "hemisphere notation", which includes the U, R, F, L, BL and BR moves, in addition to flipping the whole puzzle over (i.e. rotating 180 degrees around the left-right axis), denoted as either "x2" or "flip". Since scramble sequences are meant to be applied by human scramblers, minimising rotations was a design goal, and the solving method used outputs a maximum of two flips per scramble. (Furthermore, we want to avoid "weird" rotations, because that would require additional scrambling notation, and the simpler the notation, the less likely scrambling mistakes are; to that end, flipping is the

While the phases used in this post would lead to a slightly lower average move count (3.707+11.763+11.763 = 27.233 moves), the first phase makes use of arbitrary rotations while separating the pieces, which is extremely undesirable.

depth | # states |
---|---|

9 | 18648 |

10 | 175957 |

11 | 1239372 |

12 | 3447704 |

13 | 707850 |

14 | 441 |

The proportion of 14-movers in this specially chosen sample is much higher than in a uniform random sample. All of these 14-movers are local maxima, and most are "strict" local maxima (in the sense that every legal move brings it to depth 13). Up to symmetry, there's one 14-mover among these that isn't a strict local maximum, and it's one move away from a 14-mover

*not*among those; this new 14-mover is also a local maximum and isn't adjacent to any other 14-movers.This very strongly suggests that the actual diameter should be 14 moves, which would bring the overall upper bound down to 6+14+14=34 moves.

On another note, my current kilominx random state scrambler uses different solving phases and has a move count of 27.8±1.3 moves. The scrambling/solving is done with "hemisphere notation", which includes the U, R, F, L, BL and BR moves, in addition to flipping the whole puzzle over (i.e. rotating 180 degrees around the left-right axis), denoted as either "x2" or "flip". Since scramble sequences are meant to be applied by human scramblers, minimising rotations was a design goal, and the solving method used outputs a maximum of two flips per scramble. (Furthermore, we want to avoid "weird" rotations, because that would require additional scrambling notation, and the simpler the notation, the less likely scrambling mistakes are; to that end, flipping is the

*only*type of rotation used.)While the phases used in this post would lead to a slightly lower average move count (3.707+11.763+11.763 = 27.233 moves), the first phase makes use of arbitrary rotations while separating the pieces, which is extremely undesirable.

Last edited: Feb 27, 2018