• Welcome to the Speedsolving.com, home of the web's largest puzzle community!
    You are currently viewing our forum as a guest which gives you limited access to join discussions and access our other features.

    Registration is fast, simple and absolutely free so please, join our community of 40,000+ people from around the world today!

    If you are already a member, simply login to hide this message and begin participating in the community!

Kilominx God's number bounds

xyzzy

Member
Joined
Dec 24, 2015
Messages
2,876
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 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
010
1240
24050
326890
452552
58616
620
Average: 3.707
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
01
18
261
3452
42674
59182
67070
7235
Average: 5.19
Upper bound: 7

Permutation:
depth# states
01
14
46
556
6190
7746
84727
925251
10140966
11602085
12944543
1395825
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.

depth# states
00
10
20
31
40
53
610
787
8671
95453
1040232
11245288
12600187
13108065
143
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.)
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:
depth# states
918648
10175957
111239372
123447704
13707850
14441
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 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:

jaap

Member
Joined
Sep 22, 2009
Messages
32
Location
Netherlands
WCA
2003SCHE01
YouTube
Visit Channel
Ok. I was a bit confused by your permutations calculation, as it has to preserve orientations, but presumably then you didn't just use a breadth first search using the orientation preserving generators you listed. Did you do a breadth first search using single moves and just filter from the output the ones that had the wrong orientation? Or did that take too long and you had to tackle the deeper positions separately with separate searches?
 

xyzzy

Member
Joined
Dec 24, 2015
Messages
2,876
Ok. I was a bit confused by your permutations calculation, as it has to preserve orientations, but presumably then you didn't just use a breadth first search using the orientation preserving generators you listed. Did you do a breadth first search using single moves and just filter from the output the ones that had the wrong orientation? Or did that take too long and you had to tackle the deeper positions separately with separate searches?
Right, I should've elaborated on this. I solved all of the 10!/2 positions with oriented pieces with IDA*. For example, this is one of the solutions produced: F' R' F2' R2' U2 F2' U2 R U2 R2' U. Each solve takes ~4 milliseconds, so this "brute force" approach took only around two hours to complete.
 

jaap

Member
Joined
Sep 22, 2009
Messages
32
Location
Netherlands
WCA
2003SCHE01
YouTube
Visit Channel
Cool. Anyway, this is really good work. I like the clever reductions due to the rotations of the whole puzzle.

Have you tested the neighbours (and neighbours of the inverses) of the three depth 14 positions you found in <U,R,F>? It's unlikely to result in a depth 15 position, but it is worth checking.
 

xyzzy

Member
Joined
Dec 24, 2015
Messages
2,876
Have you tested the neighbours (and neighbours of the inverses) of the three depth 14 positions you found in <U,R,F>? It's unlikely to result in a depth 15 position, but it is worth checking.
Oh, I didn't think of that. Just ran the solver on the neighbours, and those three positions and their inverses are local maxima (every move brings them to depth 13).

I like the clever reductions due to the rotations of the whole puzzle.
Funny thing is, I originally had this idea for megaminx, where you cannot use these "automatic symmetry reductions" because of the fixed centres. (And on a megaminx, G_1\G_0 is a much larger coset space because of the edges.) Still trying to figure out what's a good way of upper-bounding megaminx god's number that isn't just "build blocks, then more blocks, etc. etc.". I have some vague ideas, but they would be tricky to implement.
 

qqwref

Member
Joined
Dec 18, 2007
Messages
7,834
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
Ben Whitmore recently computed God's Algorithm on the <U,R,F> subgroup and God's Number is 14. So the whole puzzle can be solved in at most 34 moves.
http://cubezzz.dyndns.org/drupal/?q=node/view/560

EDIT: Hey xyzzy, if you see this, it doesn't sound like you considered permutation parity in the separation step. That is, each half must have even permutation. Can you try doing the computation taking that into account? One way might be, for each coset, continue searching for separation algorithms until you find two where the permutation parities of the "top hemisphere" pieces differ. Then one of those two will solve one permutation-parity version of that coset and the other will solve the other, even though you don't know which is which. You can check for differing hemisphere permutations on a puzzle with all pieces distinct, but the search can still be done in the coset space.
 
Last edited:

xyzzy

Member
Joined
Dec 24, 2015
Messages
2,876
it doesn't sound like you considered permutation parity in the separation step.

Oh dang, you're right. There's a way to incorporate the permutation parity into the separation directly and I've done this before (for the Redi Cube solver/scrambler). I don't know why I suddenly just forgot about it…

Will rerun the code and post results shortly.

Edit: Take 2! This is the fixed move distribution for the separation step, now taking parity into account:

depth# reduced cosets
020
1480
29480
386960
4223808
548684
680
Average: 3.841
Upper bound: 6

