Optimal solutions to the Eliac puzzle

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:
```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          1600300800
```
The 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         1600300800
```
One 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.

Comment viewing options

81 depth 46 HTM cosets solved

I've finished solving the 81 cosets at depth 46 in HTM. Interestingly there are no depth 71 positions in any of these cosets. In the following table, R is the horizontal reflection symmetry.
```Depth  Total mod R  Total
46     1274         2454
47     2335         4502
48     0            0
49     2158         4124
50     19122        36864
51     33754        64956
52     0            0
53     31130        60030
54     231552       446768
55     398096       767699
56     0            0
57     368321       710279
58     2542975      4906638
59     4139738      7987480
60     0            0
61     3764337      7263115
62     22446060     43316694
63     27682873     53421905
64     0            0
65     18614465     35900464
66     41507290     80003107
67     5061121      9737879
68     0            0
69     155594       297932
70     5805         11110```

Solutions of the hard positions

Not sure why all of the line breaks disappeared in my post, but it's still readable I suppose...

Here are the solutions of the two positions given:

80 QTM position: L R2 L R2 L R2 L R2 L' R2 L' R2 L2 R2 L R2 L2 R2 L R2 L2 R2 L R2 L2 R2 L2 R2 L' R2 L R2 L2 R2 L' R2 L2 R2 L R2 L R2 L2 R2 L2 R2 L2 R2 L2 R2 L' R2 L R2 L' R2 L R2 L2 R2 L' R2 L R2 L R2 L' R2

71 HTM position: R2 L R2 L' R2 L2 R2 L R2 L2 R2 L2 R2 L R2 L2 R2 L R2 L' R2 L2 R2 L R2 L' R2 L2 R2 L' R2 L2 R2 L R2 L' R2 L2 R2 L2 R2 L R2 L' R2 L R2 L2 R2 L' R2 L2 R2 L R2 L R2 L R2 L' R2 L2 R2 L R2 L' R2 L' R2 L2 R2