cube files
Indexed Cube Lovers Archive
Optimal solutions to the Eliac puzzle
Submitted by Ben Whitmore on Sat, 05/18/2019 - 16:13.
The Eliac is a complex deep-cut 2-gen circle puzzle:
The left circle rotates in increments of 90 degrees and the right circle rotates only by 180 degrees. There is a simulator of the puzzle here.
Using ksolve++ I made an optimal solver modified it slightly to turn it into a coset solver. The subgroup I used for the coset solver is the subgroup of positions where the 18 small triangles, 10 diamonds, and 2 squares are solved. There are 1600300800 arrangements of those 30 pieces and each coset has 3024000 solvable positions. Unfortunately since the puzzle is 2-gen, there isn't a good way to select a subgroup generated by a subset of the generators of the whole puzzle, which (as far as I can tell) is what is required in order to make the "pre-pass" trick work for sub-optimally solving cosets very quickly. So each coset needs to be solved optimally using a pure DFS, which takes quite a long time (about 1.5 hours on my laptop). Notice that the puzzle has a horizontal reflection symmetry so we only need to solve one coset in each symmetry class.
First, in the "quarter" turn metric (L L' R2 = 1 move, L2 = 2 moves): The quotient set has the following distribution:
In the half turn metric (L L2 L' R2 = 1 move): The quotient set has the following distribution:
Based on these findings, I conjecture that god's number is 71 HTM and 80 QTM.
The left circle rotates in increments of 90 degrees and the right circle rotates only by 180 degrees. There is a simulator of the puzzle here.
Using ksolve++ I made an optimal solver modified it slightly to turn it into a coset solver. The subgroup I used for the coset solver is the subgroup of positions where the 18 small triangles, 10 diamonds, and 2 squares are solved. There are 1600300800 arrangements of those 30 pieces and each coset has 3024000 solvable positions. Unfortunately since the puzzle is 2-gen, there isn't a good way to select a subgroup generated by a subset of the generators of the whole puzzle, which (as far as I can tell) is what is required in order to make the "pre-pass" trick work for sub-optimally solving cosets very quickly. So each coset needs to be solved optimally using a pure DFS, which takes quite a long time (about 1.5 hours on my laptop). Notice that the puzzle has a horizontal reflection symmetry so we only need to solve one coset in each symmetry class.
First, in the "quarter" turn metric (L L' R2 = 1 move, L2 = 2 moves): The quotient set has the following distribution:
Depth New Total 0 1 1 1 3 4 2 5 9 3 8 17 4 13 30 5 21 51 6 34 85 7 55 140 8 87 227 9 135 362 10 212 574 11 336 910 12 532 1442 13 842 2284 14 1330 3614 15 2102 5716 16 3328 9044 17 5268 14312 18 8334 22646 19 13184 35830 20 20850 56680 21 32970 89650 22 52132 141782 23 82432 224214 24 130316 354530 25 205972 560502 26 325474 885976 27 514059 1400035 28 811497 2211532 29 1280423 3491955 30 2018664 5510619 31 3178372 8688991 32 4995505 13684496 33 7830623 21515119 34 12228118 33743237 35 18987309 52730546 36 29227594 81958140 37 44420837 126378977 38 66262852 192641829 39 96117892 288759721 40 133904784 422664505 41 176000175 598664680 42 213210584 811875264 43 231056520 1042931784 44 216256467 1259188251 45 168138807 1427327058 46 104002928 1531329986 47 48698841 1580028827 48 16217649 1596246476 49 3562546 1599809022 50 461818 1600270840 51 29217 1600300057 52 741 1600300798 53 2 1600300800The two cosets at depth 53 are not symmetrical so they form one equivalence class. Of the 741 depth 52 cosets, 5 are symmetrical and the others form 368 equivalence classes of pairs. I've solved the depth 53 class and 23 classes from depth 52 (including the 5 symmetrical ones). All of them have a maximum depth of 80. In total there were 442 positions at depth 80 (not including the positions obtained by reflecting the non-symmetrical positions). Here is one such position from the depth 53 coset:
In the half turn metric (L L2 L' R2 = 1 move): The quotient set has the following distribution:
Depth New Total 0 1 1 1 4 5 2 6 11 3 12 23 4 18 41 5 36 77 6 53 130 7 104 234 8 154 388 9 296 684 10 440 1124 11 856 1980 12 1270 3250 13 2468 5718 14 3666 9384 15 7116 16500 16 10560 27060 17 20508 47568 18 30414 77982 19 59012 136994 20 87530 224524 21 169772 394296 22 251842 646138 23 488060 1134198 24 723224 1857422 25 1398656 3256078 26 2070027 5326105 27 3988708 9314813 28 5884524 15199337 29 11243144 26442481 30 16464145 42906626 31 30809268 73715894 32 44287921 118003815 33 78806648 196810463 34 108230306 305040769 35 171023128 476063897 36 211413339 687477236 37 258293040 945770276 38 257672851 1203443127 39 194871324 1398314451 40 134425097 1532739548 41 47053564 1579793112 42 18298945 1598092057 43 1911328 1600003385 44 293986 1600297371 45 3348 1600300719 46 81 1600300800One interesting thing in HTM is that in each coset, there are no positions at depth n, n+4, n+8, ... for some initial n because the two square pieces in the puzzle remain unchanged after applying any 4 move algorithm, e.g. if a coset at say depth 45 consists of positions with the squares not swapped, then there must be an even number of R2 moves in all of the solutions, which implies that the length of the solution can not be 2 mod 4. Of the 81 cosets at depth 46, there are 3 symmetrical and 39 non-symmetrical pairs. The 3 symmetrical cosets have a maximum depth of 70. Of the 3348 cosets at depth 45, there are 14 symmetrical and 1667 non-symmetrical pairs. So far, I have solved 3 of the symmetrical cosets. Two have a maximum depth of 69, and the other contained one position at depth 71, which is the following position:
Based on these findings, I conjecture that god's number is 71 HTM and 80 QTM.