Upper bound remains unchanged, which is nice to know. I didn't feel like wrapping my head around whether some of the symmetry I exploited in the original post was valid with parity taken into consideration, so this only does the "corner twist" symmetry reduction and has $$\binom{20}{10}\cdot2$$ reduced cosets.

Also interesting to note is that the depth-6 positions are the same regardless of whether parity is taken into account. (The original (incorrect) table lists 20 reduced cosets and this one lists 80 reduced cosets; this factor-of-four difference comes from using less symmetry reduction (2) and including parity (2).)
 
Last edited:

qqwref

Member
Joined
Dec 18, 2007
Messages
7,834
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
Thanks, cool stuff! Ben Whitmore has also computed <R,U,F> in qtm:
DepthNewTotal
011
167
23037
3144181
4696877
533604237
61617620413
77752097933
8369444467377
917522042219581
10825439010473971
113849008748964058
12176067961225032019
13772274582997306601
1430621700564059476657
15943999232913499468986
161562815683629127625822
17643341658435561042406
1815179055135712832957
19224335712835200

Would you mind computing separation in qtm as well?
 

xyzzy

Member
Joined
Dec 24, 2015
Messages
2,876
Clearly we should unban Ben and let him post here directly…

My BFS code doesn't directly support "qtm" but it shouldn't be too hard to add that. (In class now; will do later.)

Edit: Separation + parity, qtm.

depth# reduced cosets
020
1240
22460
316640
469644
5144740
6119688
7160000
880

Combined with Ben's upper bound of 19q for ⟨R,U,F⟩, this gives a bound of 46q in total. (Incidentally, the same as my original bound for FTM…) It'd be nice to get independent verification for this, since I haven't tested this BFS function in an actual solver.
 
Last edited:

xyzzy

Member
Joined
Dec 24, 2015
Messages
2,876
And now, a slightly better lower bound.

Assign this ordering to the twelve face moves of a kilominx: U, DFL, DBL, BL, DB, F, L, DFR, R, BR, DBR, D. (So U < DFL < DBL < … < DBR < D.) We keep track of the last move applied and count the number of move sequences of a given length with a given last move (if the length is at least 1), and reject all move sequences where moves cancel or we can reduce its lexicographic order (wrt the above ordering on moves) by swapping two consecutive moves that commute.

This excludes, for example, "U D U" (the second and third moves can be swapped, then the first and second moves cancel) and "U R D" (the "R" and "D" can be swapped). This almost provides a canonicalisation procedure for move sequences, but it's possible that a move sequence can have multiple reductions, none of which can be reduced further. (This doesn't happen on n×n×n puzzles with OBTM because whether moves commute forms an equivalence relation there; otoh, on the dodecahedral puzzles, you can have three moves such that the first commutes with the second, the second commutes with the third, but the first and third don't commute. An example is L, R, BL.)

If you work out the whole thing, it's a pretty straightforward linear recurrence in 12 variables (one variable for each possible "last move"), although some care is needed in handling the distance-0 and distance-1 special cases.

depth# reduced move sequences
01
148
21536
344928
41293568
537138432
61065635840
730573592576
8877152370688
925165283983360
10721985189445632
1120713556630568960
12594266228722237440
1317049334158528086016
14489140692981253144576
151.4033311521445843e+22
164.026118355634329e+23
171.155082247599007e+25
183.3138990979964524e+26
199.507485076950928e+27

Modulo rotations, a kilominx has 19!×3^18/2 ~ 2.36 × 10^25 states, and since there are fewer move sequences up to length 17 than that, it follows that God's number must be at least 18.
 
Joined
Nov 29, 2008
Messages
214
If you work out the whole thing, it's a pretty straightforward linear recurrence in 12 variables (one variable for each possible "last move"), although some care is needed in handling the distance-0 and distance-1 special cases.

I did an analysis for Megaminx https://www.speedsolving.com/forum/threads/lower-bound-for-megaminx-in-htm-and-qtm.35724/ some time ago. I see no reason why this argumentation should not hold for Kilominx since it has the same set of commutating and not-commutating moves. Especially the number of positions in depth 3 of Megaminx is exactly 43520 (Tom Rokicki provided this number) and this is also the number of "canonical" move sequences I got. So if you have 44928 move sequences for depth 3 with Kilominx it seems that your analysis is not complete. Also your asymptotic branching factor seems to be > 28 which is higher than the 26.4803 I got (which is in accordance with the number for the Dodecahedron given here ).

I get 3.7871*10^24 move sequences with 17 moves and 1.00283*10^26 with 18 moves, so unfortunately the lower bound still stays 18....
 

xyzzy

