Home »

Kilominx can be solved in 34 moves

Submitted by Ben Whitmore on Sun, 02/11/2018 - 12:58.
Last night, I found this thread on the speedsolving forums which proves an upper bound of 46 moves. First, the puzzle is separated into two halves, which takes at most 6 moves. Each half is then solved in at most 20 moves (= 7 moves for orientation + 13 moves for permutation, after orientation is solved), for a total of 6+2*(7+13) = 46. xyzzy writes 
The ⟨U,R,F⟩ 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.
I just completed this BFS. No symmetry reduction was necessary, just a standard BFS was used, and it took just over 11 hours to run. 
Depth	New		Total
0	1		1
1	12		13
2	96		109
3	768		877
4	6144		7021
5	49152		56173
6	392364		448537
7	3117359		3565896
8	24649511	28215407
9	192551113	220766520
10	1438993775	1659760295
11	8766794158	10426554453
12	21419138541	31845692994
13	3866926287	35712619281
14	215919		35712835200
15	0		35712835200
So the diameter of <U,R,F> is 14 which gives an upper bound on the full puzzle of 6+2*14 = 34.
» 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.

I confirm these numbers (in t

Submitted by rokicki on Tue, 03/10/2020 - 13:19.
I confirm these numbers (in the HTM).

My confirmation of the numbers took less than 20 minutes on a single core using no puzzle-specific code. I used puzzle-geometry to generate a "good" ksolve-type description of the kilominx with moves U,R,F, and fed that to twsearch. I did not have to write a single line of new code to confirm these numbers.

I also generated all the antipodes and tried to solve them all using all moves (rather than just U,R,F). The great majority are solvable in fewer than 14 moves, but there are a fair percentage that do require 14 moves even using all generators. So my attempt to reduce the bound by two moves was thwarted.
» login or register to post comments

46 "quarter" turns suffice

Submitted by Ben Whitmore on Tue, 02/13/2018 - 05:45.
xyzzy computes that the separation phase takes 8 moves, and my <U,R,F> computation (distribution below) shows that 19 moves are enough, for a total of 8+2*19=46. 
Depth	New		Total
0	1		1
1	6		7
2	30		37
3	144		181
4	696		877
5	3360		4237
6	16176		20413
7	77520		97933
8	369444		467377
9	1752204		2219581
10	8254390		10473971
11	38490087	48964058
12	176067961	225032019
13	772274582	997306601
14	3062170056	4059476657
15	9439992329	13499468986
16	15628156836	29127625822
17	6433416584	35561042406
18	151790551	35712832957
19	2243		35712835200
20	0		35712835200
» login or register to post comments

Or maybe not...

Submitted by Ben Whitmore on Sun, 02/11/2018 - 20:05.
I just noticed that in the speedsolving thread, it appears that xyzzy forgot to consider permutation parity in the separation phase. For now, note that the parity of the permutations in each hemisphere can be flipped by doing L' BL' L BL. This gives an upper bound of 38, although it can likely be improved by a move or two if the separation phase computation is corrected. xyzzy said he will redo the computation and post the results soon.
» login or register to post comments

34 move upper bound is correct

Submitted by Ben Whitmore on Sun, 02/11/2018 - 21:23.
xyzzy has redone the separation computation with the permutation parity correction, and surprisingly, the upper bound is still 6 moves. So the 34 move bound is correct after all.
» login or register to post comments