Member
Joined
Dec 24, 2015
Messages
2,876
I did an analysis for Megaminx https://www.speedsolving.com/forum/threads/lower-bound-for-megaminx-in-htm-and-qtm.35724/ some time ago. I see no reason why this argumentation should not hold for Kilominx since it has the same set of commutating and not-commutating moves. Especially the number of positions in depth 3 of Megaminx is exactly 43520 (Tom Rokicki provided this number) and this is also the number of "canonical" move sequences I got. So if you have 44928 move sequences for depth 3 with Kilominx it seems that your analysis is not complete.
This is entirely correct and I don't know how I missed it!

I was working with an "almost-canonicalisation" procedure like this: for every pair (A, B) of commuting moves, decide whether AB or BA should be the "canonical" representation, and reject every move sequence with a "non-canonical" subsequence. The problem with this is that it's not truly canonical, which explains the discrepancy in our numbers. (The reason that this procedure cannot be canonical in the general case is that, if it were, the numbers would be independent of the ordering of moves I chose (U < DFL < …), but they're not independent.)

Also, something interesting I noticed was that, in the grand scheme of things, a branching factor of 26.something (your analysis) and a branching factor of 44 (naïve analysis) are almost the same on a logarithmic scale; in essence the more complicated analysis only manages to increase the lower bound from 16 moves to 18 moves.
 
Joined
Nov 29, 2008
Messages
214
Also, something interesting I noticed was that, in the grand scheme of things, a branching factor of 26.something (your analysis) and a branching factor of 44 (naïve analysis) are almost the same on a logarithmic scale; in essence the more complicated analysis only manages to increase the lower bound from 16 moves to 18 moves.
This reminds me of a similar behavior concerning the more difficult to find God's number for all these puzzles which also seems to be only a few moves away from the easy to find lower bound, 20 moves versus 18 moves for Rubik's cube for example. This is intuitively quite clear. If you have for example a branching factor of 30 and the lower bound is N, then with N+1 moves you have more canonical sequences than the number of states and with N+3 or N+4 moves you have at least 900 times or 27000 times more canonical sequences than the number of states so that it not unlikely that you "hit" each state at least once.
 

rokicki

Member
Joined
Oct 31, 2008
Messages
301
Building on the previous work, I have reduced the upper bound on God's Number on the kilominx from 34 to 31 in the HTM, and from 46 to 42 in the QTM. I also present a lower bound in the QTM.

I use a three stage decomposition.

First, I fix the corner opposite ULF, turning the three moves that turn that corner into deep moves on the opposite face. So my move set is U u F f L l BL FR BR FL R DL.

My first stage solves the face opposite L (DR) by properly placing the four non-fixed corners. This can always be done in seven moves. The state space here is 57*54*51*48 = 7,534,944 and this is the distance distribution:

0 1 1 1 20 21 2 430 451 3 8345 8796 4 130435 139231 5 1373859 1513090 6 5222857 6735947 7 798997 7534944

The second stage then solves the remaining five pieces in the hemisphere opposite ULF, using only moves that maintain the solved DR face. These moves are U F L l BL FL DL. This step takes at most 10 moves. The state space has size 45*42*39*36*33 = 87,567,480, and the distance distribution is:

0 1 1 1 16 17 2 192 209 3 2452 2661 4 30184 32845 5 345585 378430 6 3476179 3854609 7 23966545 27821154 8 52310104 80131258 9 7434665 87565923 10 1557 87567480

The final stage solves the hemisphere around ULF with the three moves U,L,F as before, which takes a maximum of 14 moves. So the total is 7 + 10 + 14 = 31 moves. The gap between the lower and upper bounds has been reduced from 16 moves to 13.

In the QTM, using the same reduction, we can solve the first stage in 10 moves, with this distribution:

0 1 1 1 10 11 2 110 121 3 1110 1231 4 9905 11136 5 77897 89033 6 497905 586938 7 2140487 2727425 8 3831159 6558584 9 973812 7532396

And the second stage can be solved in 14 moves, with this distribution:

0 1 1 1 8 9 2 52 61 3 334 395 4 2106 2501 5 12936 15437 6 77205 92642 7 437565 530207 8 2253329 2783536 9 9634904 12418440 10 27884812 40303252 11 35786611 76089863 12 11098546 87188409 13 378834 87567243 14 237 87567480

With the QTM bound of 19 moves for the third stage, this gives a new lower bound of 42 moves, a reduction of four moves.

The lower bound for the QTM for the kilominx is 22 moves (based on the same sort of canonical sequence analysis used above for the HTM), so the difference between the upper bound and lower bound has been reduced from 24 to 20 moves.

For completeness, here are the canonical sequence numbers in the QTM:

0 1 1 1 24 25 2 408 433 3 6208 6641 4 90624 97265 5 1300800 1398065 6 18538560 19936625 7 263393280 283329905 8 3737257920 4020587825 9 52996688000 57017275825 10 751335964800 808353240625 11 10650537753600 11458890994225 12 150969043801600 162427934795825 13 2139908037888000 2302335972683825 14 3.03318092352e+16 3.263414520788382e+16 15 4.299320046551e+17 4.625661498629839e+17 16 6.093972263998118e+18 6.556538413861102e+18 17 8.637754132523383e+19 9.293407973909493e+19 18 1.224337234632807e+21 1.317271314371902e+21 19 1.735406475122343e+22 1.867133606559533e+22 20 2.459808749349617e+23 2.64652211000557e+23 21 3.486594640346255e+24 3.751246851346812e+24 22 4.941986665268552e+25 5.317111350403234e+25
 
Last edited:

abunickabhi

Member
Joined
Jan 9, 2014
Messages
6,687
Location
Yo
WCA
2013GHOD01
YouTube
Visit Channel
Building on the previous work, I have reduced the upper bound on God's Number on the kilominx from 34 to 31 in the HTM, and from 46 to 42 in the QTM. I also present a lower bound in the QTM.

I use a three stage decomposition.

First, I fix the corner opposite ULF, turning the three moves that turn that corner into deep moves on the opposite face. So my move set is U u F f L l BL FR BR FL R DL.

My first stage solves the face opposite L (DR) by properly placing the four non-fixed corners. This can always be done in seven moves. The stage space here is 57*54*51*48 = 7,534,944 and this is the distance distribution:

0 1 1 1 20 21 2 430 451 3 8345 8796 4 130435 139231 5 1373859 1513090 6 5222857 6735947 7 798997 7534944

The second stage then solves the remaining five pieces in the hemisphere opposite ULF, using only moves that maintain the solved DR face. These moves are U F L l BL FL DL. This step takes at most 10 moves. The state space has size 45*42*39*36*33 = 87,567,480, and the distance distribution is:

0 1 1 1 16 17 2 192 209 3 2452 2661 4 30184 32845 5 345585 378430 6 3476179 3854609 7 23966545 27821154 8 52310104 80131258 9 7434665 87565923 10 1557 87567480

The final stage solves the hemisphere around ULF with the three moves U,L,F as before, which takes a maximum of 14 moves. So the total is 7 + 10 + 14 = 31 moves. The gap between the lower and upper bounds has been reduced from 16 moves to 13.

In the QTM, using the same reduction, we can solve the first stage in 10 moves, with this distribution:

0 1 1 1 10 11 2 110 121 3 1110 1231 4 9905 11136 5 77897 89033 6 497905 586938 7 2140487 2727425 8 3831159 6558584 9 973812 7532396

And the second stage can be solved in 14 moves, with this distribution:

0 1 1 1 8 9 2 52 61 3 334 395 4 2106 2501 5 12936 15437 6 77205 92642 7 437565 530207 8 2253329 2783536 9 9634904 12418440 10 27884812 40303252 11 35786611 76089863 12 11098546 87188409 13 378834 87567243 14 237 87567480

With the QTM bound of 19 moves for the third stage, this gives a new lower bound of 42 moves, a reduction of four moves.

The lower bound for the QTM for the kilominx is 22 moves (based on the same sort of canonical sequence analysis used above for the HTM), so the difference between the upper bound and lower bound has been reduced from 24 to 20 moves.

For completeness, here are the canonical sequence numbers in the QTM:

0 1 1 1 24 25 2 408 433 3 6208 6641 4 90624 97265 5 1300800 1398065 6 18538560 19936625 7 263393280 283329905 8 3737257920 4020587825 9 52996688000 57017275825 10 751335964800 808353240625 11 10650537753600 11458890994225 12 150969043801600 162427934795825 13 2139908037888000 2302335972683825 14 3.03318092352e+16 3.263414520788382e+16 15 4.299320046551e+17 4.625661498629839e+17 16 6.093972263998118e+18 6.556538413861102e+18 17 8.637754132523383e+19 9.293407973909493e+19 18 1.224337234632807e+21 1.317271314371902e+21 19 1.735406475122343e+22 1.867133606559533e+22 20 2.459808749349617e+23 2.64652211000557e+23 21 3.486594640346255e+24 3.751246851346812e+24 22 4.941986665268552e+25 5.317111350403234e+25
Interesting result Tomas.

How much computational power or time was spent in computing out these bounds?
 

rokicki

Member
Joined
Oct 31, 2008
Messages
301
Interesting result Tomas.

How much computational power or time was spent in computing out these bounds?

About 20 minutes on a single core for HTM and QTM combined, using twsearch. I can provide the twsearch files if anyone wants to reproduce these results.
 
Top